218 problems

Let $X$ be uniformly distributed on the Boolean hypercube $\\{-1,1\\}^n$, and let $Y$ be obtained by transmitting $X$ through a memoryless binary symmetric channel with crossover p…

Log-rank conjecture. For any Boolean function $f$, $\operatorname{cc}(f)$ is bounded above by a polynomial in $\log r$.

Let $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$ be a Boolean function. Its Fourier entropy is the Shannon entropy of its power spectrum $\{\hat{f}(S)^2:S\subseteq\{1,\ldots,n\}\}$, and its…

A Boolean function is a map $f:[?{0,1}^n\rightarrow\{0,1\}$. Its sensitivity is the maximum, over inputs, of the number of coordinates whose change alters the function value; its d…

A Boolean $k$-SAT function on $n$ variables is a function represented by a $k$-SAT formula, and it is unate if it admits a formula in which each variable appears only positively or…

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

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

Let $t(n,k)$ denote the rectangle crossing time, and let $(k_n)_{n\ge1}$ be a sequence with $k_n\to\infty$. Being above the median of $t(n,k_n)$ means the corresponding indicator p…

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

Let $X$ be uniformly distributed on $\{0,1\}^n$, let $Y$ be obtained from $X$ through a memoryless binary symmetric channel with crossover probability $0<p<\frac{1}{2}$, and let…

A Boolean function is a function $f:\{0,1\}^n\to\{0,1\}$. Its decision-tree complexity $D(f)$ is the minimum number of input bits an adaptive algorithm must query to determine $f$,…

Let $\boldsymbol{e}_{n,k}$ denote the elementary symmetric Boolean function of degree $k$ in $n$ variables. A Boolean function is balanced when it takes each value equally often, a…

Let $\rho_q(n)$ be the maximum nonlinearity of a function from $\mathbb{F}_q^n$ to $\mathbb{F}_q$, and define … In particular, $mu_2(n)$ denotes this quantity for Boolean functions…

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a transitive-symmetric function, meaning that for every $1\leq i<j\leq n$ there is a permutation $\sigma$ of $[n]$ with $\sigma(i)=j$ such that…

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…

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

Fix a constant $c>0$, and let $k=k(n)$ vary with $n$. Bollobás–Brightwell's enumeration conjecture. As long as … the number of $k$-SAT functions on $n$ variables is … This concerns…

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_n)_{n\geq 1}$ be Boolean functions on $\\{0,1\\}^n$, and let $(X^{(n)})_{n\geq 1}$ be continuous-time $p_n$-biased random walks, with $C_n$ denoting the number of value cha…

Let $F:{\mathbb F}_{2^n}\to{\mathbb F}_{2^n}$ be a function, and let its nonlinearity be … where $\mathcal W_F(a,b)$ is the Walsh transform of $F$. Even-dimensional nonlinearity bo…

Zhang–Zheng's conjecture. The absolute indicator of $f$ is at least

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 $f$ be a threshold Boolean function depending on $n$ variables, and let its specification number be the minimum number of Boolean points that uniquely determine $f$ within the…

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