18 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.
Proved in one dimension in 2007. In two dimensions it remains the central structural conjecture of the field.
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.
Depth-3 networks can express functions depth-2 cannot. Whether training can find them is a different question, and it is open.
For linear models the answer is a clean minimum-norm statement. For anything deeper, there is no general theory.
Santos disproved the linear bound in 2010. Whether the diameter is polynomially bounded is still unknown.
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?
Tao proved it for polynomials of sufficiently large degree. The remaining degrees are open.
The hexagonal lattice constant is √(2+√2). Nobody knows the value for the square lattice.
Can a countable first-order theory have strictly between ℵ₀ and 2^ℵ₀ countable models?
How many unit balls can touch a central unit ball in R^5? Somewhere between 40 and 44.
Dimensions 1, 2, 3, 8 and 24 are settled. Dimension 4 is not, and the conjectured answer is the D4 lattice.
A single finite number nobody knows: the bounds are 43 and 46, and the answer is widely believed to be 43.