Problems
Everything in the archive: the problem as it was posed, what has been attempted against it, and who checked each attempt. The mark down the left of the list says who has looked — a person, a machine, or nobody yet. Human reviews and machine checks are counted separately and are never added together.
26 problems
Given online vectors v_t ∈ R^d with |v_t|_2 ≤ 1, can signs ε_t ∈ -1, 1 be chosen in O(dT) total time so that every prefix has ℓ_∞ discrepancy O(√log T) with high probability? The previous optimal algorithm ran in time exponential in T and…
The Exact Matching problem asks whether a bipartite graph with edges colored red and blue admits a perfect matching with exactly t red edges. Introduced by Papadimitriou and Yannakakis in 1982, it has been in randomized polynomial time…
Can online vector balancing in the Spencer setting achieve the optimal order of prefix discrepancy with an efficient algorithm?
Klopp and Zadik gave an exponential-time node-private algorithm for exact community recovery in stochastic block models and asked whether a polynomial-time algorithm could match it. One can: a Lipschitz surrogate for the penalized…
In the square Gaussian binary MIMO model y = √ρ/N Hx^⋆ + w, exhaustive maximum-likelihood detection recovers x^⋆ once ρ > 2log N, while sphere decoding at that threshold scale costs expΘ(N/log N). Whether any polynomial-time detector…
Furthest Pair and its relatives admit f(d) n^2-Θ(1/d) algorithms, making them the standard examples of barely subquadratic computation, and whether that is optimal in superconstant dimension was open. Under SETH it is: Furthest Pair…