K. Tikhomirov

activity

20122026

most citedOn the spectral radius of a random matrix: an upper bound without fourth moment

25 citations · 89 across the 31 of their papers we have counts for

collaborators

49 papers

math.PR2026

The threshold for online balancing of i.i.d. binary vectors

Dylan J. Altschuler, Konstantin Tikhomirov

Consider the task of online vector balancing for stochastic arrivals $X_{1}, \dots, X_{T}$ , where the $X_{i}$ are independent uniformly random $d$ --sparse binary vectors in ${0, 1}^{n}$ .…

math.PR2023

On pseudospectrum of inhomogeneous non-Hermitian random matrices

Konstantin Tikhomirov

Let $A$ be an $n \times n$ matrix with mutually independent centered Gaussian entries. Define \begin{align*} σ^*:=\max\limits_{i,j\leq n}\sqrt{{\mathbb E}\,|A_{i,j}|^2}, \quad σ:=\m…

math.MG2023

On the probability that convex hull of random points contains the origin

Konstantin Tikhomirov

The classical theorem of Wendel provides an exact formula for the probability that the convex hull of independent symmetrically distributed vectors in $R^{d}$ contains the…

math.PR2022

Upgrading MLSI to LSI for reversible Markov chains

Justin Salez, Konstantin Tikhomirov, Pierre Youssef

For reversible Markov chains on finite state spaces, we show that the modified log-Sobolev inequality (MLSI) can be upgraded to a log-Sobolev inequality (LSI) at the surprisingly l…

math.CO2022★ 1 cited

On bounded degree graphs with large size-Ramsey numbers

Konstantin Tikhomirov

The size-Ramsey number $r^(G^{'})$ of a graph $G^{'}$ is defined as the smallest integer $m$ so that there exists a graph $G$ with $m$ edges such that every $2$ -coloring of the edges…

math.CO2022

A remark on the Ramsey number of the hypercube

Konstantin Tikhomirov

A well known conjecture of Burr and Erdos asserts that the Ramsey number $r (Q_{n})$ of the hypercube $Q_{n}$ on $2^{n}$ vertices is of the order $O (2^{n})$ . In this paper, we show that $r(…

math.PR2022★ 1 cited

Regularized modified log-Sobolev inequalities, and comparison of Markov chains

Konstantin Tikhomirov, Pierre Youssef

In this work, we develop a comparison procedure for the Modified log-Sobolev Inequality (MLSI) constants of two reversible Markov chains on a finite state space. Efficient comparis…

math.NA2022★ 1 cited

Average-case analysis of the Gaussian Elimination with Partial Pivoting

Han Huang, Konstantin Tikhomirov

The Gaussian Elimination with Partial Pivoting (GEPP) is a classical algorithm for solving systems of linear equations. Although in specific cases the loss of precision in GEPP due…

math.PR2022

Quantitative invertibility of non-Hermitian random matrices

Konstantin Tikhomirov

The problem of estimating the smallest singular value of random square matrices is important in connection with matrix computations and analysis of the spectral distribution. In th…

math.ST2021★ 4 cited

Exact Matching of Random Graphs with Constant Correlation

Cheng Mao, Mark Rudelson, Konstantin Tikhomirov

This paper deals with the problem of graph matching or network alignment for Erdős--Rényi graphs, which can be viewed as a noisy average-case version of the graph isomorphism probl…

math.PR2021

Shotgun assembly of unlabeled Erdos-Renyi graphs

Han Huang, Konstantin Tikhomirov

Given a positive integer $n$ , an unlabeled graph $G$ on $n$ vertices, and a vertex $v$ of $G$ , let $N_{G} (v)$ be the subgraph of $G$ induced by vertices of $G$ of distance at most on…

math.PR2021★ 1 cited

On Dimension-dependent concentration for convex Lipschitz functions in product spaces

Han Huang, Konstantin Tikhomirov

Let $n \geq 1$ , $K > 0$ , and let $X = (X_{1}, X_{2}, \dots, X_{n})$ be a random vector in $R^{n}$ with independent $K$ --subgaussian components. We show that for every $1$ --Lipschitz conve…

cs.DS2021★ 2 cited

Random Graph Matching with Improved Noise Robustness

Cheng Mao, Mark Rudelson, Konstantin Tikhomirov

Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental co…

math.PR2020★ 3 cited

Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs

Konstantin Tikhomirov, Pierre Youssef

Consider the switch chain on the set of $d$ -regular bipartite graphs on $n$ vertices with $3 \leq d \leq n^{c}$ , for a small universal constant $c > 0$ . We prove that the chain satisfi…

math.PR2020

Singularity of sparse Bernoulli matrices

Alexander E. Litvak, Konstantin E. Tikhomirov

Let $M_{n}$ be an $n \times n$ random matrix with i.i.d. Bernoulli(p) entries. We show that there is a universal constant $C \geq 1$ such that, whenever $p$ and $n$ satisfy $C\log n/n\…

cs.IT2019

Distribution of the minimal distance of random linear codes

Jing Hao, Han Huang, Galyna Livshyts +1

In this paper, we study the distribution of the minimal distance (in the Hamming metric) of a random linear code of dimension $k$ in $F_{q}^{n}$ . We provide quantitative estim…

math.PR2019

A remark on the smallest singular value of powers of Gaussian matrices

Han Huang, Konstantin Tikhomirov

Let $n, k \geq 1$ and let $G$ be the $n \times n$ random matrix with i.i.d. standard real Gaussian entries. We show that there are constants $c_{k}, C_{k} > 0$ depending only on $k$ such tha…

math.PR2019

The smallest singular value of inhomogeneous square random matrices

Galyna V. Livshyts, Konstantin Tikhomirov, Roman Vershynin

We show that for an $n \times n$ random matrix $A$ with independent uniformly anti-concentrated entries, such that $E ∣∣ A ∣ ∣_{H S}^{2} \leq K n^{2}$ , the smallest singular value $…

math.FA2019

Hypercontractivity and Lower Deviation Estimates in Normed Spaces

Grigoris Paouris, Konstantin Tikhomirov, Petros Valettas

We consider the problem of estimating small ball probabilities $P {f (G) ⩽ δ E f (G)}$ for sub-additive,positively homogeneous functions $f$ with respect to th…

math.PR2019

Outliers in spectrum of sparse Wigner matrices

Konstantin Tikhomirov, Pierre Youssef

In this paper, we study the effect of sparsity on the appearance of outliers in the semi-circular law. Let $(W_{n})_{n = 1}^{\infty}$ be a sequence of random symmetric matrices such that…

math.PR2019

Estimates for order statistics in terms of quantiles

Alexander E. Litvak, Konstantin Tikhomirov

Let $X_{1}, \dots, X_{n}$ be independent non-negative random variables with cumulative distribution functions $F_{1}, F_{2}, \dots, F_{n}$ , each satisfying certain (rather mild) conditions. W…

math.PR2019

Small ball probability for the condition number of random matrices

Alexander E. Litvak, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann

Let $A$ be an $n \times n$ random matrix with i.i.d. entries of zero mean, unit variance and a bounded subgaussian moment. We show that the condition number $s_{\max}(A)/s_{\min}(A)…

math.PR2018

Singularity of random Bernoulli matrices

Konstantin Tikhomirov

For each $n$ , let $M_{n}$ be an $n \times n$ random matrix with independent $\pm 1$ entries. We show that ${\mathbb P}\{\mbox{$M_n$ is singular}\}=(1/2+o_n(1))^n$, which settles an ol…

math.PR2018

On delocalization of eigenvectors of random non-Hermitian matrices

Anna Lytova, Konstantin Tikhomirov

We study delocalization of null vectors and eigenvectors of random matrices with i.i.d entries. Let $A$ be an $n \times n$ random matrix with i.i.d real subgaussian entries of zero…