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 11 linked papers with an AI index.

collaborators

11 papers

math.PR2026

Level-set entropy and sparse randomized embeddings

Konstantin Tikhomirov

Let $I^$ be a $k \times n$ sparse random matrix. For a fixed $r$ -dimensional subspace $V \subset R^{n}$ , let $U_{V} : R^{r} \to R^{n}$ denote an isometry from ${\mat…

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.PR2026

Well-invertible column subsets of sparse matrices are rare

Han Huang, Mark Rudelson, Konstantin Tikhomirov

A random $n \times k$ matrix $S$ is an \emph{ $(r, I^\pm)$ -oblivious subspace injection} (OSI) if $E ∥ S^{⊤} x ∥_{2}^{2} = ∥ x ∥_{2}^{2}$ for every $x \in R^{n}$ , and for every fixed…

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.FA2026

Cotype of random polytopes

Han Huang, Konstantin Tikhomirov

For $N \geq n$ , let $P_{N, n}$ be a random polytope in $R^{n}$ with vertices $\pm X_{i}$ , $1 \leq i \leq N$ , where $X_{1}, \dots, X_{N}$ are i.i.d standard Gaussian vectors in ${\mathb…

math.MG2026