Revision #1 Authors: Xuangui Huang, Emanuele Viola

Accepted on: 19th June 2019 22:52

Downloads: 85

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: 172

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$.