Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-082 | 2nd June 2019 05:58

Approximate degree, secret sharing, and concentration phenomena


Authors: Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson
Publication: 2nd June 2019 07:15
Downloads: 947


The $\epsilon$-approximate degree $\widetilde{\text{deg}}_\epsilon(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. 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 - \epsilon$. Our contributions are:

We give a simple new construction of a dual polynomial for the AND function, certifying that $\widetilde{\text{deg}}_\epsilon(f) \geq \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/3$-approximate degree of any read-once DNF is $\Omega(\sqrt{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} \cdot \exp(-\Omega(k^2/K))$ for all $k \leq K \leq 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(-\Omega(\widetilde{\text{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 \leq n/64$, any degree $d$ polynomial approximating a symmetric function $f$ to error $1/3$
must have $\ell_1$-norm at least $K^{-3/2} \exp({\Omega(\widetilde{\text{deg}}_{1/3}(f)^2/d)})$, which we also show to be tight for any $d > \widetilde{\text{deg}}_{1/3}(f)$.
These upper and lower bounds were also previously only known in the case $f=$ AND.

ISSN 1433-8092 | Imprint