ECCC-Report TR19-082https://eccc.weizmann.ac.il/report/2019/082Comments and Revisions published for TR19-082en-usSun, 02 Jun 2019 07:15:39 +0300
Paper TR19-082
| Approximate degree, secret sharing, and concentration phenomena |
Andrej Bogdanov,
Nikhil Mande,
Justin Thaler,
Christopher Williamson
https://eccc.weizmann.ac.il/report/2019/082The $\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.
Sun, 02 Jun 2019 07:15:39 +0300https://eccc.weizmann.ac.il/report/2019/082