Blackbox polynomial identity testing for depth 3 circuits
We study EIIE(k) circuits, i.e., depth three arithmetic circuits with top fanin k. We give the first deterministic polynomial time blackbox identity test for EIIE(k) circuits over the field Q of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001).
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/59436 |
| _version_ | 1826195273988177920 |
|---|---|
| author | Kayal, Neeraj Saraf, Shubhangi |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kayal, Neeraj Saraf, Shubhangi |
| author_sort | Kayal, Neeraj |
| collection | MIT |
| description | We study EIIE(k) circuits, i.e., depth three arithmetic
circuits with top fanin k. We give the first deterministic polynomial
time blackbox identity test for EIIE(k) circuits over the field Q of
rational numbers, thus resolving a question posed by Klivans and
Spielman (STOC 2001). |
| first_indexed | 2024-09-23T10:10:07Z |
| format | Article |
| id | mit-1721.1/59436 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:10:07Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/594362022-09-30T19:20:23Z Blackbox polynomial identity testing for depth 3 circuits Kayal, Neeraj Saraf, Shubhangi Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Saraf, Shubhangi Saraf, Shubhangi Arithmetic circuits Derandomization Sylvester–Gallai Theorem We study EIIE(k) circuits, i.e., depth three arithmetic circuits with top fanin k. We give the first deterministic polynomial time blackbox identity test for EIIE(k) circuits over the field Q of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001). National Science Foundation (U.S.) (Award CCF 0829672) 2010-10-20T20:25:16Z 2010-10-20T20:25:16Z 2010-03 2009-10 Article http://purl.org/eprint/type/JournalArticle 978-1-4244-5116-6 0272-5428 INSPEC Accession Number: 11207145 http://hdl.handle.net/1721.1/59436 Kayal, N., and S. Saraf. “Blackbox Polynomial Identity Testing for Depth 3 Circuits.” Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on. 2009. 198-207. © 2009 Institute of Electrical and Electronics Engineers. en_US http://dx.doi.org/10.1109/FOCS.2009.67 50th Annual IEEE Symposium on Foundations of Computer Science, 2009. FOCS '09 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Arithmetic circuits Derandomization Sylvester–Gallai Theorem Kayal, Neeraj Saraf, Shubhangi Blackbox polynomial identity testing for depth 3 circuits |
| title | Blackbox polynomial identity testing for depth 3 circuits |
| title_full | Blackbox polynomial identity testing for depth 3 circuits |
| title_fullStr | Blackbox polynomial identity testing for depth 3 circuits |
| title_full_unstemmed | Blackbox polynomial identity testing for depth 3 circuits |
| title_short | Blackbox polynomial identity testing for depth 3 circuits |
| title_sort | blackbox polynomial identity testing for depth 3 circuits |
| topic | Arithmetic circuits Derandomization Sylvester–Gallai Theorem |
| url | http://hdl.handle.net/1721.1/59436 |
| work_keys_str_mv | AT kayalneeraj blackboxpolynomialidentitytestingfordepth3circuits AT sarafshubhangi blackboxpolynomialidentitytestingfordepth3circuits |