Konstantin E. Tikhomirov

activity

20242026

collaborators

Showing 2026Show all

5 papers · 1 filter

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

Online Beck--Fiala Down to Logarithmic Sparsity

Dylan J. Altschuler, Konstantin Tikhomirov

The Beck--Fiala conjecture asserts that every matrix $A \in {0, 1}^{n \times T}$ with at most $d$ nonzero entries in each column has discrepancy $O (d)$ . A major breakthrough re…

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…

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…