Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950574 | Information and Computation | 2017 | 10 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Suryajith Chillara, Partha Mukhopadhyay,