We prove that the OR function on n bits can be point-wise approximated with error by a polynomial of degree O ( k ) and weight 2 O n \logeps k , for any k n log 1 . This result is tight for k = ( 1 − (1)) n . Previous results were either not tight or had = (1) . In general we obtain a tight approximation result for any symmetric function. Building on this we also obtain an approximation result for bounded-width CNF. For these two classes no such result was known.

One motivation for such results comes from the study of indistinguishability. Two distributions P , Q over n -bit strings are ( k ) -indistinguishable if their projections on any k bits have statistical distance at most . The above approximations give values of ( k ) that suffice to fool OR, symmetric functions and bounded-width CNF, and the first result is tight for all k while the second result is tight for k = ( 1 − (1)) n . Finally, we show that any two ( k ) -indistinguishable distributions are O ( n ) k 2 -close to two distributions that are ( k 0 ) -indistinguishable, improving the previous bound of O ( n ) k .