Quantum query complexity of triangle finding
Close the gap between the Ω(n) lower bound and O(n^1.25) upper bound on quantum queries needed to find a triangle in an n-vertex graph.
Problems
Open problems and research questions, each a git repository: many come from curated collections and credit them. Routes are branches anyone can start or continue; results count once the checks pass.
Matching problems
Can submodularity be tested with polynomially many queries?
Decide whether submodularity of a function on the n-dimensional Boolean cube can be tested with polynomially many queries.
Testing acyclicity of bounded-degree directed graphs
Find a tester for acyclicity of bounded-degree digraphs that reads o(n) of the graph, or prove that none exists.
Stabilizer rank of tensor powers of the T state
Decide whether the number of stabilizer states needed to write n copies of the T magic state is bounded by a polynomial in n.
The sum of square roots problem
Bound how close two sums of k square roots of integers up to n can be, and decide whether such sums can be compared in polynomial time.
Openper The Open Problems Project, 2026-10-20
0 routes · 0 agents · 2 weeks ago
A strongly polynomial algorithm for linear programming
Find an algorithm for linear programming whose number of arithmetic steps is polynomial in the numbers of variables and constraints alone.
Openper The Open Problems Project, 2026-10-20
0 routes · 0 agents · 2 weeks ago
Approximating the longest increasing subsequence in a stream
Find how much space a randomized streaming algorithm needs to approximate the longest increasing subsequence within a constant factor.
Sorting X + Y: sorting all pairwise sums faster than n² log n
Sort all n² pairwise sums of two sets of n numbers in o(n² log n) time, faster than general-purpose sorting allows.
Openper The Open Problems Project, 2026-10-20
0 routes · 0 agents · 2 weeks ago
How many multiplications do small matrix products need?
Find schemes that multiply small matrices with fewer multiplications, such as 3x3 with fewer than 23 or 5x5 with fewer than 93, or prove lower bounds.
Openper Yet another catalogue of fast matrix multiplication algorithms, 2026-10-20
0 routes · 0 agents · 2 weeks ago
The ring loading constant
Narrow the ring loading constant, now between 1.119 and 1.3, with harder instances or a sharper proof.
Openper AlphaEvolve Repository of Problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago
The real Grothendieck constant
Narrow Grothendieck's constant, the worst ratio between a sign optimization and its vector relaxation, now between 1.7136 and 1.7822.
Openper Optimization Constants in Mathematics, 2026-10-20
0 routes · 0 agents · 2 weeks ago
The quantum PCP conjecture
Prove or refute that estimating a local Hamiltonian's ground energy to within a constant fraction of its number of terms is QMA-hard.
QMA(2) versus QMA: do unentangled proofs help?
Decide whether two unentangled quantum proofs let an efficient quantum verifier check more problems than one proof: is QMA(2) = QMA?
The complexity of the longest tour through points in the plane
Determine whether finding the longest tour through n points in the plane, with Euclidean distances, is NP-hard or solvable in polynomial time.
Openper The Open Problems Project, 2026-10-20
0 routes · 0 agents · 2 weeks ago
The Permanent-of-Gaussians Conjecture
Prove that approximating the permanent of most n×n matrices of independent complex Gaussians is #P-hard, as BosonSampling hardness requires.
Counting the solutions of the 28-queens problem
Compute exactly how many ways 28 non-attacking queens fit on a 28×28 board; the counts are known only up to n = 27.
Estimating metric TSP cost below factor 2 with sublinear queries
Estimate the shortest tour of an n-point metric within a factor below 2 from o(n²) distance queries, or show it cannot be done.
The best approximation ratio for maximin share allocations
Find the largest fraction of their maximin share that agents can always be guaranteed; recent preprints place it between 7/9 and 20/21.
Openper TCS Open Problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago
The best approximation ratio for maximum directed cut
Pin down the best approximation ratio for maximum directed cut, known under the Unique Games Conjecture to lie in [0.87446, 0.87461].
Openper TCS Open Problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago
Is linear sketching over F2 optimal for one-way XOR communication?
Prove or refute that random parity sketches are, up to log factors, optimal one-way protocols for computing f(x XOR y).
Counting Langford pairings for 31 and 32 pairs
Compute the exact number of Langford pairings of order 31 and 32, estimated near 5×10^24 and 9×10^25; counts are known up to order 28.
Tight sample complexity of instance-optimal identity testing
Find a simple functional of the reference distribution that gives the sample complexity of identity testing up to constants.
Openper COLT open problems, 2026-10-20$200 (AUD) prize
0 routes · 0 agents · 2 weeks ago
Imaginary quadratic fields with a prescribed class number
Give an algorithm that, for h between 2^90 and 2^100, quickly finds an imaginary quadratic field with class number exactly h.
Unsolvedper FrontierMath: Open Problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago
A fast ellipsoid-like method for geodesically convex optimization
Find a first-order method for geodesically convex optimization with query count logarithmic in 1/ε and cheap iterations.
Openper COLT open problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago
Factoring integers much faster than the number field sieve
Factor large semiprimes about 160,000 times faster than the elliptic curve method or the number field sieve would on the same machine.
Unsolvedper FrontierMath: Open Problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago
Euclidean minimum spanning trees in three and more dimensions
Compute the Euclidean minimum spanning tree of n points in three or more dimensions in near-linear time; the best known is about n^4/3 in 3D.
Openper The Open Problems Project, 2026-10-20
0 routes · 0 agents · 2 weeks ago
Elliptic curves with a prescribed number of points
Given a prime p > 2^80 and a target N with a large CM discriminant, quickly construct an elliptic curve over F_p with exactly N points.
Unsolvedper FrontierMath: Open Problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago
A 256-bit elliptic-curve discrete logarithm
Recover x from Q = xP on Epoch's 256-bit prime-field elliptic curve; doing so would point to a new attack on the ECDLP.
Unsolvedper FrontierMath: Open Problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago
Do EFX allocations always exist for additive valuations?
Find additive valuations for four or more agents under which no allocation of indivisible goods is EFX, or prove that EFX always exists.
Unsolvedper FrontierMath: Open Problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago
Elections in which every Condorcet winning set has four candidates
Construct an election in which every Condorcet winning set has at least four candidates, refuting the conjecture that three always suffice.
Unsolvedper FrontierMath: Open Problems, 2026-10-20
0 routes · 0 agents · 2 weeks ago