20 problems

Ben-Or–Linial conjecture. Any Boolean function $f:\{0,1\}^n\to\{0,1\}$ with $\mathbb{E}(f)=1/2$ satisfies

Let $p\text{-optimality}$ mean that a monotone Boolean function $f$ satisfies … For a set $J$ of coordinates, let $f_{J\to1}$ denote the function obtained by setting the coordinate…

Let $f:[0,1]^n\to\\{0,1\\}$ be a Boolean function, and let ${\tilde I}_f$ denote its total variational influence. Strong Friedgut conjecture. There exists a function…

Let $f:\\{0,1\\}^n\to\\{0,1\\}$ be a Boolean function, and let $\mu_p(f)$ denote the probability that $f(G(n,p))=1$ when $f$ is viewed as a graph property. Friedgut's conjecture. T…

Let $f:X^n\to\\{0,1\\}$ be a Boolean function on a product probability space, and let $I_f$ be the sum of its variable influences. Dinur–Friedgut's conjecture. The Friedgut approxi…

Let $f:[0,1]^n\to\\{0,1\\}$ be a Boolean function, and let $I_f$ denote the sum of its variable influences. A function $g:[0,1]^n\to\\{0,1\\}$ depends on a set of variables if its…

Let $f:(\{0,1\}^n,\mu_{1/2}^n)\to\{\pm1\}$ be Boolean-valued, with spectral entropy … and total influence ${\rm I}^{(1/2)}[f]=\sum_{i=1}^n{\rm Inf}_i^{(1/2)}[f]$. Friedgut–Kalai's…

For a Boolean function $F:\{-1,1\}^{n}\to\{-1,1\}$, define its $i$-th influence by … Its total influence is $\operatorname{Inf}(F)=\sum_{i=1}^{n}\operatorname{Inf}_{i}(F)$. For a p…

Directed KKL inequality. Given a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$, there exists $i\in[n]$ such that

Talagrand's conjecture. The inequality above holds with $\alpha=1/2$. This strengthening is intended to provide a single isoperimetric inequality capturing both Talagrand's result…

Let $K \subseteq \mathbb{R}^n$ be symmetric and convex, and let $v \in \mathbb{S}^{n-1}$ satisfy $\operatorname{Inf}_v[K] \leq \varepsilon$. A symmetric convex set $L$ can be compa…

Let $K \subseteq \mathbb{R}^n$ be a convex symmetric set with total convex influence $\operatorname{Inf}[K] \leq I$. For an accuracy parameter $\varepsilon>0$, consider orthonormal…

Let $K$ be a symmetric convex set and suppose that the convex influence $\Inf_v[K]$ in every direction $v \in \mathbb{S}^{n-1}$ is at most $\delta$, with…

Let $f$ be a Boolean function on the discrete cube, let $h_f(y)=\#\{i\in[n]\mid f(y)\neq f(y^{\oplus i})\}$ be its sensitivity at $y$, let $\operatorname{Var}(f)$ denote its varian…

Let $f_t$ be the halfspace appearing in the paper, and let $\mathrm{VB}_1(f_t)$ and $I_1(f_t)$ denote the corresponding boundary quantity and first-coordinate influence. The paper…

Let $f(x)=\mathbbm{1}\left(\sum_i a_i x_i>t\right)$ be a halfspace, with the weight vector normalized by $\sum_i a_i^2=1$. Let $I_k(f)$ denote the influence of coordinate $k$, and…

Aaronson–Ambainis conjecture. Every such function satisfies

Talagrand constant-two conjecture. The influences satisfy

Friedgut's conjecture. Friedgut's theorem should hold without requiring any symmetry assumptions.

Dinur–Friedgut conjecture. There exists a constant $c>0$ such that there is a set $J\subset\{1,2,\ldots,n\}$ with $|J|\leq\exp(cB/\epsilon)$ and a function…