Campus Event Calendar
Event Entry
What and Who
Multi-k-ic depth three circuit lower bound
Chandan Saha
Indian Institute of Science, Bangalore
Talk
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 20 March 2015
09:30
60 Minutes
E2.1
001
Saarbrücken
Abstract
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.
Contact
Karteek Sreenivasaiah
--email hidden
passcode not visible
logged in users only
Karteek Sreenivasaiah, 03/12/2015 13:45 -- Created document.