Konstantin E. Tikhomirov

activity

20242026

collaborators

Showing 2026 · math.PRShow all

3 papers · 2 filters

math.PR2026

Online Permutation Embedding: Optimal Stopping and Scaling Laws

Dylan J. Altschuler, Quentin Dubroff, Konstantin Tikhomirov

We study optimal online algorithms for embedding a permutation $π$ of $[k]$ into an iid stream of uniform $[0, 1]$ random variables. This problem is a broad generalization of the cl…

math.PR2026

Level-set entropy and sparse randomized embeddings

Konstantin Tikhomirov

Let $Π$ 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 ${\math…

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, α)$ -oblivious subspace injection} (OSI) if $E ∥ S^{⊤} x ∥_{2}^{2} = ∥ x ∥_{2}^{2}$ for every $x \in R^{n}$ , and for every fixed…