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.
28 problems
How well can an arbitrary boolean constraint satisfaction problem of arity k be approximated in polynomial time? The paper gives a (k/2^k)-approximation, improving the previous best constant of 0.626612 k/2^k due to Makarychev and…
Monteiro and Svaiter gave a second-order method for smooth monotone variational inequalities converging at O(T^-1.5), later improved to O(T^-1.75) for the convex-concave minimax subset. Whether the conjectured complexity for general…
The paper nearly settles the tradeoff between the size of a set system over [n] and its number of full chains, an extremal question raised by Johnson, Leader and Russell as a counterpart to Sperner-type results, and linked by recent work…
Nesterov's accelerated gradient method (1983) is a cornerstone of optimization, yet whether its iterates themselves converge to a minimizer, rather than just the function values, stayed open for over forty years. Jang and Ryu resolve it in…
Yun, Sra and Jadbabaie posed as a COLT 2021 open question whether, for well-conditioned symmetric matrices, the operators encoding the expected iterate of single-shuffle SGD, random-reshuffle SGD and gradient descent on a quadratic finite…
Prim-Dijkstra routing interpolates between a minimum spanning tree and a shortest-path tree, and has been used and improved in VLSI physical design since the early 1990s, but the complexity of the terminal-only Manhattan decision problem…
On the basis of experiments up to 5000 nodes, Papamanthou and Tollis conjectured a relation between the longest paths produced by their MaxSTN and MinSTN algorithms for st-orientations of biconnected graphs. A counterexample refutes it.
Does two-terminal reliability, the probability that s still reaches t when edges fail independently, admit a fully polynomial-time randomised approximation scheme? Asked explicitly in Kannan's 1994 survey and left open while the…