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.
26 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…
Gill introduced the probabilistic automatic complexity A_P(w) of a string: the least number of states of a probabilistic finite automaton for which w is the unique most probably accepted string of its length. He asked whether A_P is…
For fixed d, can every d-dimensional feasible solution of the triangle-strengthened Max-Cut SDP be rounded in polynomial time with ratio strictly larger than α_GW? A rounding achieving α_GW + 2^-O(d) answers yes.
Two open problems about extracting order from trees in real-valued functions. A quantitative function analogue of Hodges's tree-to-order extraction yields an at most double-exponential bound on dual sequential fat-shattering dimension,…
Assuming the Unique Games Conjecture, it is NP-hard to approximate MAX-3-CUT better than the Frieze-Jerrum semidefinite program does, and similarly for Quantum MAX-CUT: the sharpness question in the Khot-Kindler-Mossel-O'Donnell line,…
Given a binary matrix M, decide whether its columns can be permuted so that every row contains at most two blocks of 1s and, if it contains two blocks, they are separated by at most one 0. The claimed theorem proves that this (2,1)-Gapped…
Can the k-distinct language - words over [n] of length at most k with no repeated symbol - be recognized by an acyclic NFA of size c^k n^O(1) for some c < 4? A construction of size 2^1.96992k n^O(1) < 3.918^k n^O(1) answers yes.
Can an S-decoding polynomial modulo a suitable product of k primes attain the lower-bound minimum of k + 1 nonzero coefficients? A construction matches the bound for special products of k primes, yielding exponentially fewer-server PIR.
Does planarity help approximate counting? The paper gives an FPRAS for the planar hard-core partition function at small activity, proves that approximately counting q-colourings on planar graphs is NP-hard for every constant q ≥ 4, and…
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.
Does every synchronizing one-cluster automaton on n states admit a reset word of length at most (n-1)^2? The new bound (m-1)(n-1) + mℓ ≤ (n-1)^2 settles the one-cluster case of the Černý conjecture.
A finite closure system can be given by implications or by a list of subsets closed under intersection. Deciding whether one specification of each kind defines the same family had remained open in several settings; the paper proves the…
Can S-decoding polynomials modulo a product of k primes be built with only k+1 nonzero coefficients, the minimum their own lower bound allows? Yes, via a general framework for special prime products. The consequence is that for any…
Nikolov and Ullman asked, as Open Problem 1 on DifferentialPrivacy.org, whether k statistical queries over a universe of size T can be released under pure differential privacy at the square-root error rate that the known lower bounds…
Can the minimum edge-outerplanarity of a finite loopless planar graph, minimized over all planar embeddings, be computed in polynomial time? Asked by Bentz in 2009.
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…
Among classes of tournaments for which neither hardness nor polynomial-time solvability of isomorphism was known, bounded VC dimension stood out as an open problem of Neuen and Grohe. Resolved: isomorphism of tournaments of VC dimension d…
Can any single-pass semi-streaming algorithm beat the naive greedy 1/2-approximation for maximum matching? No. No single-pass semi-streaming algorithm, deterministic or randomized, achieves a better-than-half approximation, so greedy is…
New upper and lower bounds on the approximation ratio achievable for Multiway Cut via large mixtures of new and old rounding schemes for the CKR relaxation, advancing the ratio ladder that has run since Călinescu-Karloff-Rabani (1998).
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…