@inproceedings{kayal2015multi-k-ic,
author = {Kayal, Neeraj and Saha, Chandan},
title = {Multi-k-ic depth three circuit lower bound},
booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)},
year = {2015},
month = {March},
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 [GKKS13a] 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 .},
publisher = {LIPICS},
url = {http://approjects.co.za/?big=en-us/research/publication/multi-k-ic-depth-three-circuit-lower-bound/},
edition = {Symposium on Theoretical Aspects of Computer Science (STACS)},
}