On polynomial approximations to AC0. Issue 2 (12th July 2018)

• Record Type: Journal Article
• Authors: Harsha, Prahladh; Srinivasan, Srikanth
• Is Part Of: Random structures & algorithms. Volume 54:Issue 2(2019)
• Page Start: 289
• Page End: 303
• Publication Date: 2018-07-12
• Subjects: anti‐concentration for polynomials -- bounded independence -- constant‐depth circuits -- probabilistic polynomials; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20786
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Classical AC 0 approximation results show that any AC 0 circuit of size s and depth d has an ɛ ‐error probabilistic polynomial over the reals of degree ( log ( s / ɛ ) ) O ( d ) . We improve this upper bound to ( log s ) O ( d ) · log ( 1 / ɛ ), which is much better for small values of ɛ . We then use this result to show that ( log s ) O ( d ) · log ( 1 / ɛ ) ‐wise independence fools AC 0 circuits of size s and depth d up to error at most ɛ, improving on Tal's strengthening of Braverman's result that ( log ( s / ɛ ) ) O ( d ) ‐wise independence suffices. To our knowledge, this is the first PRG construction for AC 0 that achieves optimal dependence on the error ɛ . We also prove lower bounds on the best polynomial approximations to AC 0 . We show that any polynomial approximating the OR function on n bits to a small constant error must have degree at least Ω ∼ ( log n ) . This result improves exponentially on a result of Meka, Nguyen, and Vu ( Theory Comput . 2016).