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

Showing 2021Show all

4 papers · 1 filter

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…