Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
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.
For semifree noncommutative differential graded algebras over a nontrivial computable unital commutative ring, are stable tame isomorphism, quasi-isomorphism, or derived Morita equivalence algorithmically decidable? All three are…
Let X be a set of cardinality ℵ_ω and f a function from the finite subsets of X to X such that f(A)not∈ A for all A. Must there exist an infinite independent Y⊆ X, i.e. with f(B)not∈ Y for all finite B⊂ Y? Claimed resolution: the positive…
Baker asked, as recorded by Poonen, whether a fixed smooth quasiprojective variety over a finite field must acquire a smooth rational hyperplane section after every sufficiently high-dimensional linearly nondegenerate embedding. Poonen…
Espuny Diaz, Lichev and Wesolek conjectured that a Dirac-type minimum degree condition forces Hamiltonicity in spanning subgraphs of cycle powers. Asymptotically true: for every ε > 0 and all large k, any spanning subgraph of the kth power…
Carefully designed stepsize schedules alone accelerate plain gradient descent beyond its textbook O(1/T) rate, without momentum. Whether they can reach the optimal O(T^-2) was open. A lower bound of Omega(T^-1.9319) for last-iterate…
Let H(n) be the largest number of vertices in a hypergraph with no isolated vertices and no partition of size greater than n. With k_1 = 1 and k_n = ⌊ n/2 ⌋ + k_⌊ n/2 ⌋ + k_⌈ n/2 ⌉, prove H(n) ≥ c k_n for some constant c > 1, already for n…
Are the Kazhdan-Lusztig polynomials of matroids always unimodal - in particular log-concave, or even real-rooted, as conjectured? No: representable matroids obtained by deleting points from finite projective geometries have non-unimodal…
Zhao's Generalized Vanishing Conjecture asks whether, for a differential operator with constant coefficients, Λ^m(P^m) = 0 for all large m forces Λ^m(P^m Q) = 0 for all large m. Refuted by an explicit five-variable counterexample.
If Sidon sets A, B ⊆ 1, …, N satisfy (A-A) ∩ (B-B) = 0, must binom|A|2 + binom|B|2 ≤ binomf(N)2 + O(1), where f(N) is the largest Sidon-set size in [N] - and can the bound be improved by a fixed proportion when |A| = |B|?
Wegner conjectured in 1965 that every finite family R of axis-parallel rectangles satisfies τ(R) ≤ 2ν(R) - 1, where τ is the minimum number of piercing points and ν the largest pairwise-disjoint subfamily. False, by an explicit…
What is the largest possible measure of a subset of a radius-R disk in R^2 containing no pair of points at a positive integer distance? A Poisson-Bessel kernel argument gives M(R) ≪ R^1/2; with Sárközy's lower construction, M(R) = R^1/2 +…
Extending the minimal model program beyond threefolds in positive characteristic is a standing goal of birational geometry. Assuming the log resolution conjecture for all log pairs birational to X, the cone theorem holds for projective log…
Djament asked whether a Grothendieck category satisfying suitable finiteness and exactness conditions must be equivalent to a module category. In the locally noetherian case the answer is no: there is a Grothendieck category with a…
A t-(v,k,λ) covering is a family of k-subsets of a v-set meeting every t-subset at least λ times, and C(v,k,t) is the least number of blocks. The recorded bounds for C(12,6,4) were 40 ≤ C(12,6,4) ≤ 41. No 4-(12,6,1) covering with 40 blocks…
Litvak conjectured in 2018 that for every p > 0 the quantity E[min_i ≤ n |g_i|^p], for g ~ N(0,Σ), is minimized over n × n correlation matrices by the Gram matrix of the regular simplex in R^n-1. False: the matrix Σ^cos_ij = cos(π(i-j)/n)…
For a positive projection P on a Dedekind complete Banach lattice whose largest central operator below P is α id, Wickstead conjectured α must be 0 or 1/n for some natural n, and proved the finite-dimensional case. The paper proves the…
Does every globally asymptotically stable homogeneous polynomial vector field admit a homogeneous polynomial Lyapunov function? No. A planar homogeneous cubic vector field with integer coefficients is globally asymptotically stable yet…
Can one hear the shape of a drum, in the Steklov setting and in the plane? No: there exist pairs of noncongruent bounded plane domains with identical Steklov spectra including multiplicities, simply connected, strictly convex, with…
Is the difference between the numbers of positive and negative adjacency eigenvalues of every connected line graph at most one? A 14-vertex witness has signature 2, and chaining copies gives connected line graphs of signature k + 1 for…