Konstantin Tikhomirov
Email: ktikhomi at andrew dot cmu dot edu
Some publications and preprints
| Paper | Statement of AI Use |
|---|---|
| The threshold for online balancing of i.i.d. binary vectors. arXiv:2609.14975 | The discrepancy lower bound as well as the upper bound in the very sparse regime were proved without AI assistance. Subsequently, also without AI, the upper bound was extended to the full range of sparsity considered in the current paper under the simplifying assumption that the non-zero entries of incoming vectors are independent and uniform on {-1,1}, rather than deterministically 1. The random signing condition was removed with help of ChatGPT. Further, ChatGPT suggested and implemented potential function approach in place of an earlier multiscale majority argument. |
| Online Permutation Embedding: Optimal Stopping and Scaling Laws. arXiv:2608.19050 | Original proof of the recursive formula for the expectation of the optimal online embedding time was developed without AI assistance and was based on a discretization argument and a reduction to 231-avoiding permutations. The much more concise martingale-based argument was obtained with help of ChatGPT. |
| Level-set entropy and sparse randomized embeddings. arXiv:2607.23017 [To be revised] | Architecture of the proof (including the use of level set entropy estimates; decomposition into light and heavy columns; canonical and reduced flat contributions; two level partitions) is developed without AI assistance. ChatGPT contribution to the proofs is at the level of a co-author. The proof of the (key) entropy lemma for the level sets is generated by ChatGPT. |
| Online Beck--Fiala Down to Logarithmic Sparsity. arXiv:2607.14238 | All proofs are ChatGPT-generated. Authors wrote high-level prompts and revised ChatGPT output. |
| Well-invertible column subsets of sparse matrices are rare. arXiv:2607.05384 | In the setting of random matrices, the main result of the work was derived by the authors without AI assistance. Subsequent generalization to deterministic matrices with the column overlap condition was obtained with substantial use of ChatGPT. |
| Cotype of random polytopes. arXiv:2603.04749 [To be revised] | No AI use |
Before 2026
- 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 [Superseded by arXiv:2609.14975]
- 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, Combinatorica 46 (2026), Paper No. 20. 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, J. Theoret. Probab. 39 (2026), Paper No. 44. arXiv:2401.07852
- K.Tikhomirov, On pseudospectrum of inhomogeneous non-Hermitian random matrices. arXiv:2307.08211
- K.Tikhomirov, On the probability that the convex hull of random points contains the origin, Pure Appl. Funct. Anal. 10 (2025), no. 6, 1537-1556. 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 lpn-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 Rn 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∞n 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.