The -approximate degree deg ( f ) of a Boolean function f is the least degree of a real-valued polynomial that approximates f pointwise to error . The approximate degree of f is at least k iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly k -wise indistinguishable, but are distinguishable by f with advantage 1 − . Our contributions are:

We give a simple new construction of a dual polynomial for the AND function, certifying that deg ( f ) ( n log 1 ) . This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1 3 -approximate degree of any read-once DNF is ( n ) .

We show that any pair of symmetric distributions on n -bit strings that are perfectly k -wise indistinguishable are also statistically K -wise indistinguishable with error at most K 3 2 exp ( − ( k 2 K )) for all k K n 64 . This implies that any symmetric function f is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against size- K coalitions with statistical error K 3 2 exp ( − ( deg 1 3 ( f ) 2 K )) for all values of K up to n 64 simultaneously. Previous secret sharing schemes required that K be determined in advance, and only worked for f = AND.

Our analyses draw new connections between approximate degree and concentration phenomena.

As a corollary, we show that for any d n 64 , any degree d polynomial approximating a symmetric function f to error 1 3 must have 1 -norm at least K − 3 2 exp ( ( deg 1 3 ( f ) 2 d ) ) , which we also show to be tight for any \widetilde{\text{deg}}_{1/3}(f)"> d deg 1 3 ( f ) . These upper and lower bounds were also previously only known in the case f = AND.