Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SHALLOW ARITHMETIC CIRCUITS:
Reports tagged with shallow arithmetic circuits:
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