Source author record

Konstantin Tikhomirov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math.CO Data Structures and Algorithms Information Theory Machine Learning math.IT math.MG math.ST Statistics Theory

Catalog footprint

Research overview

11works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Exact Matching of Random Graphs with Constant Correlation

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 problem. Let $G$ and $G'$ be $G(n, p)$ Erdős--Rényi graphs marginally, identified with their adjacency matrices. Assume that $G$ and $G'$ are correlated such that $\mathbb{E}[G_{ij} G'_{ij}] = p(1-α)$ . For a permutation $π$ representing a latent matching between the vertices of $G$ and $G'$ , denote by $G^π$ the graph obtained from permuting the vertices of $G$ by $π$ . Observing $G^π$ and $G'$ , we aim to recover the matching $π$ . In this work, we show that for every $\varepsilon \in (0,1]$ , there is $n_0>0$ depending on $\varepsilon$ and absolute constants $α_0, R > 0$ with the following property. Let $n \ge n_0$ , $(1+\varepsilon) \log n \le np \le n^{\frac{1}{R \log \log n}}$ , and $0 < α< \min(α_0,\varepsilon/4)$ . There is a polynomial-time algorithm $F$ such that $\mathbb{P}\{F(G^π,G')=π\}=1-o(1)$ . This is the first polynomial-time algorithm that recovers the exact matching between vertices of correlated Erdős--Rényi graphs with constant correlation with high probability. The algorithm is based on comparison of partition trees associated with the graph vertices.

preprint2022arXiv

Quantitative invertibility of non-Hermitian random matrices

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 this survey, we consider recent developments in the study of quantitative invertibility in the non-Hermitian setting, and review some applications of this line of research.

preprint2022arXiv

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

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 comparison of the MLSI Dirichlet forms is a well known obstacle in the theory of Markov chains. We approach this problem by introducing a {\it regularized} MLSI constant which, under some assumptions, has the same order of magnitude as the usual MLSI constant yet is amenable for comparison and thus considerably simpler to estimate in certain cases. As an application of this general comparison procedure, we provide a sharp estimate of the MLSI constant of the switch chain on the the set of simple bipartite regular graphs of size $n$ with a fixed degree $d$ . Our estimate implies that the total variation mixing time of the switch chain is of order $O_d(n\log n)$ . The result is optimal up to a multiple depending on $d$ and resolves a long-standing open problem. We expect that the MLSI comparison technique implemented in this paper will find further applications.

preprint2022arXiv

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

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 satisfies a Poincaré inequality with a constant of order $O(nd)$ ; moreover, when $d$ is fixed, we establish a log-Sobolev inequality for the chain with a constant of order $O_d(n\log n)$ . We show that both results are optimal. The Poincaré inequality implies that in the regime $3\leq d\leq n^c$ the mixing time of the switch chain is at most $O\big((nd)^2 \log(nd)\big)$ , improving on the previously known bound $O\big((nd)^{13} \log(nd)\big)$ due to Kannan, Tetali and Vempala and $O\big(n^7d^{18} \log(nd)\big)$ obtained by Dyer et al. The log-Sobolev inequality that we establish for constant $d$ implies a bound $O(n\log^2 n)$ on the mixing time of the chain which, up to the $\log n$ factor, captures a conjectured optimal bound. Our proof strategy relies on building, for any fixed function on the set of $d$ -regular bipartite simple graphs, an appropriate extension to a function on the set of multigraphs given by the configuration model. We then establish a comparison procedure with the well studied random transposition model in order to obtain the corresponding functional inequalities. While our method falls into a rich class of comparison techniques for Markov chains on different state spaces, the crucial feature of the method - dealing with chains with a large distortion between their stationary measures - is a novel addition to the theory.

preprint2020arXiv

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

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 that the smallest singular value of $G^k$ satisfies $c_k\,t\leq {\mathbb P}\big\{s_{\min}(G^k)\leq t^k\,n^{-1/2}\big\}\leq C_k\,t,\quad t\in(0,1],$ and, furthermore, $c_k/t\leq {\mathbb P}\big\{\|G^{-k}\|_{HS}\geq t^k\,n^{1/2}\big\}\leq C_k/t,\quad t\in[1,\infty),$ where $\|\cdot\|_{HS}$ denotes the Hilbert-Schmidt norm.

preprint2020arXiv

Distribution of the minimal distance of random linear codes

In this paper, we study the distribution of the minimal distance (in the Hamming metric) of a random linear code of dimension $k$ in $\mathbb{F}_q^n$ . We provide quantitative estimates showing that the distribution function of the minimal distance is close ({\it{}superpolynomially} in $n$ )to the cumulative distribution function of the minimum of $(q^k-1)/(q-1)$ independent binomial random variables with parameters $\frac{1}{q}$ and $n$ . The latter, in turn, converges to a Gumbel distribution at integer points when $\frac{k}{n}$ converges to a fixed number in $(0,1)$ . Our result confirms in a strong sense that apart from identification of the weights of proportional codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimal code weight. As a corollary of the main result, we obtain an improvement of the Gilbert--Varshamov bound for $2<q<49$ .

preprint2020arXiv

Invertibility via distance for non-centered random matrices with continuous distributions

Let $A$ be an $n\times n$ random matrix with independent rows $R_1(A),\dots,R_n(A)$ , and assume that for any $i\leq n$ and any three-dimensional linear subspace $F\subset {\mathbb R}^n$ the orthogonal projection of $R_i(A)$ onto $F$ has distribution density $ρ(x):F\to{\mathbb R}_+$ satisfying $ρ(x)\leq C_1/\max(1,\|x\|_2^{2000})$ ( $x\in F$ ) for some constant $C_1>0$ . We show that for any fixed $n\times n$ real matrix $M$ we have ${\mathbb P}\{s_{\min}(A+M)\leq t n^{-1/2}\}\leq C'\, t,\quad\quad t>0,$ where $C'>0$ is a universal constant. In particular, the above result holds if the rows of $A$ are independent centered log-concave random vectors with identity covariance matrices. Our method is free from any use of covering arguments, and is principally different from a standard approach involving a decomposition of the unit sphere and coverings, as well as an approach of Sankar-Spielman-Teng for non-centered Gaussian matrices.

preprint2016arXiv

Adjacency matrices of random digraphs: singularity and anti-concentration

Let ${\mathcal D}_{n,d}$ be the set of all $d$ -regular directed graphs on $n$ vertices. Let $G$ be a graph chosen uniformly at random from ${\mathcal D}_{n,d}$ and $M$ be its adjacency matrix. We show that $M$ is invertible with probability at least $1-C\ln^{3} d/\sqrt{d}$ for $C\leq d\leq cn/\ln^2 n$ , where $c, C$ are positive absolute constants. To this end, we establish a few properties of $d$ -regular directed graphs. One of them, a Littlewood-Offord type anti-concentration property, is of independent interest. Let $J$ be a subset of vertices of $G$ with $|J|\approx n/d$ . Let $δ_i$ be the indicator of the event that the vertex $i$ is connected to $J$ and define $δ= (δ_1, δ_2, ..., δ_n)\in \{0, 1\}^n$ . Then for every $v\in\{0,1\}^n$ the probability that $δ=v$ is exponentially small. This property holds even if a part of the graph is "frozen".

preprint2016arXiv

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

We present a probabilistic model of illuminating a convex body by independently distributed light sources. In addition to recovering C.A. Rogers' upper bounds for the illumination number, we improve previous estimates of J. Januszewski and M. Naszódi for a generalized version of the illumination parameter.

preprint2015arXiv

Minimax of an n-dimensional Brownian motion

For some absolute constants $c$ , $n_0$ and any $n\geq n_0$ , we show that with probability close to one the convex hull of the $n$ -dimensional Brownian motion ${\rm conv}\{BM_n(t):\, t\in[1,2^{cn}]\}$ does not contain the origin. The result can be interpreted as an estimate of the minimax of the Gaussian process $\{ \langle \bar{u},BM_n(t)\rangle,\, \bar{u}\in S^{n-1},\, t\in [1,2^{cn}]\}$ .

preprint2014arXiv

The limit of the smallest singular value of random matrices with i.i.d. entries

Let $\{a_{ij}\}$ $(1\le i,j<\infty)$ be i.i.d. real valued random variables with zero mean and unit variance and let an integer sequence $(N_m)_{m=1}^\infty$ satisfy $m/N_m\longrightarrow z$ for some $z\in(0,1)$ . For each $m\in{\mathbb N}$ denote by $A_m$ the $N_m\times m$ random matrix $(a_{ij})$ $(1\le i\le N_m,1\le j\le m)$ and let $s_{m}(A_m)$ be its smallest singular value. We prove that the sequence $\bigl({N_m}^{-1/2} s_{m}(A_m)\bigr)_{m=1}^\infty$ converges to $1-\sqrt{z}$ almost surely. Our result does not require boundedness of any moments of $a_{ij}$ 's higher than the $2$ -nd and resolves a long standing question regarding the weakest moment assumptions on the distribution of the entries sufficient for the convergence to hold.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Konstantin Tikhomirov

Research overview

Is this your work?

11 publications

Exact Matching of Random Graphs with Constant Correlation

Quantitative invertibility of non-Hermitian random matrices

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

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

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

Distribution of the minimal distance of random linear codes

Invertibility via distance for non-centered random matrices with continuous distributions

Adjacency matrices of random digraphs: singularity and anti-concentration

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

Minimax of an n-dimensional Brownian motion

The limit of the smallest singular value of random matrices with i.i.d. entries

See the researcher in context

Building this map preview