Skip to main content
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 ...
Clement C.'s user avatar
  • 4,471
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 ...
Mahdi Cheraghchi's user avatar
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 ...
Thomas's user avatar
  • 2,803
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 $\...
Andrew Morgan's user avatar
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{...
Pedro Juan Soto's user avatar
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 ...
Clement C.'s user avatar
  • 4,471
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. ...
Chao Xu's user avatar
  • 4,479
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 ...
Joshua Grochow's user avatar
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\}...
Clement C.'s user avatar
  • 4,471
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\...
Clement C.'s user avatar
  • 4,471
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 ...
kodlu's user avatar
  • 2,070
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 ...
Andy's user avatar
  • 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.
user3919899's user avatar
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$, ...
Aryeh's user avatar
  • 10.6k

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