Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-015 | 30th January 2015 11:59

Multi-$k$-ic depth three circuit lower bound


Authors: Neeraj Kayal, Chandan Saha
Publication: 30th January 2015 12:28
Downloads: 772


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 (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$.

ISSN 1433-8092 | Imprint