Name
Title | ||
|---|---|---|
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in |
Abstract | ||
|---|---|---|
We give the first sub-exponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 circuits with a plus gate at the top (also known as ΣΠΣΠ circuits) and has a running time of exp(poly(log(n),log(s),k)) where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. In particular, when the circuit is of polynomial (or quasi-polynomial) size, our algorithm runs in quasi-polynomial time. In [AV08], it was shown that derandomizing polynomial identity testing for general ΣΠΣΠ circuits implies a derandomization of polynomial identity testing in general arithmetic circuits. Prior to this work sub-exponential time deterministic algorithms were known for depth-$3$ circuits with small top fan-in and for very restricted versions of depth-4 circuits. The main ingredient in our proof is a new structural theorem for multilinear ΣΠΣΠ(k) circuits. Roughly, this theorem shows that any nonzero multilinear ΣΠΣΠ(k) circuit contains an `embedded' nonzero multilinear ΣΠΣ(k) circuit. Using ideas from previous works on identity testing of sums of read-once formulas and of depth-3 multilinear circuits, we are able to exploit this structure and obtain an identity testing algorithm for multilinear ΣΠΣΠ(k) circuits. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/1806689.1806778 | SIAM Journal on Computing |
Keywords | Field | DocType |
nonzero multilinear,deterministic identity testing,depth-4 multilinear circuit,depth-3 multilinear circuit,small top fan-in,algorithm work,depth-4 circuit,bounded top fan-in,general arithmetic circuit,polynomial identity testing,identity testing algorithm,identity testing,polynomial time | Arithmetic circuits,Polynomial identity testing,Discrete mathematics,Combinatorics,Polynomial,Fan-in,Identity testing,Electronic circuit,Multilinear map,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
42 | 6 | 0097-5397 |
Citations | PageRank | References |
17 | 0.63 | 25 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zohar S. Karnin | 1 | 266 | 20.98 |
| Partha Mukhopadhyay | 2 | 91 | 12.71 |
| Amir Shpilka | 3 | 1095 | 64.27 |
| Ilya Volkovich | 4 | 145 | 8.64 |