Konstantin Tikhomirov Carnegie Mellon University Email: ktikhomi at andrew dot cmu dot edu I work in discrete probability, combinatorics, and convex geometry, with applications to data analysis. CV

Some publications and preprints:


• D. J. Altschuler, P. Dodos, K. Tikhomirov, K. Tyros, Metric Poincare inequalities for graphs. arXiv:2509.25489


• D. J. Altschuler, K. Tikhomirov, A threshold for online balancing of sparse i.i.d. vectors. arXiv:2509.02432


• D. J. Altschuler, K. Tikhomirov, Metric dimension reduction modulus for superlogarithmic distortion. arXiv:2507.02785


• D. J. Altschuler, P. Dodos, K. Tikhomirov, K. Tyros, Discrete Poincare inequalities and universal approximators for random graphs. arXiv:2506.17433


• D. J. Altschuler, P. Dodos, K. Tikhomirov, K. Tyros, A universal threshold for geometric embeddings of trees. arXiv:2504.15212


• D. J. Altschuler, K. Tikhomirov, Universal geometric non-embedding of random regular graphs. arXiv:2501.09142


• D. J. Altschuler, P. Dodos, K. Tikhomirov, K. Tyros, A combinatorial approach to nonlinear spectral gaps. arXiv:2410.04394


• M. Bakhshi, J. Ostrowski, K. Tikhomirov, On the optimal objective value of random linear programs. arXiv:2401.17530


• D. J. Altschuler, P. Oliveira Santos, K. Tikhomirov, P. Youssef, On spectral outliers of inhomogeneous symmetric random matrices. arXiv:2401.07852


• K.Tikhomirov, On pseudospectrum of inhomogeneous non-Hermitian random matrices. arXiv:2307.08211


• K.Tikhomirov, On the probability that convex hull of random points contains the origin. arXiv:2304.13133


• K.Tikhomirov, On bounded degree graphs with large size-Ramsey numbers, Combinatorica 44 (2024), no. 1, 9-14. arXiv:2210.05818


• K.Tikhomirov, A remark on the Ramsey number of the hypercube, European J. Combin. 120 (2024), Paper No. 103954, 24 pp. arXiv:2208.14568


• K.Tikhomirov, P.Youssef, Regularized modified log-Sobolev inequalities, and comparison of Markov chains, Ann. Probab. 52 (2024), no. 4, 1201-1224. arXiv:2206.12477


• H.Huang, K.Tikhomirov, Average-case analysis of the Gaussian Elimination with Partial Pivoting, Probab. Theory Related Fields 189 (2024), 501-567. arXiv:2206.01726


• K.Tikhomirov, Quantitative invertibility of non-Hermitian random matrices, Proc. Int. Cong. Math. 2022, Vol. 4, pp. 3292--3313. EMS Press, Berlin, 2023. arXiv:2206.00601


• C.Mao, M.Rudelson, K.Tikhomirov, Exact Matching of Random Graphs with Constant Correlation, Probab. Theory Related Fields 186 (2023), no. 1-2, 327-389. arXiv:2110.05000


• H.Huang, K.Tikhomirov, Shotgun assembly of unlabeled Erdos-Renyi graphs, Probab. Theory Related Fields 192 (2025), no. 1-2, 575-624. arXiv:2108.09636


• H.Huang, K.Tikhomirov, On dimension-dependent concentration for convex Lipschitz functions in product spaces, Electron. J. Probab. 28 (2023), Paper No. 63, 23 pp. arXiv:2106.06121


• C.Mao, M.Rudelson, K.Tikhomirov, Random Graph Matching with Improved Noise Robustness, COLT 2021. arXiv:2101.11783


• K.Tikhomirov, P.Youssef, Sharp Poincare and log-Sobolev inequalities for the switch chain on regular bipartite graphs, Probab. Theory Related Fields 185 (2023), no.1-2, 89-184. arXiv:2007.02729


