96 problems

For each integer $n\geq 1$, determine … where … In particular, determine the exact value of $M_{\mathrm{bal}}(8)$; the supplied report claims $M_{\mathrm{bal}}(8)=116$, excluding…

For every integer $k\ge 2$, let $N=2^k-1$. For every integer $t$ with $1\le t\le N-1$, the number of pairs $(a,b)\in\{0,1,\ldots,N-1\}^2$ satisfying $a+b\equiv t\pmod N$ and…

Let $V=\mathbb{F}_q^n$ and let $J_q(n,k)$ be the Grassmann graph whose vertices are the $k$-dimensional subspaces of $V$. A function $f$ on the vertices is Boolean degree $1$ if it…

Let $n$ and $t$ satisfy $0\leq t\leq n-1$, and let ${\cal F}^{n,t}$ be the family of Boolean functions defined by … where $\deg(a)\leq 1$, together with arbitrary Boolean functions…

Optimal-scale conjecture. For each $C>0$ there is an $\varepsilon>0$ such that, for every monotone ${\cal F}$, there exists

Let $0\leq\rho\leq1$ and let $q\geq2$ be an integer. For $f:[q]^n\to[0,1]$, let $\mathbb{S}_\rho(f)$ denote its noise stability and let $\mathrm{Inf}_i(f)$ denote the influence of…

For $d\geq1$, let $C_n$ be the collection of odd, transitive-symmetric functions $f:\{-1,1\}^n\to\{-1,1\}$. Let $\widehat f(S)$ denote Fourier coefficients, and let…

Patterson–Wiedemann conjecture.

Let $n$ be a positive integer, let $\{I,H\}^n$ denote the transform set consisting of $n$ choices between the identity transform $I$ and the Hadamard transform $H$, and let the cli…

Friedgut–Kahn–Kalai–Keller antipodal correlation conjecture. For every increasing $f,g:\{0,1\}^n\to\{0,1\}$, if $g$ is antipodal, then

Friedgut–Kahn–Kalai–Keller spectral correlation conjecture. For any increasing Boolean functions $f,g:\{0,1\}^n\to\{0,1\}$,

Let $q=2^e$ with $e$ an even positive integer, let $u$ be a generator of $\mu_{q+1}$, and for $\alpha\in{\mathbb F}_{q}^*$ define $g_\alpha$ on ${\mathbb F}_{q^2}$ by…

Let $q=2^e$ with $e$ an even positive integer, let ${\bb F}_{q^2}$ be the finite field of order $q^2$, and for each $\alpha\in{\bb F}_{q}^*$ define … where $\sigma(X)=X+X^d+X^{dq}$…

Kalai–Keller–Mossel correlation conjecture. For every increasing and balanced family $\mathcal{A}\subseteq\Omega_n$, there exists an increasing linear-threshold family…

Let $f:(\{0,1\}^n,\mu_p^n)\to\{\pm1\}$ be Boolean-valued and let $0<p<1$. Define … and let $h(q)=-q\log q-(1-q)\log(1-q)$ be the binary entropy function. Binary-entropy lower-bound…

Let $0<p<1$, let $n$ be positive, and let $f:(\{0,1\}^n,\mu_p^n)\to\{\pm1\}$ be Boolean-valued. Write … and ${\rm I}^{(p)}[f]=\sum_{i=1}^n{\rm Inf}_i^{(p)}[f]$. Keller–Mossel–Schla…

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…

Let $n,k,t$ be non-negative integers with $k\leq n$ and $t\leq\min(k,n-k)$. Let $m_1(n,k,t)$ denote the first matching number associated with the paired construction for Boolean fu…

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

Let $m_u,m_w,e_u,e_w\in[0,1]$ satisfy $H_2(m_u)\geq e_u$ and $H_2(m_w)\geq e_w$. Let $\phi$ and $J$ be the functions defined in the paper. The explicit lower-bound conjecture. One…

For $(u,w)\in(0,1)^2$, define … with $\kappa(u,u)=0$. The kappa inequalities. The following two assertions hold: for $u,w\in(0,1/2]$, $\kappa(u,w)\leq\kappa(1-u,w)$; and the functi…

Let $X^n\sim\operatorname{Unif}(\mathbb{H}^n)$, let $Y^n$ be obtained by passing $X^n$ through a binary symmetric channel with crossover probability $p\in[0,1]$, and let…

The candidate function conjecture. The function $\phi$ belongs to the class $\Psi$. If true, this would establish the most-informative Boolean function conjecture for balanced func…

The Hellinger conjecture. Under these assumptions,

Let $\mathbf{X}\sim\operatorname{Unif}(\mathbb{H}^n)$ be uniformly distributed on the Boolean hypercube, and let $\mathbf{Y}$ be obtained by passing each bit of $\mathbf{X}$ throug…