Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Depth 4 arithmetic circuits:
TR13-181 | 20th December 2013
Mrinal Kumar, Shubhangi Saraf

Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits

In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree $n$ in $n^2$ variables such that any homogeneous depth 4 arithmetic circuit computing it must have size $n^{\Omega(\log \log n)}$.

Our results extend ... more >>>

TR19-035 | 5th March 2019
Alexey Milovanov

PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials

This text is a development of a preprint of Ankit Gupta.

We present an approach for devising a deterministic polynomial time whitekbox identity testing (PIT) algorithm for depth-$4$ circuits with bounded top fanin.
This approach is similar to Kayal-Saraf approach for depth-$3$ circuits. Kayal and Saraf based their ... more >>>

ISSN 1433-8092 | Imprint