Polynomial Identity Testing for Depth 3 Circuits

Kayal, Neeraj ; Saxena, Nitin (2007) Polynomial Identity Testing for Depth 3 Circuits Computational Complexity, 16 (2). pp. 115-138. ISSN 1016-3328

Full text not available from this repository.

Official URL: http://doi.org/10.1007/s00037-007-0226-9

Related URL: http://dx.doi.org/10.1007/s00037-007-0226-9


We study the identity testing problem for depth 3 arithmetic circuits (ΣΠΣ circuit). We give the first deterministic polynomial time identity test for ΣΠΣ circuits with bounded top fanin. We also show that the rank of a minimal and simple ΣΠΣ circuit with bounded top fanin, computing zero, can be unbounded. These results answer the open questions posed by Klivans–Spielman (STOC 2001) and Dvir–Shpilka (STOC 2005).

Item Type:Article
Source:Copyright of this article belongs to Springer Nature Switzerland AG.
ID Code:122753
Deposited On:12 Aug 2021 13:20
Last Modified:12 Aug 2021 13:20

Repository Staff Only: item control page