Campus Event Calendar
Event Entry
What and Who
Arithmetic Circuits : A chasm at depth four
Nitin Saurabh
Max-Planck-Institut für Informatik - D1
MPI-Seminar
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 9 May 2018
16:15
60 Minutes
E1 4
022
Saarbrücken
Abstract
Agrawal and Vinay [FOCS'08] showed that any polynomial size arithmetic circuit can be reduced to a subexponential sized circuit of depth 4. This reduction was further analyzed carefully by Koiran [TCS'12] and Tavenas [MFCS'13]. We will discuss the proof, and consequences of depth reduction to lower bounds.
Contact
Daniel Vaz
--email hidden
passcode not visible
logged in users only
Daniel Vaz, 05/02/2018 15:07 -- Created document.