Konstantin E. Tikhomirov

works on

beck-fiala conjecture 1 discrepancy theory 1 metropolis walk 1 online algorithms 1 vector balancing 1

From the 1 of 12 linked papers with an AI index.

activity

20242026

collaborators

Showing math.COShow all

3 papers · 1 filter

math.CO2026

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…

math.CO2026

A universal threshold for geometric embeddings of trees

Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1

A graph $G = (V, E)$ is geometrically embeddable into a normed space $X$ when there is a mapping $I^¶ : V \to X$ such that $∥ I^¶ (v) - I^¶ (w) ∥_{X} ⩽ 1$ if and only if ${v, w} \in E$ , f…

math.CO2024

Locally seeded embeddings, and Ramsey numbers of bipartite graphs with sublinear bandwidth

Dylan J. Altschuler, Han Huang, Konstantin Tikhomirov

A seminal result of Lee asserts that the Ramsey number of any bipartite $d$ -degenerate graph $H$ satisfies $lo g r (H) = lo g n + O (d)$ . In particular, this bound applies to every b…