Kayal, N. ; Saxena, N. (2006) Polynomial Identity Testing for Depth 3 Circuits In: CCC '06: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, July 2006.
Full text not available from this repository.
Official URL: http://doi.org/10.1109/CCC.2006.34
Related URL: http://dx.doi.org/10.1109/CCC.2006.34
Abstract
We study the identity testing problem for depth 3 arithmetic circuits (\Sigma\Pi\Sigma circuit). We give the first deterministic polynomial time identity test for \Sigma\Pi\Sigma circuits with bounded top fanin. We also show that the rank of a minimal and simple \Sigma\Pi\Sigma circuit with bounded top fanin, computing zero, can be unbounded. These results answer the open questions posed by Klivans-Spielman [KS01] and Dvir-Shpilka [DS05].
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Association for Computing Machinery. |
| ID Code: | 122779 |
| Deposited On: | 16 Aug 2021 07:59 |
| Last Modified: | 16 Aug 2021 07:59 |
Repository Staff Only: item control page