• A.E.Litvak, K.Tikhomirov, Singularity of sparse Bernoulli matrices, Duke Math. J. 171 (2022), no.5, 1135-1233. arXiv:2004.03131


• J.Hao, H.Huang, G.Livshyts, K.Tikhomirov, Distribution of the minimal distance of random linear codes, IEEE Trans. Inform. Theory 68 (2022), no. 10, 6388-6401. arXiv:1912.12833


• H.Huang, K.Tikhomirov, A remark on the smallest singular value of powers of Gaussian matrices, Electron. Commun. Probab. 25 (2020), Paper No. 10, 8 pp. arXiv:1910.03702


• G.Livshyts, K.Tikhomirov, R.Vershynin, The smallest singular value of inhomogeneous square random matrices, Ann. Probab. 49 (2021), no. 3, 1286-1309. arXiv:1909.04219


• G.Paouris, K.Tikhomirov, P.Valettas, Hypercontractivity, and Lower Deviation Estimates in Normed Spaces, Ann. Probab. 50 (2022), no. 2, 688-734. arXiv:1906.03208


• K.Tikhomirov, P.Youssef, Outliers in spectrum of sparse Wigner matrices, Random Structures Algorithms 58 (2021), no. 3, 517-605. arXiv:1904.07985


• A.E.Litvak, K.Tikhomirov, N.Tomczak-Jaegermann, Small ball probability for the condition number of random matrices,
  in Geometric aspects of functional analysis. Vol. II, 125-137, Lecture Notes in Math., 2266, Springer, Cham [2020]. arXiv:1901.08655


• K.Tikhomirov, Singularity of random Bernoulli matrices, Ann. of Math. (2) 191 (2020), no. 2, 593-634. arXiv:1812.09016


• A.Lytova, K.Tikhomirov, On delocalization of eigenvectors of random non-Hermitian matrices, Probab. Theory Related Fields 177 (2020), no. 1-2, 465-524. arXiv:1810.01590


• M.Rudelson, K.Tikhomirov, The sparse circular law under minimal assumptions,
  Geom. Funct. Anal. 29 (2019), no. 2, 561-637. arXiv:1807.08085


• K.Tikhomirov, On the Banach-Mazur distance to cross-polytope, Adv. Math. 345 (2019), 598-617. arXiv:1804.08212


• A.E.Litvak, A.Lytova, K.Tikhomirov, N.Tomczak-Jaegermann, P.Youssef,
  The rank of random regular digraphs of constant degree, J. Complexity 48 (2018), 103-110. arXiv:1801.05577


• A.E.Litvak, A.Lytova, K.Tikhomirov, N.Tomczak-Jaegermann, P.Youssef,
  Circular law for sparse random regular digraphs, J. Eur. Math. Soc. (JEMS) 23 (2021), no. 2, 467-501. arXiv:1801.05576


• A.E.Litvak, A.Lytova, K.Tikhomirov, N.Tomczak-Jaegermann, P.Youssef,
  Structure of eigenvectors of random regular digraphs, Trans. Amer. Math. Soc. 371 (2019), no. 11, 8097-8172. arXiv:1801.05575


• G.Livshyts, K.Tikhomirov, Cube is a strict local maximizer for the illumination number, Discrete Comput. Geom. 63 (2020), no. 1, 209-228. arXiv:1710.05070


• K.Tikhomirov, Invertibility via distance for non-centered random matrices with continuous distributions, Random Structures Algorithms 57 (2020), no. 2, 526-562. arXiv:1707.09656


• A.E.Litvak, A.Lytova, K.Tikhomirov, N.Tomczak-Jaegermann, P.Youssef,
  The smallest singular value of a shifted d-regular random square matrix, Probab. Theory Related Fields 173 (2019), no. 3-4, 1301-1347. arXiv:1707.02635


