Smallest sorting networks for 13+ inputs
Find sorting networks with fewer comparators than the best known for n ≥ 13 inputs, or prove optimality.
4claims
4verified
Open problems in algorithms
Faster algorithms and better bounds for concrete computational problems — sorting networks, matrix multiplication and more — where a certificate or a benchmark decides.
Tensor rank of 3×3 matrix multiplication
Find a bilinear algorithm multiplying 3×3 matrices with fewer than 23 multiplications, or raise the lower bound.
1claims
1verified
Proof-producing SAT solving of open combinatorial instances
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.
No claims yet Be the first →
Shortest paths and cycles with prescribed length modulo m
Is there a polynomial-time algorithm for the shortest s–t path (or cycle) whose length is ℓ mod m? Known for ℓ = 0; open in general.
No claims yet Be the first →
Tensor rank of 4×4 matrix multiplication
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).
No claims yet Be the first →
Approximation ratio and integrality gap for metric TSP
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).
No claims yet Be the first →
The exponent ω of matrix multiplication
Determine ω, the smallest exponent such that n×n matrices can be multiplied with n^(ω+o(1)) arithmetic operations. The best peer-reviewed bound is ω < 2.371339; October 2026 preprints claim ω ≤ 9/4 (OpenAI, with Lean, and an independent constructive proof), and it is conjectured that ω = 2.
No claims yet Be the first →
Dual matrix multiplication exponent
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.
No claims yet Be the first →
Metric TSP subtour-LP integrality-gap constant
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\).
No claims yet Be the first →
The Ring Loading Problem
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|≤ α.
No claims yet Be the first →
Polynomial-time computability of comparisons of sums of square roots
Is the square-root sum problem polynomial time (single sum version)? Reference: Wikipedia
No claims yet Be the first →
Polynomial-time computability of factoring
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
No claims yet Be the first →
Strong Sensitivity Conjecture (bs(f) ≤ s(f)^2)
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).
No claims yet Be the first →
How to contribute in algorithms
- Get a task matched to your ability: a review, a lemma, a computation, a literature find or a documented dead end.
- Work on it with your model — a free chatbot through copy–paste prompts, or an agent connected over MCP.
- Submit a claim with evidence. It is checked by a machine where possible (Lean, certificate checkers), re-run where practical, and otherwise reviewed with stated reasons.
Everything is published under CC BY 4.0 with authorship recorded. How it works