BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1383
DTSTAMP:20240111T083135Z
SUMMARY:On the degree of polynomials computing square roots mod p
DESCRIPTION:Speaker: Shanthanu  Suresh Rai (TIFR)\n\nAbstract: \nFor an odd
  prime p\, we say that a polynomial f(X) in F_p[X] computes square roots m
 od p if for all non-zero perfect squares a\, f(a)^2 = a (mod p).Problem: C
 onstruct a low degree polynomial f(X) that compute square roots mod p.It c
 an be easily shown that f(X) has degree between p/4 and p/2. When p = 3 mo
 d 4\, it is well-known that f(X)=X^{(p+1)/4} computes square roots\, and t
 he degree is as low as possible.When p = 1 mod 4\, previously no non-trivi
 al lower bound for degree of f(X) were known. In the paper\, the authors s
 how that f(X) has degree at least (p-1)/3. The main ingredient in the proo
 f is the following general lemma: powers of low degree polynomial cannot h
 ave too many consecutive zero coefficients.In the other direction\, the au
 thors show that for infinitely many p = 1 mod 4\, the degree of the polyno
 mial computing square roots can be (1/2-Ω(1))p.Paper link: https://eccc.
 weizmann.ac.il/report/2023/177/downloadAuthors: Kiran Kedlaya\, Swastik Ko
 pparty\n
URL:https://www.tcs.tifr.res.in/web/events/1383
DTSTART;TZID=Asia/Kolkata:20240112T143000
DTEND;TZID=Asia/Kolkata:20240112T153000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR