Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On the Complexity of Symmetric Polynomials
Speaker:Gorav Jindal
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 7 August 2018
Time:13:00
Duration:45 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Gorav Jindal
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created:
Gorav Jindal, 07/23/2018 04:02 PM
Last modified:
Uwe Brahm/MPII/DE, 08/07/2018 07:01 AM
  • Gorav Jindal, 07/23/2018 04:03 PM
  • Gorav Jindal, 07/23/2018 04:02 PM -- Created document.