12 entries matching the current filters. Sorted by recently added.
Everyone expected additivity. Hastings produced a random counterexample, and the classical capacity of a quantum channel became genuinely hard.
Resolved in 2020 by a complexity-theoretic argument that nobody in operator algebras saw coming.
The answer is 7 when the dimension is a prime power. In dimension 6 nobody can get past 3.
Numerically found in every dimension tried, exactly constructed in many, and proved in none in general.
Held–Karp has stood since 1962. No exact algorithm is known with running time O(1.99^n).
Babai's quasipolynomial algorithm moved the problem, but the gap to polynomial time remains.
Is there any truly subquadratic algorithm for finding three numbers summing to zero?
Are splay trees within a constant factor of the best possible binary search tree, on every access sequence?
Is deterministic communication complexity polylogarithmic in the rank of the communication matrix?
Widely believed to be equal, and provably tied to circuit lower bounds nobody can prove.
Every improvement since 1969 has shaved digits off 2.37. Nobody can rule out 2 + o(1), and nobody can achieve it.
Half of it was proved in 2018. Whether the full statement holds decides the approximability of dozens of problems at once.