2019/06/02 by Bogdanov, Andrej, Mande, Nikhil S., Thaler, Justin +1 · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1906.00326
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 K3/2 ⋅ exp(-Ω(k2/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 K3/2 exp(-Ω(deg1/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(Ω(deg1/3(f)2/d)), which we also show to be tight for any d > deg1/3(f). These upper and lower bounds were also previously only known in the case f= AND.