Header menu link for other important links
X
VNP=VP in the multilinear world
M. Mahajan, , S. Tavenas
Published in Elsevier
2016
Volume: 116
   
Issue: 2
Pages: 179 - 182
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. © 2015 Elsevier B.V.
About the journal
JournalData powered by TypesetInformation Processing Letters
PublisherData powered by TypesetElsevier
ISSN00200190