Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with depth-3:
TR99-023 | 16th June 1999
Amir Shpilka, Avi Wigderson

Depth-3 Arithmetic Formulae over Fields of Characteristic Zero

In this paper we prove near quadratic lower bounds for
depth-3 arithmetic formulae over fields of characteristic zero.
Such bounds are obtained for the elementary symmetric
functions, the (trace of) iterated matrix multiplication, and the
determinant. As corollaries we get the first nontrivial lower
bounds for ... more >>>

TR07-042 | 7th May 2007
Zohar Karnin, Amir Shpilka

Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in

Revisions: 2 , Comments: 1

In this paper we consider the problem of determining whether an
unknown arithmetic circuit, for which we have oracle access,
computes the identically zero polynomial. Our focus is on depth-3
circuits with a bounded top fan-in. We obtain the following

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>

TR09-101 | 20th October 2009
Nitin Saxena

Progress on Polynomial Identity Testing

Polynomial identity testing (PIT) is the problem of checking whether a given
arithmetic circuit is the zero circuit. PIT ranks as one of the most important
open problems in the intersection of algebra and computational complexity. In the last
few years, there has been an impressive progress on this ... more >>>

TR10-013 | 31st January 2010
Nitin Saxena, C. Seshadhri

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits

Revisions: 1

We study the problem of identity testing for depth-3 circuits, over the
field of reals, of top fanin k and degree d (called sps(k,d)
identities). We give a new structure theorem for such identities and improve
the known deterministic d^{k^k}-time black-box identity test (Kayal &
Saraf, FOCS 2009) to one ... more >>>

TR16-143 | 15th September 2016
Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan

An Almost Cubic Lower Bound for $\Sigma\Pi\Sigma$ Circuits Computing a Polynomial in VP

In this note, we prove that there is an explicit polynomial in VP such that any $\Sigma\Pi\Sigma$ arithmetic circuit computing it must have size at least $n^{3-o(1)}$. Up to $n^{o(1)}$ factors, this strengthens a recent result of Kayal, Saha and Tavenas (ICALP 2016) which gives a polynomial in VNP with ... more >>>

TR17-092 | 10th May 2017
Shuichi Hirahara

A Duality Between Depth-Three Formulas and Approximation by Depth-Two

We establish an explicit link between depth-3 formulas and one-sided approximation by depth-2 formulas, which were previously studied independently. Specifically, we show that the minimum size of depth-3 formulas is (up to a factor of n) equal to the inverse of the maximum, over all depth-2 formulas, of one-sided-error correlation ... more >>>

TR23-014 | 16th February 2023
Tameem Choudhury, Karteek Sreenivasaiah

Depth-3 Circuit Lower Bounds for k-OV

The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples $A$ and $B$ of $n$ vectors each of dimension $d$, decide if there exists a vector $u\in A$, and $v\in B$ such that $u$ and $v$ are orthogonal. This problem, and its generalization $k$-OV defined analogously for $k$ tuples, ... more >>>

ISSN 1433-8092 | Imprint