Name
Abstract | ||
|---|---|---|
We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula each variable occurs only a constant number of times and each subformula computes a multilinear polynomial. Before our work no subexponential-time deterministic algorithm was known for this class of formulae. We also present a deterministic algorithm that works in a blackbox fashion and runs in quasi-polynomial time in general, and polynomial time for constant depth. Finally, we extend our results and allow the inputs to be replaced with sparse polynomials. Our results encompass recent deterministic identity tests for sums of a constant number of read-once formulae, and for multilinear depth-four circuits. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/CCC.2011.18 | CCC '11 Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity |
Keywords | Field | DocType |
computational complexity,deterministic algorithms,blackbox fashion,multilinear constant-read formulae,polynomial identity testing,polynomial-time deterministic algorithm,quasi-polynomial time,sparse polynomials,arithmetic circuit,bound-depth circuit,derandomization | Polynomial identity testing,Discrete mathematics,Multilinear map,Mathematics | Conference |
ISSN | ISBN | Citations |
1093-0159 E-ISBN : 978-0-7695-4411-3 | 978-0-7695-4411-3 | 15 |
PageRank | References | Authors |
0.63 | 22 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthew Anderson | 1 | 33 | 2.67 |
| Dieter van Melkebeek | 2 | 487 | 32.80 |
| Ilya Volkovich | 3 | 145 | 8.64 |