Problems

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,…

Is computing a Kemeny-optimal aggregate ranking NP-hard when the input consists of exactly three complete rankings? Hardness was known for every even n ≥ 4; three voters was the minimal open case, and n = 2 is polynomial-time solvable.

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.

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 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.

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…

Given online vectors v_t ∈ R^d with |v_t|_2 ≤ 1, can signs ε_t ∈ -1, 1 be chosen in O(dT) total time so that every prefix has ℓ_∞ discrepancy O(√log T) with high probability? The previous optimal algorithm ran in time exponential in T and…

Can online vector balancing in the Spencer setting achieve the optimal order of prefix discrepancy with an efficient algorithm?

Klopp and Zadik gave an exponential-time node-private algorithm for exact community recovery in stochastic block models and asked whether a polynomial-time algorithm could match it. One can: a Lipschitz surrogate for the penalized…

Furthest Pair and its relatives admit f(d) n^2-Θ(1/d) algorithms, making them the standard examples of barely subquadratic computation, and whether that is optimal in superconstant dimension was open. Under SETH it is: Furthest Pair…