ECCC-Report TR19-085https://eccc.weizmann.ac.il/report/2019/085Comments and Revisions published for TR19-085en-usMon, 13 Jan 2020 23:16:43 +0200
Revision 2
| Approximate Degree-Weight and Indistinguishability |
Xuangui Huang,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2019/085#revision2We 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.
Mon, 13 Jan 2020 23:16:43 +0200https://eccc.weizmann.ac.il/report/2019/085#revision2
Revision 1
| Approximate Degree-Weight and Indistinguishability |
Emanuele Viola,
Xuangui Huang
https://eccc.weizmann.ac.il/report/2019/085#revision1We 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$.Wed, 19 Jun 2019 22:52:49 +0300https://eccc.weizmann.ac.il/report/2019/085#revision1
Paper TR19-085
| Approximate Degree-Weight and Indistinguishability |
Emanuele Viola,
Xuangui Huang
https://eccc.weizmann.ac.il/report/2019/085We 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$.
Fri, 07 Jun 2019 02:40:41 +0300https://eccc.weizmann.ac.il/report/2019/085