Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with depth reductions:
TR16-096 | 14th June 2016
Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay

The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revisions: 2

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>>

TR16-137 | 3rd September 2016
Mrinal Kumar, Ramprasad Saptharishi

Finer separations between shallow arithmetic circuits

In this paper, we show that there is a family of polynomials $\{P_n\}$, where $P_n$ is a polynomial in $n$ variables of degree at most $d = O(\log^2 n)$, such that

1. $P_n$ can be computed by linear sized homogeneous depth-$5$ circuits.

2. $P_n$ can be computed by ... more >>>

ISSN 1433-8092 | Imprint