Random Structures & Algorithms

On polynomial approximations to AC 0

Early View


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).

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.