• A.Lytova, K.Tikhomirov, The variance of the l_pⁿ-norm of the Gaussian vector, and Dvoretzky's theorem, Algebra i Analiz 30 (2018), no. 4, 107-139. arXiv:1705.05052


• K.Tikhomirov, Superconcentration, and randomized Dvoretzky's theorem for spaces with 1-unconditional bases, J. Funct. Anal. 274 (2018), no. 1, 121-151. arXiv:1702.00859


• K.Tikhomirov, P.Youssef, The spectral gap of dense random regular graphs, Ann. Probab. 47 (2019), no. 1, 362-419. arXiv:1610.01765


• K.Tikhomirov, P.Youssef, On the norm of a random jointly exchangeable matrix, J Theor Probab (2018). https://doi.org/10.1007/s10959-018-0844-y arXiv:1610.01751


• A.E.Litvak, K.Tikhomirov, Order statistics of vectors with dependent coordinates, and the Karhunen-Loeve basis,
  Ann. Appl. Probab. 28 (2018), no. 4, 2083-2104. arXiv:1609.02126


• C.Bordenave, P.Caputo, D.Chafaï, K.Tikhomirov, On the spectral radius of a random matrix: an upper bound without fourth moment,
  Ann. Probab. 46 (2018), no. 4, 2268-2286. arXiv:1607.05484


• K.Tikhomirov, Illumination of convex bodies with many symmetries, Mathematika (63), 2017, No. 2, 372-382. arXiv:1606.08976


• G.Livshyts, K.Tikhomirov, Randomized coverings of a convex body with its homothetic copies, and illumination, Proc. Amer. Math. Soc., to appear. arXiv:1606.08876


• K.Tikhomirov, Sample covariance matrices of heavy-tailed distributions, Int. Math. Res. Not. IMRN 2018, no. 20, 6254-6289. arXiv:1606.03557


• A.E.Litvak, A.Lytova, K.Tikhomirov, N.Tomczak-Jaegermann, P.Youssef,
  Adjacency matrices of random digraphs: singularity and anti-concentration, J. Math. Anal. Appl. (445), 2017, No. 2, 1447-1491. arXiv:1511.00113


• D.Chafaï, K.Tikhomirov, On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence,
  Probab. Theory Relat. Fields 170 (2018), no. 3-4, 847-889. arXiv:1509.02231


• E.Rebrova, K.Tikhomirov, Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries,
  Israel J. Math. 227 (2018), no. 2, 507-544. arXiv:1508.06690


• K.Tikhomirov, P.Youssef, When does a discrete-time random walk in Rⁿ absorb the origin into its convex hull?
  Ann. Probab. (45), 2017, No. 2, 965-1002. arXiv:1410.0458


• S.V. Astashkin, G.P. Curbera, K.E. Tikhomirov, On the existence of RUC systems in rearrangement invariant spaces,
  Math. Nachr. 289 (2016), no. 2-3, 175-186.


• K.Tikhomirov, The limit of the smallest singular value of random matrices with i.i.d. entries, Adv. Math. (284), 2015, 1-20. arXiv:1410.6263


• K.Tikhomirov, The smallest singular value of random rectangular matrices with no moment assumptions on entries,
  Israel J. Math. 212 (2016), no. 1, 289-314. arXiv:1409.7975.


• K.Tikhomirov, On the Distance of Polytopes with Few Vertices to the Euclidean Ball, Discrete Comput. Geom. 53 (2015), no. 1, 173-181.


• K.Tikhomirov, The Randomized Dvoretzky's Theorem in l_∞ⁿ and the χ-Distribution,
  Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, Vol. 2116 (2014), 455-463.


• S.V.Astashkin, L.Maligranda, K.Tikhomirov, New examples of K-monotone weighted Banach couples.
  Studia Math. 218 (2013), no. 1, 55-88. arXiv:1206.1244


• K.Tikhomirov, Almost Euclidean sections in symmetric spaces and concentration of order statistics, J. Funct. Anal. 265 (2013), no. 9, 2074-2088.