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.
4 problems
The low-degree conjecture predicts that when the low-degree advantage between a planted distribution and a uniform null distribution stays bounded, no polynomial-time algorithm can distinguish them. It is false. There is a planted…
Does exhaustive AdaBoost always converge to a finite cycle of weak classifiers and weight vectors on every finite training set? A finite instance whose orbit never becomes periodic answers no.
Odifreddi asked, as Problem 3 in his surveys "Strong Reducibilities" (1981) and "Reducibilities" (1999), whether every computably enumerable tt-degree contains a c.e. irreducible m-degree, meaning an m-degree consisting of a single…
Steurer conjectured in 2010 that any family of n unit vectors with polynomially small average correlation E_i,j|⟨ v_i,v_j⟩| ≤ n^-ε contains linear-sized constant-separated sets. Refuted in a strong sense, using sparse high-dimensional…