Name
Abstract | ||
|---|---|---|
In this note, we show that over fields of any characteristic, exponential sums of Boolean instantiations of polynomials computed by multilinear circuits can be computed by multilinear circuits with polynomial blow-up in size. In particular, multilinear-VNP equals multilinear-VP. Our result showing closure under exponential sums also holds for other restricted multilinear classes – polynomials computed by multilinear (bounded-width) algebraic branching programs and formulas. Furthermore, it holds even if the circuit class is not fully multilinear but computes a polynomial that is multilinear in the summation variables. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.ipl.2015.08.004 | Information Processing Letters |
Keywords | Field | DocType |
Computational complexity,Algebraic complexity,Circuits,Branching programs,Multilinearity | Discrete mathematics,Combinatorics,Algebraic number,Exponential function,Polynomial,Polarization of an algebraic form,Algebraic complexity,Multilinear map,Mathematics,Computational complexity theory,Branching (version control) | Journal |
Volume | Issue | ISSN |
116 | 2 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| Nitin Saurabh | 2 | 5 | 3.81 |
| Sébastien Tavenas | 3 | 14 | 5.19 |