Revision #2 Authors: Xuangui Huang, Emanuele Viola

Accepted on: 13th January 2020 23:16

Downloads: 476

Keywords:

We prove that the Or function on $n$ bits can be point-wise approximated with error $\eps$ by a polynomial of degree $O(k)$ and weight $2^{O(n \log (1/\eps)/k)}$, for any $k \geq \sqrt{n \log 1/\eps}$. This result is tight for all $k$. Previous results were either not tight or had $\eps = \Omega(1)$. In general we obtain an approximation result for any symmetric function, also tight. Building on this we also obtain an approximation result for bounded-width CNF. For these two classes no such result was known.

One motivation for such results comes from the study of indistinguishability.

Two distributions $P$, $Q$ over $n$-bit strings are $(k,\delta)$-indistinguishable if their projections on any $k$ bits have statistical distance at most $\delta$.

The above approximations give values of $(k,\delta)$ that suffice to fool symmetric functions and bounded-width CNF, and the first result is tight.

We also show that any two $(k, \delta)$-indistinguishable distributions are $O(n)^{k/2}\delta$-close to two distributions that are $(k,0)$-indistinguishable, improving the previous bound of $O(n)^k \delta$. Finally we present proofs of

some known approximate degree lower bounds in the language of indistinguishability, which

we find more intuitive.

Many small changes, also to introduction. We include proofs of

some known approximate degree lower bounds in the language of indistinguishability.

Revision #1 Authors: Xuangui Huang, Emanuele Viola

Accepted on: 19th June 2019 22:52

Downloads: 637

Keywords:

We prove that the OR function on $n$ bits can be point-wise approximated with error $\epsilon$ by a polynomial of degree $O(k)$ and weight $2^{O{n \logeps /k}}$, for any $k \geq \sqrt{n \log 1/\epsilon}$. This result is tight for $k = (1-\Omega(1))n$. Previous results were either not tight or had $\epsilon = \Omega(1)$. In general we obtain a tight approximation result for any symmetric function. Building on this we also obtain an approximation result for bounded-width CNF. For these two classes no such result was known.

One motivation for such results comes from the study of indistinguishability.

Two distributions $P$, $Q$ over $n$-bit strings are $(k,\delta)$-indistinguishable if their projections on any $k$ bits have statistical distance at most $\delta$.

The above approximations give values of $(k,\delta)$ that suffice to fool OR, symmetric functions and bounded-width CNF, and the first result is tight for all $k$ while the second result is tight for $k = (1-\Omega(1))n$.

Finally, we show that any two $(k, \delta)$-indistinguishable distributions are $O(n)^{k/2}\delta$-close to two distributions that are $(k,0)$-indistinguishable, improving the previous bound of $O(n)^k \delta$.

TR19-085 Authors: Xuangui Huang, Emanuele Viola

Publication: 7th June 2019 02:40

Downloads: 694

Keywords:

We prove that the Or function on $n$ bits can be point-wise approximated with error $\eps$ by a polynomial of degree $O(k)$ and weight $2^{O(n \log (1/\eps)/k)}$, for any $k \geq \sqrt{n \log 1/\eps}$. This result is tight for all $k$. Previous results were either not tight or had $\eps = \Omega(1)$. In general we obtain an approximation result for any symmetric function, also tight. Building on this we also obtain an approximation result for bounded-width CNF. For these two classes no such result was known.

One motivation for such results comes from the study of indistinguishability.

Two distributions $P$, $Q$ over $n$-bit strings are $(k,\delta)$-indistinguishable if their projections on any $k$ bits have statistical distance at most $\delta$.

The above approximations give values of $(k,\delta)$ that suffice to fool symmetric functions and bounded-width CNF, and the first result is tight.

Finally, we show that any two $(k, \delta)$-indistinguishable distributions are $O(n)^{k/2}\delta$-close to two distributions that are $(k,0)$-indistinguishable, improving the previous bound of $O(n)^k \delta$.