25 citations · 89 across the 31 of their papers we have counts for
6 papers · 1 filter
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…
On bounded degree graphs with large size-Ramsey numbers
Konstantin Tikhomirov
The size-Ramsey number of a graph is defined as the smallest integer so that there exists a graph with edges such that every -coloring of the edges…
A remark on the Ramsey number of the hypercube
Konstantin Tikhomirov
A well known conjecture of Burr and Erdos asserts that the Ramsey number of the hypercube on vertices is of the order . In this paper, we show that $r(…
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…
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…
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…