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.

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

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