کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331046 | 686440 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
VNP=VP in the multilinear world
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: VNP=VP in the multilinear world VNP=VP in the multilinear world](/preview/png/10331046.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 2, February 2016, Pages 179-182
Journal: Information Processing Letters - Volume 116, Issue 2, February 2016, Pages 179-182
نویسندگان
Meena Mahajan, Nitin Saurabh, Sébastien Tavenas,