Campus Event Calendar
Event Entry
What and Who
On the Complexity of Symmetric Polynomials
Gorav Jindal
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 7 August 2018
13:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
A function f(x1,x2,..,xn) is said to be symmetric if it is invariant under any permutation of the n input variables x1,x2,..,xn.
We know that symmetric Boolean functions are easy to compute because they only depend upon the number of 1's in the input.
So one can ask the same question for symmetric polynomials also. In this work, we show that there exist hard symmetric polynomials whose arithmetic complexity is super polynomial (assuming VP \neq VNP). The main tool used in proving this result is the so called "Newton's Iteration" for power series.
Contact
Gorav Jindal
--email hidden
passcode not visible
logged in users only
Gorav Jindal, 07/23/2018 16:03
Gorav Jindal, 07/23/2018 16:02 -- Created document.
Gorav Jindal, 07/23/2018 16:02 -- Created document.