# 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 , 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 ...
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 ...

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

### Why does Fourier analysis of Boolean functions "work"?

Here might be another take on this question. Assuming the pseudo Boolean function is k-bounded, the Walsh polynomial representation of the function can be decomposed into k subfunctions. All of the ...

You shouldn't have a square root. Namely, for every $\delta$-biased distribution $Z$ (using your notation), we have $$\delta^2+2^{-n} \geq \lVert Z\rVert^2_2 \geq \frac{1}{\lvert\operatorname{supp} Z\... 2 votes ### Fourier decomposition in terms of another basis As pointed out in the comments if u\in \{\pm 1\} then x=x(u) \in \{0,1\} where$$x(u)=\frac{1-u}{2},$$with x(-1)=1, and x(1)=0. This will then yield$$f(x)=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in ...
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$, ...