From the 1 of 8 linked papers with an AI index.
8 papers
Online Beck--Fiala Down to Logarithmic Sparsity
Dylan J. Altschuler, Konstantin Tikhomirov
The paper presents an efficient online algorithm that achieves near‑optimal discrepancy for the Beck–Fiala problem when the column sparsity is as low as roughly log T, extending pr…
A universal threshold for geometric embeddings of trees
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
A graph is geometrically embeddable into a normed space when there is a mapping such that if and only if , f…
Metric Poincaré inequalities for graphs
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
This article obtains purely metric counterparts of cornerstone results in the theory of embedding graphs into normed spaces. Our first main result is a metric analogue of MatouÅ¡ek…
A threshold for online balancing of sparse i.i.d. vectors
Dylan J. Altschuler, Konstantin Tikhomirov
Consider the task of \textit{online} vector balancing for stochastic arrivals , where the time horizon satisfies , and the are i.i.d uniform …
Metric dimension reduction modulus for superlogarithmic distortion
Dylan J. Altschuler, Konstantin Tikhomirov
The metric dimension reduction modulus is the smallest such that every --point metric space can be embedded into some -dimensional normed space, wit…
Discrete Poincaré inequalities and universal approximators for random graphs
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
Nonlinear Poincaré inequalities are indispensable tools in the study of dimension reduction and low-distortion embeddings of graphs into metric spaces, and have found remarkable al…