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.
28 shown
Explain why the test loss of neural networks follows power laws in model size, data and compute, and predict the exponents from properties of the data and architecture. Reproducible small-scale experiments serve as evidence.
Prove halting or non-halting of specific small Turing machines that current deciders cannot resolve.
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 sorting networks with fewer comparators than the best known for n ≥ 13 inputs, or prove optimality.
Find a bilinear algorithm multiplying 3×3 matrices with fewer than 23 multiplications, or raise the lower bound.
Find bilinear algorithms that multiply two 4×4 matrices with fewer multiplications. The records are 48 over Q and C (2025) and 47 over GF(2) (2022).
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.
Find better polynomial-time approximation algorithms for the metric Traveling Salesman Problem and prove the conjectured 4/3 integrality gap of the subtour LP. The best known ratio is 3/2 − ε with ε > 10^−36 (Karlin–Klein–Oveis Gharan).
Construct explicit n×n matrices that stay high-rank even after many entry changes, with parameters strong enough for Valiant's circuit lower bounds. Random matrices are highly rigid, but no explicit matrix is known to meet the required parameters.
Prove that every synchronizing complete DFA with n states has a reset word of length at most (n−1)². The best general upper bound is about 0.1654·n³ (Shitov 2019). The conjecture has been verified by computer for small automata.
Determine ω, the smallest exponent such that n×n matrices can be multiplied with n^(ω+o(1)) arithmetic operations. The best published bound is ω < 2.371339, a 2026 preprint claims ω < 2.371177, and it is conjectured that ω = 2.
Is the deterministic communication complexity of every Boolean matrix M bounded by a polynomial in log rank(M)? The best upper bound is O(√rank) (Sudakov–Tomon), and the largest known separation is quadratic in log rank.
Khot's conjecture (2002) that approximating the value of unique games is NP-hard. Its imperfect-completeness 2-to-2 variant was proven in 2018, but the full conjecture remains open.
Decide whether every problem whose solutions can be verified in polynomial time can also be solved in polynomial time (Clay Millennium Prize Problem). A full solution is not expected here; the goal is mapped barriers and verifiable partial results.
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|≤ α.
The integer factorization problem: Can the prime factorization of a positive integer be computed in polynomial time? We state the problem by asking if Nat.primeFactorsList is polynomial-time computable (assuming typical encodings of ℕ and List ℕ into bitstrings). Reference: Wikipedia
Strong Sensitivity Conjecture, for every Boolean function f : 0,1^n → 0,1, bs(f) ≤ s(f)^2. We call this the strong sensitivity conjecture because the original sensitivity conjecture only asked for a polynomial bound in terms of s(f).
