Max-Planck-Institut für Informatik
max planck institut
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:Depth Reduction in arithmetic circuits
Speaker:Ramprasad Saptharishi
coming from:Chennai Mathematical Institute
Speakers Bio:
Event Type:Talk
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Monday, 16 March 2015
Duration:60 Minutes
The first step in almost all lower bound proofs is to find a good starting model to attack the circuit class of interest. This is normally achieved via a "depth reduction" to obtain a "shallow circuit" of not too large size. For most of the lower bounds in depth-4 circuits, this step is provided by the results of [Agrawal-Vinay] and subsequent strengthening by [Koiran] and [Tavenas]. Other lower bounds, such as the recent non-homogeneous depth-three lower bound by [Kayal-Saha] build on a depth reduction to depth three circuits [Gupta et al.].

In this talk, we shall see an overview of some of these depth reduction results and how they directly influenced lower bounds subsequently. We shall also see a slightly different perspective* of [Tavenas] strengthening of [Agrawal-Vinay] that might have some relevance to attacking homogeneous formulas.

Based on joint work with V Vinay

Name(s):Karteek Sreenivasaiah
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created by:Karteek Sreenivasaiah, 03/12/2015 01:55 PMLast modified by:Uwe Brahm/MPII/DE, 03/16/2015 04:01 AM
  • Karteek Sreenivasaiah, 03/12/2015 01:55 PM -- Created document.