Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with identities:
TR08-108 | 19th November 2008
Nitin Saxena, C. Seshadhri

An Almost Optimal Rank Bound for Depth-3 Identities

We show that the rank of a depth-3 circuit (over any field) that is simple,
minimal and zero is at most O(k^3\log d). The previous best rank bound known was
2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005).
This almost resolves the rank question first posed by ... 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 >>>

TR10-167 | 5th November 2010
Nitin Saxena, C. Seshadhri

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F.
It is a major open problem to design a deterministic polynomial time blackbox algorithm
that tests if C is identically zero.
Klivans & Spielman (STOC 2001) observed ... more >>>

ISSN 1433-8092 | Imprint