کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950574 | 1440713 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the limits of depth reduction at depth 3 over small finite fields
ترجمه فارسی عنوان
در محدوده کاهش عمق در عمق 3 بیش از زمینه های کوچک محدود است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We also give an example of an explicit polynomial (NWn,ϵ(X)) in VNP (which is not known to be in VP), for which any ΣΠΣ circuit computing it (over fixed-size fields) must be of size 2Ω(nlogâ¡n). The polynomial we consider is constructed from the combinatorial design of Nisan and Wigderson, and is closely related to the polynomials considered in many recent papers (by Kayal-Saha-Saptharishi, Kayal-Limaye-Saha-Srinivasan, and Kumar-Saraf), where strong depth 4 circuit size lower bounds are shown.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 256, October 2017, Pages 35-44
Journal: Information and Computation - Volume 256, October 2017, Pages 35-44
نویسندگان
Suryajith Chillara, Partha Mukhopadhyay,