Imported from VibeMathed under CC BY 4.0. Each record links to its registry entry and named primary source. Registry verification is preserved verbatim.
What is the optimal competitive ratio for online vertex cover when edges arrive one at a time? The paper proves a tight factor-2 lower bound via a reduction in the blueprint framework of Assadi, Jiang and Xiang, closing the gap left by prior work.
Online Shadow Tomography with logm dependence, while retaining poly(log(d)/ϵ) dependence. Also, matching the best classical bounds for Adaptive Data Analysis
Sampling a nearly uniform Eulerian tour of a directed Eulerian multigraph was stuck at mn-type running times coming from arborescence sampling. A randomized algorithm achieves O(m3/2) worst case, breaking that barrier on sparse graphs.
Iterates of a firmly nonexpansive operator converge weakly but not strongly, by Genel and Lindenstrauss. Whether their Cesaro means converge strongly was open. They need not: an explicit curve gives a counterexample.
Monical, Tokcan and Yong conjectured that Schubitopes, the generalized permutahedra arising as Newton polytopes of Schubert polynomials and of Demazure characters of GLn, are Ehrhart positive. Disproved by an explicit Schubitope whose Ehrhart polynomial has a negative coefficient in its monomial expansion.
Moraga conjectured, and Kollár and Zhuang recorded, an odd-dimensional extension of the rank bound for faithful abelian p-group actions on smooth Calabi–Yau varieties. The paper disproves it.
After L2 normalization, stable phase retrieval holds over the L2-spans of independent real-valued centered random variables exactly when all but possibly one coordinate satisfies a uniform two-sided L1 bound. This confirms the characterization conjectured by Calderbank, Daubechies, Freeman and Freeman.
If a chromatic symmetric function is Schur positive, must every finite-variable specialization XG(x1,…,xk) have a saturated Newton polytope? A 12-vertex bipartite graph realizes weights (6,6,0) and (8,2,2) but omits their midpoint (7,4,1).
The interchange graph G(R,S) has the (0,1)-matrices with row sums R and column sums S as vertices, adjacent when they differ by a single 2×2 interchange. Brualdi asked whether G(R,S) is always Hamiltonian. It satisfies more: it is maximally Hamiltonian, Hamilton-laceable when bipartite and Hamilton-connected when not.
Both bounds move, and the gap stays enormous: the lower bound rises from exp(Ω(log2k)) to exp(Ω(k1/3)) and the upper falls from exp(O(k4)) to exp(O(k2)), so A(k) is still undetermined between an exponent of k1/3 and one of k2. The paper's own closing discussion argues its lower-bound construction is near the limit of the method and that beating it needs additional randomness,…
The total Chern class of Symd(Cn) as a torus representation is a symmetric polynomial whose coefficients were conjectured positive, with a binomial log-concavity refinement. Both are established.
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 sum satisfy ∥Wss∥≤∥Wrs∥≤∥Wgd∥. They do.
This is the MODIFIED conjecture, not the original Lyons-Sidorova one, and it is proved for continuous bounded-variation paths. Prior work had a line-image result under the stronger assumption of infinite radius on every subinterval; this removes that assumption.
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 predicted no for every positive-dimensional variety, and that prediction is correct.
Three immediate consequences follow for undirected unweighted planar graphs: better compression of the Okamura-Seymour metric, less space for constant-time exact distance oracles, and a faster distributed algorithm.
Ziegler proved every simplicial d-dimensional 0/1-polytope has at most 2d vertices, and asked whether attaining 2d vertices forces central symmetry (i.e. a 0/1 cross-polytope). Known true for d≤6; open since ~2000.
Zhao's Generalized Vanishing Conjecture asks whether, for a differential operator with constant coefficients, Λm(Pm)=0 for all large m forces Λm(PmQ)=0 for all large m. Refuted by an explicit five-variable counterexample.
The Hessian conjecture HCn asks whether every polynomial f with detHess(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 conjecture. Proved for every quartic polynomial in dimension four: the quartic case reduces to f=P(x1,x2,x3)+x4Q(x1,x2,x3)+ax42 wi…
The realisation problem asks which unital Banach algebras arise as the Calkin algebra B(X)/K(X) of some Banach space. Recorded in Tarbard's thesis and studied by Horváth and Kania. The paper exhibits a unital Banach algebra that cannot be one.
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))(4n), by reducing arbitrary pairs of trees to caterpillars through a common-root planarization and an identity on five-leaf trees.
Escobar, Klein and Weigandt proved that gradedness of an ASM weak order interval, constancy of Coxeter length across its fibres, and equidimensionality of the associated ASM varieties are mutually equivalent, and conjectured (Conjecture 3.21) that Cohen-Macaulayness of those varieties belongs on the same list. Proved, via a 0-Hecke monoid action on the MacNeille completion of Bruhat order and vertex-decomposabilit…
Does quantum memory give a query-complexity advantage for learning an unknown quantum channel, when protocols without it must measure after each channel use and keep only a classical transcript? It does, and the paper also determines how little coherent memory suffices for the advantage to appear.
Conditional on the randomized exact-volume Small-Set Expansion Hypothesis, and stated for least-squares objectives rather than sparse convex optimization in general.