Abstract
The epsilonapproximate degree deg~_epsilon(f) of a Boolean function f is the least degree of a realvalued polynomial that approximates f pointwise to within epsilon. A sound and complete certificate for approximate degree being at least k is a pair of probability distributions, also known as a dual polynomial, that are perfectly kwise indistinguishable, but are distinguishable by f with advantage 1  epsilon. Our contributions are:
 We give a simple, explicit new construction of a dual polynomial for the AND function on n bits, certifying that its epsilonapproximate degree is Omega (sqrt{n log 1/epsilon}). This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1/3approximate degree of any (possibly unbalanced) readonce DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anticoncentration of the Binomial distribution.
 We show that any pair of symmetric distributions on nbit strings that are perfectly kwise indistinguishable are also statistically Kwise indistinguishable with at most K^{3/2} * exp (Omega (k^2/K)) error for all k < K <= n/64. This bound is essentially tight, and implies that any symmetric function f is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against sizeK coalitions with statistical error K^{3/2} * exp (Omega (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 analysis draws another new connection between approximate degree and concentration phenomena.
As a corollary of this result, we show that for any d <= n/64, any degree d polynomial approximating a symmetric function f to error 1/3 must have coefficients of l_1norm at least K^{3/2} * exp ({Omega (deg~_{1/3}(f)^2/d)}). We also show this bound is essentially tight for any d > deg~_{1/3}(f). These upper and lower bounds were also previously only known in the case f=AND.
BibTeX  Entry
@InProceedings{bogdanov_et_al:LIPIcs:2019:11286,
author = {Andrej Bogdanov and Nikhil S. Mande and Justin Thaler and Christopher Williamson},
title = {{Approximate Degree, Secret Sharing, and Concentration Phenomena}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {71:171:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11286},
URN = {urn:nbn:de:0030drops112869},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.71},
annote = {Keywords: approximate degree, dual polynomial, pseudorandomness, polynomial approximation, secret sharing}
}
Keywords: 

approximate degree, dual polynomial, pseudorandomness, polynomial approximation, secret sharing 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) 
Issue Date: 

2019 
Date of publication: 

17.09.2019 