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

LMN theorem shows that if f is a boolean function$(f:\{-1,1\}^n \rightarrow \{-1,1\})$ computable by an $\text{AC}^0$ circuit of size M, $$\sum_{S:|S|> k} \hat f(S)^{2} \leq 2^{-\Omega(k/(\log M)^{... • 193 8 votes 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,011 8 votes ### 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,783 7 votes ### 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 ... 6 votes ### Is a monotone boolean function monotone as a multilinear polynomial? Yes. Let f : \{-1,1\}^n \to \mathbb{R}, and let F : [-1,1]^n \to \mathbb{R} be its multilinear extension. If f is monotone, then so is F. proof: Fix a variable index i; we'll show that \... • 1,419 5 votes Accepted ### Dimension of the Fourier transform for S_5 A quantum Fourier transform is a unitary operation, so the number of basis states of the input and output must be the same. The number of basis states before the Fourier transform is 120, the number ... • 23.8k 5 votes Accepted ### Given a subset of of the hypercube and an affine transform of it, find the affine map From D.W.'s comment, we see that your problem is equivalent to the same problem with s=0 (and with d only increased by 1). The resulting problem is precisely the Linear Code Equivalence Problem ... • 35.9k 5 votes Accepted ### A boolean function f: \{0,1\}^n \rightarrow \{0,1\} is chosen at random from all 2^{2^n} such f. What do the Fourier coefficients look like? Here's one way of attacking the problem. Any boolean function f: [2]^n \rightarrow [2] can be written as f(\alpha) = \sum_{\beta \in [2]^n} \chi_{\beta}\delta_{\beta} (\alpha) \end{... 5 votes Accepted ### Basic property of boolean functions with restrictions This is Corollary 3.22 of Analysis of Boolean Functions, by Ryan O'Donnell (2014). You may want to consult the proof in the book, or look directly at the online version (which has a different ... • 4,361 5 votes Accepted ### Is this "subgroup packing" polytope integral? Andrew(the asker) and I had discussed this over email, and we have shown the conjecture is false. The polytope is not integral for Abelian groups, not even for cyclic groups. On the positive side. ... • 4,276 4 votes Accepted ### Question about discarding the second register in the standard approach of hidden subgroup algorithm Discarding in this context can be carried out by performing a Partial Trace. The system you're interested in is that of the first register. If you want to know only its state, as opposed to the ... 2 votes 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 ... • 235 2 votes ### Which (almost) balanced Boolean function has smallest "total" influence You have the lower bound of \mathbf{Inf}[f] \geq \operatorname{Var}[ f ] for f\colon \{-1,1\}^n\to\mathbb{R} (Poincaré Inequality), so that for an (almost) balanced f\colon \{-1,1\}^n\to\{-1,1\}... • 4,361 2 votes Accepted ### Lower bound on the support size of an \epsilon-biased distribution 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\...
• 4,361
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$, ...