#lower bounds
20 papers · 1 filter
Entropy-Smooth Convex Optimization Cannot Be Accelerated
Jacob M. Aguirre, Dmitrii M. Ostrovskii
The paper proves that for convex functions that are smooth relative to negative entropy (or von Neumann entropy in the quantum case), no first-order method can achieve an accelerat…
Stronger Lower Bounds for Tree Covers via Cyclic Symmetry
Shengtang Huang
The paper improves known lower bounds on the distortion of tree covers for n-point metric spaces by using cyclic symmetry instead of antipodal symmetry, tightening the gap between…
Improved Bounds for Distinct Multiples in Intervals
Kaizhe Chen, Samuel Korsky
The paper establishes new lower and upper bounds for the functions F(n) and h_P(n), which measure the smallest interval length needed to contain distinct multiples of all integers…
Polynomially Improved Lower Bounds for Trifferent Codes via Locally Sparse -Uniform Hypergraphs
Xuejiao Han, Yubo Sun, Gennian Ge
The paper improves the known lower bound on the size of ternary trifferent codes by a factor of √n, using a refined concatenation method that employs locally sparse 3‑uniform hyper…
A Census of New Snake-in-the-Box Records
Paul Orland, Lucas Fagan, Michele Tarquini +7
The paper presents new longest induced (chordless) paths, called snakes, in hypercube graphs for dimensions 9 through 13, thereby improving the known lower bounds for the snake-in-…
A lower bound of 4 for online graph exploration
Julia Baligacs
The paper proves that any online algorithm for graph exploration must have a competitive ratio of at least 4, improving the previous bound of 10/3, and shows that certain restricti…