Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Can there be a finite covering system of the integers with distinct moduli, all of which are odd and greater than 1?
For an inclusion-free hypergraph on n vertices, a weight assignment w:[n]→[d] is isolating when a unique edge attains minimum weight. Faber and Harris conjectured that the number of isolating assignments is at least n∑_j=0^d-1 j^n-1,…
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…
Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. Their conjectured lower bound is established for…
Norine conjectured that every red-blue edge-colouring of the n-dimensional hypercube Q_n in which antipodal edges get opposite colours contains a monochromatic path from some vertex to its antipode. The paper proves it, via a chain-level…
Arjevani et al. asked whether almost-surely bounded oracle error permits a better rate than bounded variance for smooth nonconvex stochastic optimization. It does not: every randomized adaptive algorithm still needs Omega(dL/eps^2 + dL…
Sivaraman asked whether perfect divisibility is characterized by its chromatic consequence: is a graph G perfectly divisible if and only if χ(H) ≤ binomω(H)+12 for every induced subgraph H of G? False: the Paley graph P(17) satisfies the…
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…
Erdos asked whether a finite unit-distance graph in the plane can have independence ratio below 1/4. One exists, built on the geometric fractional chromatic number framework of Matolcsi, Ruzsa, Varga and Zsamboki plus a carefully chosen…
Localizing Bernstein theory to prove lower bounds for the Lebesgue constants of Lagrange interpolation, with application to a problem of Erdős and Turán and to a conjectured bound from the interpolation literature.
Shokurov's global index conjecture, in the setting of foliations. Proved for foliations in dimension at most three, which also answers a question of Liu, Meng and Xie in dimension three.
The classical Abbott-Hanson recurrence gives S(k+2) ≥ 9S(k)+4 for Schur numbers, and had stood as the basis for the best asymptotic lower bounds. Shifted S-templates, a more flexible form of Rowley's template construction, yield S(k+2) ≥…
Let A(x) count n ≤ x such that every prime p | n has a divisor d > 1 of n with d ≡ 1 pmod p. Erdos asked whether A(x)/x = exp(-(c+o(1))√log xloglog x). It does, with c = 1/(2√log 2).
The Hessian conjecture HC_n asks whether every polynomial f with det Hess(f) ∈ C^× has a polynomial gradient inverse. It is known for n ≤ 3, false for n ≥ 5, and open exactly in dimension four, where it implies the plane Jacobian…
Regts and Sevenster conjectured that a complex-valued graph parameter f with f(∅)=1 has exponentially bounded edge-connection rank precisely when it is a mixed partition function. The paper proves it, with the numbers of even and odd…
For a finite-dimensional algebra A, finite global dimension forces HH_n(A) = 0 for all large n. Han conjectured the converse: eventual vanishing of Hochschild homology should detect homological smoothness. Disproved by an explicit…
Erdős, Herzog and Piranian (1958) asked whether the regular n-gon maximizes the product of pairwise distances among n points of fixed diameter. After the recent discovery that it does not for even n, this paper proves the first exponential…
Does the Dinitz-Garg-Goemans cost-preserving unsplittable-flow rounding conjecture survive on acyclic planar instances with only four terminals? An explicit instance answers no: every cost-nonincreasing unsplittable routing has upper…
For A=0,1,2^d, write f(d) for the fewest proper sub-boxes covering every point exactly twice. Leader, Miličević and Tan asked whether f(d)≥ 2^d for all d, as Question 4.1 of the PatternBoost paper. The paper gives new bounds on f(d).
Let D_q(n) be the largest possible least degree of a polynomial omitted by a non-covering family of n distinct-modulus congruence classes in F_q[x]. What is its asymptotic size? The answer is D_q(n) = n/q-1 + O_q(1).