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:Multi-k-ic depth three circuit lower bound
Speaker:Chandan Saha
coming from:Indian Institute of Science, Bangalore
Speakers Bio:
Event Type:Talk
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 20 March 2015
Duration:60 Minutes
In a multi-k-ic depth three circuit, every variable appears in at most k of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables (as the formal degree of a multi-k-ic depth three circuit can be kn where n is the number of variables). The problem of proving lower bounds for depth three circuits with high formal degree has gained in importance following a work by Gupta, Kamath, Kayal and Saptharishi (2013) on depth reduction to high formal degree depth three circuits. In the talk, we will show an exponential lower bound for multi-k-ic depth three circuits for any arbitrary constant k.

Based on joint work with Neeraj Kayal.

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

Created:Karteek Sreenivasaiah, 03/12/2015 01:45 PM Last modified:Uwe Brahm/MPII/DE, 03/20/2015 04:01 AM
  • Karteek Sreenivasaiah, 03/12/2015 01:45 PM -- Created document.