Konstantin E. Tikhomirov

activity

20242026

collaborators

Showing math.PRShow all

6 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.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.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 = Θ (n)$ , and the $X_{i}$ are i.i.d uniform $d$ -…

math.PR2024

On spectral outliers of inhomogeneous symmetric random matrices

Dylan J. Altschuler, Patrick Oliveira Santos, Konstantin Tikhomirov +1

Sharp conditions for the presence of spectral outliers are well understood for Wigner random matrices with iid entries. In the setting of inhomogeneous symmetric random matrices (i…

math.PR2024

A note on the capacity of the binary perceptron

Dylan J. Altschuler, Konstantin Tikhomirov

Determining the capacity $α_{c}$ of the Binary Perceptron is a long-standing problem. Krauth and Mezard (1989) conjectured an explicit value of $α_{c}$ , approximately equal to .833, an…