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.PRShow all

3 papers · 1 filter

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

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 $(X_{i})_{i \in [T]}$ , where the time horizon satisfies $T = I^ (n)$ , and the $X_{i}$ are i.i.d uniform $d$ …