Tag Info

Accepted

Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$?

In his CCC'17 paper [1], Avishay Tal improved the bound to $$\left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1}$$ You may want to check p.15:4 for a discussion. It also refers to (see Footnote ...
• 4,471
Accepted

Is the basis of parity functions the only orthonormal basis for Boolean functions?

I don't think parities are the only orthonormal Boolean basis, for example Paley basis provides a Boolean orthonormal basis in some cases. It's natural to ask if such bases, interpreted as Boolean ...
• 4,031

Average-case analogue of Small-bias Spaces

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$. In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits ...
• 2,803

• 4,471
Accepted

• 2,070
Accepted

Level $k$ bounds in Analysis of Boolean functions

Just posting an answer in order to close the question. See the helpful comments to the question which contain all the info; Yes it is vacuous, but if you use the stronger bound you get something ...
• 245
1 vote

Level $k$ bounds in Analysis of Boolean functions

This statement has been removed from the latest version of the textbook and the referenced problem (9.19) has been updated to prove a weaker result instead.
1 vote

Sparsity of a Boolean function and its Fourier depth

The Fourier transform is a linear operation. In particular, for $f:\{-1,1\}\to\mathbb{R}$ and $S\subseteq[n]$, the Fourier coefficient $\hat f(S)$ is a linear functional of $f$. If $\hat f(S)\neq 0$, ...
• 10.6k

Only top scored, non community-wiki answers of a minimum length are eligible