Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-085 | 19th June 2019 22:52

Approximate Degree-Weight and Indistinguishability

RSS-Feed




Revision #1
Authors: Xuangui Huang, Emanuele Viola
Accepted on: 19th June 2019 22:52
Downloads: 21
Keywords: 


Abstract:

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


Paper:

TR19-085 | 7th June 2019 02:40

Approximate Degree-Weight and Indistinguishability





TR19-085
Authors: Xuangui Huang, Emanuele Viola
Publication: 7th June 2019 02:40
Downloads: 110
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint