Konstantin E. Tikhomirov

activity

20242026

collaborators

15 papers

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…

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

Metric Poincaré inequalities for graphs

Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1

This article obtains purely metric counterparts of cornerstone results in the theory of embedding graphs into normed spaces. Our first main result is a metric analogue of Matoušek'…

math.MG2025

Metric dimension reduction modulus for superlogarithmic distortion

Dylan J. Altschuler, Konstantin Tikhomirov

The metric dimension reduction modulus $k_{n}^{α} (ℓ_{\infty})$ is the smallest $k$ such that every $n$ --point metric space can be embedded into some $k$ -dimensional normed space, with…

math.MG2025

Discrete Poincaré inequalities and universal approximators for random graphs

Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1

Nonlinear Poincaré inequalities are indispensable tools in the study of dimension reduction and low-distortion embeddings of graphs into metric spaces, and have found remarkable al…

math.CO2025

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 $ζ : V \to X$ such that $∥ ζ (v) - ζ (w) ∥_{X} ⩽ 1$ if and only if ${v, w} \in E$ , for…

math.MG2025

Universal geometric non-embedding of random regular graphs

Dylan J. Altschuler, Konstantin Tikhomirov

Let $Δ \geq 3$ be fixed, $n \geq n_{Δ}$ be a large integer. It is a classical result that $Δ$ --regular expanders on $n$ vertices are not embeddable as geometric (distance) graphs into E…

math.CO2024

Locally seeded embeddings, and Ramsey numbers of bipartite graphs with sublinear bandwidth

Dylan J. Altschuler, Han Huang, Konstantin Tikhomirov

A seminal result of Lee asserts that the Ramsey number of any bipartite $d$ -degenerate graph $H$ satisfies $lo g r (H) = lo g n + O (d)$ . In particular, this bound applies to every b…

math.MG2024

A combinatorial approach to nonlinear spectral gaps

Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1

A seminal open question of Pisier and Mendel--Naor asks whether every degree-regular graph which satisfies the classical discrete Poincaré inequality for scalar functions, also sat…

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…