Problems
No problem here has yet been reviewed by a person.
Yun, Sra and Jadbabaie posed as a COLT 2021 open question whether, for well-conditioned symmetric matrices, the operators encoding the expected iterate of single-shuffle SGD, random-reshuffle SGD and gradient descent on a quadratic finite…
Ehrhart conjectured that a full-dimensional compact convex body in R^n whose barycenter is its unique interior lattice point has volume at most (n+1)^n/n!. With the inequality itself settled, the remaining question was which bodies attain…
da Silva Machado and Seade conjectured that weighted homogeneous isolated hypersurface singularities are exactly those admitting a logarithmic vector field transverse to the link. True: for a reduced isolated hypersurface germ in C^n+1…
Does bipartite bound information exist: classical correlations between two parties and an eavesdropper that cost secret bits to create, yet from which no secret key can ever be distilled?
For every real ξ>0 the sequence of integer parts [ξ 7^n], n=0,1,2,…, contains infinitely many composite numbers. Second, there is no infinite right truncatable prime in base~7.
Prim-Dijkstra routing interpolates between a minimum spanning tree and a shortest-path tree, and has been used and improved in VLSI physical design since the early 1990s, but the complexity of the terminal-only Manhattan decision problem…
What is the optimal uniform continuity bound for quantum conditional entropy in trace distance, depending only on the dimension of the conditioned system? The sharp bound h_2(δ) + δ log(d^2 - 1) up to δ = 1 - d^-2, conjectured by Wilde, is…
The quartet distance counts the four-leaf subsets on which two binary phylogenetic trees display different topologies. Bandelt and Dress conjectured the maximum over trees on n leaves. Proved: it is (2/3 + o(1))binomn4, by reducing…
Coble and Barg introduced binary Coxeter codes, the span of indicators of standard cosets of fixed rank in a finite Coxeter system, generalizing Reed-Muller codes, and proposed a conjectural value for the minimum distance of a general…
Kawauchi conjectured that the Conway polynomial of an amphicheiral knot factors as ∇_K(z) = f(z)f(-z) for an integer polynomial f. Hartley proved it for negative amphicheiral knots and Ermotti, Hongler and Weber published the first…
The dissipative barrier method suppresses spectral pollution when a differential operator is truncated, but can it hide genuine spectral points? Known as the graveyard problem, the question stayed open in dimension two and above for more…
Given n independent standard Gaussian vectors in R^d, an ellipsoid fit is a positive semidefinite S with x_i' S x_i = d for every i. Saunderson, Parrilo and Willsky conjectured that this semidefinite feasibility problem has a sharp…
For the set of n by n doubly stochastic matrices, Kim and Roush conjectured in 1981 that for odd n = 2k+1 > 1 the maximum of per(I-A) equals 3 times 2^(k-2), attained by an explicit block construction. Proved in full, and the maximizers…
Gao, Huo and Ma asked whether for every fixed k ≥ 3 there is a function f_k(n) → ∞ such that every n-vertex (k+1)-critical graph contains f_k(n) consecutive cycle lengths. The paper settles this and two related problems on cycle lengths…
Dogon, Levit and Vigdorovich asked for an explicit upper bound on the stability radius of an infinitely presented group. The lamplighter group provides the first: explicit polynomial bounds on both its Hilbert-Schmidt stability rate and…
If a subgroup of a product of groups of type F_k virtually surjects onto every k-tuple of factors, must it be of type F_k itself? Yes, for discrete groups, and likewise for FP_k. The homological n-(n+1)-(n+2) Conjecture follows for…
Davis, Figiel, Johnson and Pełczyński showed their interpolation space admits a Schauder basis when the range space has a shrinking one. Can the DFJP space always be chosen with a basis whenever the range space has a basis? The paper…
The Elton–Odell theorem gives, in every infinite-dimensional normed space, a unit-sphere sequence with mutual distances at least 1+ε. Over C, identifying vectors differing by a unimodular scalar gives a toroidal distance. Does every…
The discrete-time Kac walk on S^n-1 started from a coordinate vector exhibits total variation cutoff at C_BRW n log n, where C_BRW ≈ 3.8916 is set by the speed of the leftmost particle in a branching random walk. The cutoff is therefore…
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…