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
Abstract
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
