Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR19-085 | 13th January 2020 23:16

#### Approximate Degree-Weight and Indistinguishability

Revision #2
Authors: Xuangui Huang, Emanuele Viola
Accepted on: 13th January 2020 23:16
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.
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.

Changes to previous version:

Many small changes, also to introduction. We include proofs of
some known approximate degree lower bounds in the language of indistinguishability.

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

#### Approximate Degree-Weight and Indistinguishability

Revision #1
Authors: Xuangui Huang, Emanuele Viola
Accepted on: 19th June 2019 22:52
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
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