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