ECCC-Report TR10-188https://eccc.weizmann.ac.il/report/2010/188Comments and Revisions published for TR10-188en-usSat, 21 May 2011 21:35:40 +0300
Revision 1
| Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae |
Matthew Anderson,
Dieter van Melkebeek,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2010/188#revision1We 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. Our algorithm runs in time $s^{O(1)}\cdot n^{k^{O(k)}}$, where $s$ denotes the size of the formula, $n$ denotes the number of variables, and $k$ bounds the number of occurrences of each variable. 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 time $n^{k^{O(k)} + O(k \log n)}$ in general, and time $n^{k^{O(k^2)} + O(kD)}$ for depth $D$. 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 formulae.
Sat, 21 May 2011 21:35:40 +0300https://eccc.weizmann.ac.il/report/2010/188#revision1
Paper TR10-188
| Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae |
Matthew Anderson,
Dieter van Melkebeek,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2010/188We 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. Our algorithm runs in time $s^{O(1)}\cdot n^{k^{O(k)}}$, where $s$ denotes the size of the formula, $n$ denotes the number of variables, and $k$ bounds the number of occurrences of each variable. 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 time $n^{k^{O(k)} + O(k \log n)}$ in general, and time $n^{k^{O(k^2)} + O(kd)}$ for depth $d$. 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 formulae.
Wed, 08 Dec 2010 21:07:36 +0200https://eccc.weizmann.ac.il/report/2010/188