BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1194
DTSTAMP:20230914T125954Z
SUMMARY:Hardness and Independence of Polynomials
DESCRIPTION:Speaker: Prerona Chatterjee\n\nAbstract: \nAlgebraic Complexit
y Theory is a field in which one studies complexity theoretic questions su
rrounding algebraic objects. In this talk we will be broadly discussing tw
o such problems.\nThe first problem is showing lower bounds for explicit p
olynomials against various algebraic computational models. The most natura
l and well studied models of computation are algebraic circuits\, algebrai
c branching programs (ABPs) and algebraic formulas. With respect to provin
g lower bounds against these models\, we show the following results.\n1. A
ny algebraic branching program computing \\sum_{i=1}^n x_i^n must have at
least n^2 vertices. The previous best known lower bound was \\Omega(n log
n) on the number of edges for the same polynomial [Baur-Strassen].\n2. Any
formula computing the elementary symmetric polynomial of degree 0.1n must
have at least n^2 vertices. The previous best lower bound for any multili
near polynomial was \\Omega(n^2/log n) [Nechiporuk\, Kalorkoti]. It can al
so be shown that previous known methods can not prove a bound better than
\\Omega(n^2/log n) for any explicit multilinear polynomial.\nThis is joint
work with Mrinal Kumar\, Adrian She and Ben Lee Volk.\nAlong with proving
lower bounds against these models\, studying their relative powers is als
o an important problem in algebraic circuit complexity. It is known that f
ormulas can be efficiently simulated by ABPs and checking whether the conv
erse of this statement holds is a central question in the field. We make p
rogress towards solving this problem in the non-commutative setting\, wher
e we show a tight super-polynomial separation between ABPs and some struct
ured formulas.\nThe second problem that we are interested in relates the q
uestions of checking whether a given algebraic compuational model is compu
ting the zero polynomial or not and checking whether a given set of polyno
mials is algebraically independent or not. The connection between these qu
estions is via the notion of Faithful Homomorphisms. Although construction
of faithful homomorphisms were known when the underlying field had charac
teristic zero [Beecken-Mittman-Saxena\, Agrawal-Saha-Saptharishi-Saxena]\,
they were not known in the setting where the underlying field had finite
characteristic since efficient algorithms to check algebraic indepndence w
ere not known in this setting. Following up on the work of Pandey\, Saxena
andÂ Sinhababu\, we construct faithful homomorphisms over fields of fini
te characetristics in some restricted settings and as a consequence show e
fficient polynomial identity tests for related models of computation. This
is joint work with Ramprasad Saptharishi.\n
URL:https://www.tcs.tifr.res.in/web/events/1194
DTSTART;TZID=Asia/Kolkata:20220317T143000
DTEND;TZID=Asia/Kolkata:20220317T153000
LOCATION:in person @ R.No. AG-66 and also via Zoom
END:VEVENT
END:VCALENDAR