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,361
11 votes

Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

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 ...
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 $\...
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 ...
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 ...
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{...
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
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,016
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.1k

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