BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/907
DTSTAMP:20230914T125943Z
SUMMARY:Bootstrapping Identity Tests for Algebraic Models
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nPolynomial identity testi
ng (PIT) is the algorithmic task of determining whether a given polynomia
l is identically zero. The ``Schwarz-Zippel lemma'\;'\; (credited t
o Ore\, DeMillo\, Lipton\, Schwarz and Zippel) gives us that any nonzero
polynomial of degree d on n variables evaluates to a nonzero value on som
e point in the n dimensional grid [d+1] x ... x [d+1]. Hence this grid fo
rms an exponential sized ``hitting set'\;'\; for the class of n-var
iate polynomials of degree d.\nFor the class of n-variate\, degree-d polyn
omials that have algebraic formulas of size s\; a hitting set of size pol
y(n\,d\,s) is known to exist. However\, constructing an explicit hitting
set of any non-trivial size remains an open problem. In this talk\, we wi
ll see the following surprising result. Suppose for some constant $n$ and
all $d \\leq s$\, we have an explicit hitting set of size $s^{(n - 1)}$
for $n$- variate\, degree-$d$ polynomials that have formulas of size $s$.
Then for all $s$\, we have an explicit hitting set of size $s^{tiny(s)}$
for $s$-variate\, degree-$s$ polynomials that have formulas of size $s$.
Here $tiny(s) = exp(exp(log^{*}s))$\, which grows barely faster than a c
onstant. Arguments in the proof will be fairly elementary and hence very
little background in algebra or algebraic complexity will be assumed for
the talk (joint work with Mrinal Kumar (Simons Institute\, UCB) and Rampra
sad Saptharishi).\n
URL:https://www.tcs.tifr.res.in/web/events/907
DTSTART;TZID=Asia/Kolkata:20181012T171500
DTEND;TZID=Asia/Kolkata:20181012T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR