K. Tikhomirov

activity

20152021

most citedRandomized coverings of a convex body with its homothetic copies, and illumination

1 citations · 1 across the 6 of their papers we have counts for

collaborators

18 papers

cs.DS2021

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

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