14
votes
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,451
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,803
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,429
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
\begin{equation}
f(\alpha) = \sum_{\beta \in [2]^n} \chi_{\beta}\delta_{\beta} (\alpha)
\end{...
- 234
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 ...
- 36.9k
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,451
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,367
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 ...
- 24.3k
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 ...
- 977
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,451
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,451
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 ...
- 2,070
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.3k
Only top scored, non community-wiki answers of a minimum length are eligible