ECCC-Report TR15-015https://eccc.weizmann.ac.il/report/2015/015Comments and Revisions published for TR15-015en-usFri, 30 Jan 2015 12:28:00 +0200
Paper TR15-015
| Multi-$k$-ic depth three circuit lower bound |
Neeraj Kayal,
Chandan Saha
https://eccc.weizmann.ac.il/report/2015/015In 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 (FOCS 2013) on depth reduction to high formal degree depth three circuits. In this work, we show an exponential lower bound for multi-$k$-ic depth three circuits for any arbitrary constant $k$.Fri, 30 Jan 2015 12:28:00 +0200https://eccc.weizmann.ac.il/report/2015/015