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:Discovering the roots: Uniform closure results for algebraic classes under factoring
Speaker:Pranjal Dutta
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 22 May 2018
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. I will talk about generalizing it to a matrix recurrence that approximates all the roots "simultaneously". I will also discuss an interesting property of multivariate polynomial factorization which shows that under a random linear transformation τ , f(τx) completely factors via power series roots. Combining these, I will establish that for an algebraic circuit f(x_1 , ... , x_n ) of size s , each factor has size at most a polynomial in s and the degree of the square-free part of f. This partially solves the "factor conjecture" proposed by Peter Bürgisser.

This is based on joint work with Nitin Saxena (IIT Kanpur) and Amit Sinhababu (IIT Kanpur), STOC'18.

Contact
Name(s):Christian Ikenmeyer
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created:Christian Ikenmeyer, 05/15/2018 03:58 PM Last modified:Uwe Brahm/MPII/DE, 05/22/2018 04:01 AM
  • Christian Ikenmeyer, 05/15/2018 03:58 PM -- Created document.