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].
问题
开放问题和研究问题，每个都是一个 git 仓库：很多来自精选合集，并注明出处。路线是任何人都能开启或接续的分支；检验通过后，结果才算数。
符合的问题
Low autocorrelation binary sequences beyond length 66
Find ±1 sequences of length 67 and beyond with lower autocorrelation energy than known, or prove optimality; optima are known only up to 66.
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).
Legendre pairs of length 115 and the other open lengths below 200
Find a Legendre pair of length 115, 145, 159, 161, 169, 175, 177, 185, 187 or 195, the open odd lengths below 200.
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.
The price of joint differential privacy in linear contextual bandits
Close the gap between regret upper and lower bounds for linear contextual bandits under joint differential privacy.
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.
Densest graphs without triangles or 4-cycles on 54 or more vertices
Find a 54-vertex graph with no triangles or 4-cycles and more than 185 edges, or prove 185 is the maximum.
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.
General unfoldings of nonconvex polyhedra
Decide whether every polyhedron can be cut open, with cuts anywhere on its surface, and flattened into one non-overlapping piece.
Is the flip graph of tetrahedralizations in 3D connected?
Decide whether 2–3 and 3–2 flips connect all tetrahedralizations of every point set in general position in three dimensions.
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.
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.
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.
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.
Edge-unfolding polycubes
Show that every polycube can be cut along cube edges and unfolded flat in one non-overlapping piece, or find one that cannot.
Dürer's problem: edge-unfolding convex polyhedra
Prove that every convex polyhedron can be cut along its edges and unfolded flat in one piece without overlap, or find one that cannot.
Selecting n data points whose average is nearly as good as the mean
Find the worst-case loss ratio when the mean of a planar dataset is replaced by the best average of n of its points.
The XL set: vehicle routing with 1,000 to 10,000 customers
Beat the best-known routes on 100 capacitated vehicle routing instances with 1,000 to 10,000 customers, released for the 2026 BKS Challenge.
The 39 open instances of the CVRPLIB X set
Find cheaper routes, or prove optimality, for the 39 X instances of the capacitated vehicle routing problem that are still unsolved.
Counting polyominoes and Klarner's constant
Count the polyominoes with n cells, known exactly up to n = 70, and pin down Klarner's growth constant, now between 4.0025 and 4.5252.
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.
A binary code of length 21 with minimum distance 10
Construct a binary code of length 21 and minimum distance 10 with 43 words, beating the record of 42 that has stood since 1989.
How much overparameterization does ALS need for tensor decomposition?
Prove that alternating least squares decomposes rank-r tensors with o(r^2) components, or that about r^2 are needed.
Truly subquadratic algorithms for 3SUM-hard problems
3SUM now has a truly subquadratic algorithm; find one for a 3SUM-hard geometric problem, such as deciding whether n points have three on a line.