BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: The fundamental theorem of symmetric polynomials states that f
or a symmetric polynomial f _Sym in C [ x 1 \, x 2 \,...\, x n ]\, t
here exists a unique "witness" f in C [ y 1 \, y 2 \,...\, y n ] su
ch that f _Sym= f ( e 1 \, e 2 \,...\, e n )\, where the e_ i 's are
the elementary symmetric polynomials. In this work\, we study the arithmet
ic complexity L ( f ) of the witness f as a function of the arithmetic c
omplexity L ( f _Sym) of f _Sym. We show that the arithmetic complexity
L ( f ) of f is bounded by poly( L ( f _Sym)\,deg( f )\, n ). Prior to th
is work\, only exponential upper bounds were known for L ( f ). The main i
ngredient in our result is an algebraic analogue of Newton’s iteration on p
ower series. As a corollary of this result\, we show that if VP is not equa
l to VNP then there are symmetric polynomial families which have super-poly
nomial arithmetic complexity. This is joint work with Markus Bläser.
DTSTAMP:20200109T185400
DTSTART:20200120T170000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Gorav Jindal (Aalto University\, Helsinki): On the Complexity of Sy
mmetric Polynomials
UID:104960969@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200120-C-Jindal.html
END:VEVENT
END:VCALENDAR