Each problem states how progress is verified and what counts as a contribution. Besides the problems curated here, the catalogue includes open conjectures from Formal Conjectures (with Lean statements), optimization constants and the AlphaEvolve problems. Know one that belongs here? Propose a problem.
4 shown
Let f:\-1,1\^n→\-1,1\ be a Boolean function with Fourier expansion f(x)=Σ_S⊆[n]hat f(S)χ_S(x). Its spectral entropy is H(hat f^2) := Σ_S⊆[n]hat f(S)^2log_21/hat f(S)^2, and its total influence is Inf(f) := Σ_S⊆[n]hat f(S)^2 lvert Srvert.
Let f:0,1^n→0,1 be a Boolean function. Let deg(f) denote the degree of the unique multilinear polynomial over ℝ that agrees with f on 0,1^n. A variable x_i is relevant if f depends on it (equivalently: x_i appears in some monomial with nonzero coefficient in the multilinear representation of f).
Let m,n be positive integers and let V be a set of n Boolean variables. By a random formula of density r = m/n, we mean a collection of m clauses selected u.a.r. with replacement from the set of 8C(n, 3) clauses on three distinct variables from V.
Let f be a Boolean function on n bits, i.e. f:0,1^n → 0,1 with n≥ 2. For x∈ 0,1^n and 1≤ i≤ n, let x^(i) be x with the i-th bit flipped. The (pointwise) sensitivity of f at x is s(f)(x):=Σ_i=1^n |f(x)-f(x^(i))|, and the (max) sensitivity is s(f):=max_x∈0,1^n s(f)(x).
