Mahajan, Meena ; Saurabh, Nitin ; Tavenas, Sébastien (2016) VNP=VP in the multilinear world Information Processing Letters, 116 (2). pp. 179-182. ISSN 0020-0190
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.ipl.2015.08.004
Related URL: http://dx.doi.org/10.1016/j.ipl.2015.08.004
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier B.V. |
| Keywords: | Algebraic complexity; Branching programs; Circuits; Computational complexity; Multilinearity |
| ID Code: | 128045 |
| Deposited On: | 14 Oct 2022 11:25 |
| Last Modified: | 14 Oct 2022 11:25 |
Repository Staff Only: item control page
