The index

Community consensus

28 entries matching the current filters. Sorted by recently added.

Full hierarchy →

Community consensus×Open×Clear all

OP-0057Condensed matterOpen

Does the two-dimensional Hubbard model superconduct?

The simplest model believed to capture high-temperature superconductivity, and its phase diagram is still contested.

Community consensus· 1987

OP-0054Quantum informationOpen

An area law for two-dimensional gapped ground states

Proved in one dimension in 2007. In two dimensions it remains the central structural conjecture of the field.

Community consensus· 2007

OP-0053Quantum informationOpen

How many mutually unbiased bases are there in dimension 6?

The answer is 7 when the dimension is a prime power. In dimension 6 nobody can get past 3.

Community consensus· 1989

OP-0052Quantum informationOpen

Zauner's conjecture: do SIC-POVMs exist in every dimension?

Numerically found in every dimension tried, exactly constructed in many, and proved in none in general.

Community consensus· 1999

OP-0051Quantum informationOpen

The quantum PCP conjecture

Is estimating the ground state energy of a local Hamiltonian to constant relative precision still QMA-hard?

Community consensus· 2002

OP-0049Deep learning theoryOpen

Depth separation for functions learnable by gradient descent

Depth-3 networks can express functions depth-2 cannot. Whether training can find them is a different question, and it is open.

Community consensus· 2016

OP-0047Deep learning theoryOpen

Characterise the implicit bias of gradient descent for non-linear networks

For linear models the answer is a clean minimum-norm statement. For anything deeper, there is no general theory.

Community consensus· 2017

OP-0038Algorithms and data structuresOpen

The polynomial Hirsch conjecture

Santos disproved the linear bound in 2010. Whether the diameter is polynomially bounded is still unknown.

Community consensus· 1957

OP-0036CryptographyOpen

Do one-way functions exist?

The minimal assumption of modern cryptography, and it has never been proved from anything weaker than itself.

Community consensus· 1976

OP-0035Algorithms and data structuresOpen

Beating 2^n for the travelling salesman problem

Held–Karp has stood since 1962. No exact algorithm is known with running time O(1.99^n).

Community consensus· 1962

OP-0034Algorithms and data structuresOpen

Is graph isomorphism in P?

Babai's quasipolynomial algorithm moved the problem, but the gap to polynomial time remains.

Community consensus· 1972

OP-0033Computational complexityOpen

A superlinear circuit lower bound for an explicit function

After fifty years, the best known bound for any function in NP is about 3.1n gates.

Community consensus· 1949

OP-0032Algorithms and data structuresOpen

The 3SUM conjecture

Is there any truly subquadratic algorithm for finding three numbers summing to zero?

Community consensus· 1995

OP-0031Algorithms and data structuresOpen

The dynamic optimality conjecture

Are splay trees within a constant factor of the best possible binary search tree, on every access sequence?

Community consensus· 1985

OP-0030Computational complexityOpen

The log-rank conjecture

Is deterministic communication complexity polylogarithmic in the rank of the communication matrix?

Community consensus· 1988

OP-0029Computational complexityOpen

Does randomness help? BPP versus P

Widely believed to be equal, and provably tied to circuit lower bounds nobody can prove.

Community consensus· 1977

OP-0028Algorithms and data structuresOpen

Is the exponent of matrix multiplication equal to 2?

Every improvement since 1969 has shaved digits off 2.37. Nobody can rule out 2 + o(1), and nobody can achieve it.

Community consensus· 1969

OP-0027Computational complexityOpen

The Unique Games Conjecture

Half of it was proved in 2018. Whether the full statement holds decides the approximability of dozens of problems at once.

Community consensus· 2002

OP-0023ProbabilityOpen

The connective constant of self-avoiding walks on Z²

The hexagonal lattice constant is √(2+√2). Nobody knows the value for the square lattice.

Community consensus· 1953

OP-0022ProbabilityOpen

Conformal invariance of critical percolation on the square lattice

Smirnov proved it for the triangular lattice in 2001. The square lattice remains untouched.

Community consensus· 1992

OP-0021Logic and foundationsOpen

Vaught's conjecture

Can a countable first-order theory have strictly between ℵ₀ and 2^ℵ₀ countable models?

Community consensus· 1961

OP-0019Number theoryOpen

The Littlewood conjecture

Can two real numbers be simultaneously badly approximable in the multiplicative sense?

Community consensus· 1930

OP-0016Geometry and topologyOpen

The kissing number in dimension 5

How many unit balls can touch a central unit ball in R^5? Somewhere between 40 and 44.

Community consensus· 1694

OP-0015Geometry and topologyOpen

Optimal sphere packing in dimension 4

Dimensions 1, 2, 3, 8 and 24 are settled. Dimension 4 is not, and the conjectured answer is the D4 lattice.

Community consensus· 1611

OP-0013CombinatoricsOpen

The Ramsey number R(5,5)

A single finite number nobody knows: the bounds are 43 and 46, and the answer is widely believed to be 43.

Community consensus· 1935