98 problems

For every integer $n\ge 1$, every Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$, and every noise parameter $\rho\in[0,1]$, let $X$ be uniformly distributed on $\{-1,1\}^n$, let…

Let $f$ be a finite sum of quadratic monomial rotation-symmetric Boolean functions, and let $W_f(n)$ denote the Hamming weight of its induced Boolean function on $n$ variables. Let…

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…

Anthony–Brightwell–Shawe-Taylor conjecture. If $f$ has specification number $n+1$, then $f$ is nested:

Bollobás–Brightwell–Leader conjecture. The number of $k$-SAT functions on $n$ boolean variables is

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

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\\}$,

Friedgut–Kalai Fourier entropy-influence conjecture. There exists a universal constant $c$ such that, for every such $f$,

Nisan–Szegedy's sensitivity conjecture. There exists an absolute constant $C>0$ such that, for every Boolean function $f$,

Optimal-predictor acyclicity conjecture. The graph $\mathcal{G}_{\rho,n}$ contains no cycles.

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 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…