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.
13 shown
Explain why some networks generalise long after fitting their training data, and predict when this happens. Reproducible small-model experiments serve as evidence, e.g. modular arithmetic transformers whose circuits can be reverse-engineered.
For each n, find the largest radius r such that n non-overlapping circles of radius r fit in a unit square. Optimality is proven only for small n. For larger n, improve the best known packings or prove new cases optimal.
Settle open finite combinatorial questions with SAT solvers that emit checkable unsatisfiability proofs (DRAT/LRAT). Examples of solved cases are Boolean Pythagorean triples, Schur number five, Keller's conjecture in dimension 7, and the empty hexagon number.
Find configurations of n unit point charges on the sphere that minimise Coulomb energy. Global optimality is proven only for a few n, so the tasks are to lower best known energies and to prove new cases optimal.
In algebraic complexity theory, for each real k ≥ 0, let ω(k) denote the exponent for multiplying an n × n^k matrix by an n^k × n matrix. We define α := supk ≥ 0 : ω(k) = 2.
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 be a convex function with 1-Lipschitz gradient. We assume black-box access to the function and its gradient. Gradient descent will converge to a global minimum with an appropriate choice of _step size_ s: x_k+1 := x_k - s· ∇ f(x_k). In general, s can be chosen to vary with the step k.
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).
In the symmetric metric traveling salesman problem, one is given a complete graph K_n=(V,E) with a nonnegative symmetric cost function c:E→ ℝ_≥ 0 satisfying the triangle inequality. For S⊆ V, let δ(S) denote the set of edges with exactly one endpoint in S, and write δ(v):=δ(\v\).
C_14 is the smallest n, such that the value of the busy beaver number BB(n) is undecidable in ZFC (or equivalently ZF). Explicitly, it is the smallest n such that there is a Turing machine with n states for which it cannot be proven in ZFC (assuming ZFC is consistent) whether it halts or not.
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).
Let C be the infimum of all reals α for which the following statement holds: for all positive integers m and nonnegative reals u_1, …, u_m and v_1, …, v_m with u_i + v_i ≤ 1, there exist z_1, …, z_m such that for every k, we have z_k ∈ v_k, -u_k, and |Σ_i=1^k z_i - Σ_i=k+1^m z_i|≤ α.
