Open problems

980 registered problems.

OP-00029 Solution claimed

Global synchronization of random 3-regular graphs

PR · global synchronization · Kuramoto model · random regular graphs · Randomstrasse101

OP-00030 Open

Sub-exponential detection in the hard regime of multi-frequency synchronization

ST · group synchronization · Randomstrasse101 · spiked random matrices · statistical-to-computational gaps

OP-00031 Open

The largest discrepancy of square ±1 matrices relative to √n

CO · discrepancy theory · Randomstrasse101 · sign matrices · Spencer's theorem

OP-00032 Open

The Hadamard conjecture

CO · combinatorial designs · Hadamard matrices · Randomstrasse101

OP-00033 Partially resolved

Fast mixing of Glauber dynamics for the SK model up to β = 1

PR · Glauber dynamics · mixing time · Randomstrasse101 · Sherrington–Kirkpatrick model · spin glasses

OP-00034 Open

A type-2 inequality for injective norms of Gaussian sums of tensors

PR · injective norm · matrix concentration inequalities · Randomstrasse101 · random tensors

OP-00035 Open

The Lovász number of random circulant graphs

CO · circulant graphs · Lovász theta function · random graphs · Randomstrasse101

OP-00036 Partially resolved

Vinzant's conjecture on 4M − 5 phase retrieval measurements

FA · frames · injectivity · phase retrieval · Randomstrasse101

OP-00037 Open

The Balan–Wang conjecture on the stability of real phase retrieval

FA · frames · phase retrieval · Randomstrasse101 · stability

OP-00038 Partially resolved

A degree-4 Sum-of-Squares proof that ℂ⁶ has no seven mutually unbiased bases

OC · mutually unbiased bases · Randomstrasse101 · semidefinite programming · Sum-of-Squares

OP-00039 Solution claimed

Zauner's conjecture

FA · equiangular tight frames · quantum information · Randomstrasse101 · SIC-POVM

OP-00040 Open

The clique number of Paley graphs

NT · clique number · Paley graph · pseudorandom graphs · Randomstrasse101

OP-00041 Open

The Lovász number of the 1-localization of the Paley graph

CO · clique number · Lovász theta function · Paley graph · Randomstrasse101

OP-00042 Open

A Lovász-number bound for the 2-localization of the Paley graph

CO · clique number · Lovász theta function · Paley graph · Randomstrasse101

OP-00043 Open

A degree-4 Sum-of-Squares bound for the Paley clique number

OC · clique number · Paley graph · Randomstrasse101 · Sum-of-Squares

OP-00044 Open

The Paley ETF restricted isometry conjecture

FA · compressed sensing · equiangular tight frames · Paley graph · Randomstrasse101 · restricted isometry property

OP-00045 Solution claimed

The Kannan–Lovász–Simonovits conjecture

PR · convex geometry · isoperimetry · KLS conjecture · log-concave measures · Randomstrasse101

OP-00046 Open

Minimum and maximum bisections of random regular graphs

PR · graph bisection · maximum cut · random regular graphs · Randomstrasse101 · spin glasses

OP-00047 Open

Directional convex hulls that are not semialgebraic

MG · directional convexity · Randomstrasse101 · rank-one convexity · semialgebraic sets

OP-00048 Open

When are directional convex hulls semialgebraic?

MG · directional convexity · Randomstrasse101 · rank-one convexity · semialgebraic sets

OP-00049 Open

Rigorous consequences of low-degree hardness

ST · hypothesis testing · low-degree polynomials · Randomstrasse101 · statistical-to-computational gaps

OP-00050 Open

A low-degree polynomial that finds cliques of size log₂ n in G(n, 1/2)

PR · clique number · low-degree polynomials · random graphs · Randomstrasse101

OP-00051 Solution claimed

The Group Spencer conjecture

CO · discrepancy theory · Matrix Spencer · Randomstrasse101 · regular representation

OP-00052 Solution claimed

Global synchronization with negative edges

PR · Burer–Monteiro · community detection · global synchronization · Kuramoto model · Randomstrasse101

OP-00053 Solution claimed

The minimum-degree threshold 3/4 for global synchronization

CO · extremal graph theory · global synchronization · Kuramoto model · Randomstrasse101

OP-00054 Solution claimed

The spectral threshold of Kikuchi matrices for tensor PCA

PR · Kikuchi hierarchy · random matrices · Randomstrasse101 · statistical-to-computational gaps · tensor PCA

OP-00055 Solution claimed

Infinitely many square ±1 matrices with discrepancy a constant factor above √n

CO · discrepancy theory · Randomstrasse101 · sign matrices · Spencer's theorem

OP-00056 Solved

The discrepancy of the Sylvester–Hadamard matrices H_k for odd k

CO · Boolean functions · discrepancy theory · Hadamard matrices · Randomstrasse101

OP-00057 Solution claimed

The Lovász number of G(n, 1/2)

CO · Lovász theta function · random graphs · Randomstrasse101 · semidefinite programming

OP-00058 Solution claimed

Maximum cut and maximum bisection of random regular graphs

PR · graph bisection · maximum cut · random regular graphs · Randomstrasse101

OP-00059 Solution claimed

Sharp norm bounds for graph matrices

PR · graph matrices · matrix chaos · random matrices · Randomstrasse101 · Sum-of-Squares

OP-00060 Solution claimed

The value of ω(A) for Gaussian matrices in real phase retrieval

PR · phase retrieval · random matrices · Randomstrasse101 · stability

OP-00061 Solution claimed

The Matrix Spencer conjecture

CO · discrepancy theory · Matrix Spencer · random matrices · Randomstrasse101

OP-00062 Solution claimed

Fitting ellipsoids to random points: the threshold d²/4

PR · ellipsoid fitting · phase transitions · random geometry · Randomstrasse101 · semidefinite programming

OP-00063 Solution claimed

A diverging number of frequencies in multi-frequency synchronization

ST · group synchronization · Randomstrasse101 · spiked random matrices · statistical-to-computational gaps

OP-00064 Solution claimed

The Komlós conjecture

CO · discrepancy theory · Komlós conjecture · Randomstrasse101 · vector balancing

OP-00075 Solution claimed

No seven mutually unbiased bases in ℂ⁶

CO · frames · mutually unbiased bases · quantum information · Randomstrasse101