20 problems

Gotsman–Linial conjecture. The extremal examples among degree-$d$ polynomial threshold functions for total influence are symmetric polynomials whose signs alternate around the midd…

Fourier entropy–influence conjecture. There exists a constant $c>0$ such that, for every $n$ and every Boolean function $f$,

Friedgut–Kalai entropy-influence conjecture. There is an absolute constant $K$ such that, for every $n$ and every Boolean function $f:\{-1,1\}^n\to\{-1,1\}$,

Fourier-Min-Entropy-Influence conjecture. There exists a constant $c>0$ such that, for every Boolean function $f:\\{-1,1\\}^n\to\\{-1,1\\}$,

Fourier-Entropy-Influence conjecture. There exists a constant $c>0$ such that, for every Boolean function $f:\\{-1,1\\}^n\to\\{-1,1\\}$,

Let $f\colon [0,1]^n \to \{0,1\}$ be a measurable function, and let $I_S^b(f)$ denote the corresponding resilience quantity for a set $S\subseteq[n]$ and $b\in\{0,1\}$. Friedgut's…

Let $n$ be a positive integer and let $f:{-1,1}^n\to\{-1,1\}$ be a Boolean function. Write … where $\chi_S(x)=\prod_{i\in S}x_i$ and … with logarithms base $2$. FEI conjecture. The…

Minimum Fourier entropy–influence conjecture. There exists a constant $c>0$ such that, for every $n$ and every Boolean function $f$,

Quantum Fourier entropy-influence conjecture. There is a constant $c$ independent of $n$ such that

Quadratic PTF influence conjecture. When $k=2$, the bound under discussion should still be

Steif–Jonasson conjecture. If $(f_n)_{n\in\mathcal{N}}$ is a non-degenerate sequence of transitive Boolean functions and

Fourier–Min–Entropy Conjecture. The min-entropy of the Fourier spectrum of $f$ is at most $O(I[f])$:

Fourier–Entropy Conjecture. The Shannon entropy of the Fourier spectrum of $f$ is at most $O(I[f])$:

Positive-influence conjecture. One has

Let $f\colon\left\{0,1\right\}^{n}\to\left\{0,1\right\}$ be a Boolean function, write $\mu=\mathbb{E}[f]$, and let $I(f)$ denote its total influence. A function $g$ is a Junta if i…

Let $f\colon\left\{0,1\right\}^{n}\to\left\{0,1\right\}$ be a monotone Boolean function with expectation $\mathbb{E}[f]=\mu$, and let $I[f]$ denote its total influence. A DNF of wi…

Let $f$ be a Boolean function on $\\{0,1\\}^n$, and let $\mu(f)$ denote its probability of taking the value $1$. For $S\subseteq[n]$, write $J_S^+(f)$ for the probability that a un…

Fix $0<p<1$. Let $f:\{-1,1\}^n_p\to\{-1,1\}$ be a Boolean function, let $\operatorname{I}(f)$ denote its total influence, and let $\hat f(S)$ be its Fourier coefficients. Fourier c…

Let $\mu_p$ be the product measure on the discrete cube $\{0,1\}^n$, and let $f:\{0,1\}^n_p\to\{-1,1\}$ be a Boolean function. Write $\operatorname{Ent}_p(f)$ for its spectral entr…

Keller–Pilpel's conjecture. The total influence of $f$ should satisfy