Vishesh Jain

Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago Office: SEO 622 Email:   visheshj at uic dot edu Accessibility

Publications and Preprints

Invertibility of random matrices

1. Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial, joint with Asaf Ferber, Ashwin Sah, and Mehtaab Sawhney. Mathematical Proceedings of the Cambridge Philosophical Society, pp. 1--14 (2022). [Journal][arXiv:2106.04049]
2. Rank deficiency of random matrices, joint with Ashwin Sah and Mehtaab Sawhney. Electronic Communications in Probability, vol. 27, paper no. 14, 1-9 (2022). [Journal][arXiv:2103.02467]
3. On the smallest singular value of symmetric random matrices, joint with Ashwin Sah and Mehtaab Sawhney. Combinatorics, Probability and Computing, 31(4), 662-683 (2022). [Journal][arXiv:2011.02344]
4. Singularity of discrete random matrices, joint with Ashwin Sah and Mehtaab Sawhney. Geometric and Functional Analysis (GAFA), 31, pp. 1160-1218 (2021). [Journal][arXiv:2010.06554]
5. Sharp invertibility of random Bernoulli matrices, joint with Ashwin Sah and Mehtaab Sawhney. Merged with above for publication. [arXiv:2010.06553]
6. The smallest singular value of dense random regular digraphs, joint with Ashwin Sah and Mehtaab Sawhney. International Mathematics Research Notices (IMRN), rnab 247 (2021). [Journal][arXiv:2008.04755]
7. Quantitative invertibility of random matrices: a combinatorial perspective. Discrete Analysis, 2021:10. [Journal][arXiv:1908.11255]
8. Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices. Israel Journal of Mathematics, 242, pp. 461--500 (2021). [Journal][arXiv:1904.10592]
9. On the counting problem in inverse Littlewood-Offord theory, joint with Asaf Ferber, Kyle Luh, and Wojciech Samotij. Journal of the London Mathematical Society, vol. 103, issue 4, pp. 1333--1362 (2021). [Journal][arXiv:1904.10425]
10. Singularity of random symmetric matrices -- a combinatorial approach to improved bounds, joint with Asaf Ferber. Forum of Mathematics, Sigma, vol. 7, e22, 29 pages (2019). [Journal][arXiv:1809.04718]

Counting, sampling, and Markov chains

1. Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses, joint with Nima Anari, Frederic Koehler, Huy Tuan Pham, and Thuy Duong Vuong. Submitted. [arXiv:2307.10466]
2. Optimal mixing of the down-up walk on independent sets of a given size, joint with Marcus Michelen, Huy Tuan Pham, and Thuy Duong Vuong. Submitted. [arXiv:2305.06198]
3. Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain, joint with Huy Tuan Pham and Thuy Duong Vuong. Comptes Rendus Mathematique. vol. 361, pp. 869--876 (2023). [Journal][arXiv:2203.03858]
4. Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities, joint with Nima Anari, Frederic Koehler, Huy Tuan Pham, and Thuy Duong Vuong. To appear in the 54th ACM Symposium on the Theory of Computing (STOC 2022). [arXiv:2111.03247]
5. Approximate counting and sampling via local central limit theorems, joint with Will Perkins, Ashwin Sah and Mehtaab Sawhney. To appear in the 54th ACM Symposium on the Theory of Computing (STOC 2022). [arXiv:2108.01161]
6. Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models, joint with Nima Anari, Frederic Koehler, Huy Tuan Pham, and Thuy Duong Vuong. To appear in the 54th ACM Symposium on the Theory of Computing (STOC 2022). [arXiv:2106.04105]
7. Spectral independence, coupling, and the spectral gap of the Glauber dynamics, joint with Huy Tuan Pham and Thuy Duong Vuong. To appear in Information Processing Letters. [arXiv:2105.01201]
8. On the sampling Lovász Local Lemma for atomic constraint satisfaction problems, joint with Huy Tuan Pham and Thuy Duong Vuong. Submitted. [arXiv:2102.08342]
9. Towards the sampling Lovász Local Lemma, joint with Huy Tuan Pham and Thuy Duong Vuong. To appear in 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021). [arXiv:2011.12196]
10. Perfectly sampling \(k \geq (8/3 + o(1))\Delta\)-colorings in graphs, joint with Ashwin Sah and Mehtaab Sawhney. 53rd ACM Symposium on the Theory of Computing (STOC 2021). [Conference][arXiv:2007.06360]
11. Fast and memory-optimal dimension reduction using Kac's walk, joint with Natesh Pillai, Ashwin Sah, Mehtaab Sawhney, and Aaron Smith. To appear in Annals of Applied Probability. [arXiv:2003.10069]

Numerical analysis

1. Optimal and algorithmic norm regularization of random matrices, joint with Ashwin Sah and Mehtaab Sawhney. To appear in Proceedings of the American Mathematical Society. [arXiv:2012.00175]
2. On the smoothed analysis of the smallest singular value with discrete noise, joint with Ashwin Sah and Mehtaab Sawhney. To appear in Bulletin of the London Mathematical Society. [arXiv:2009.01699]
3. On the real Davies' conjecture, joint with Ashwin Sah and Mehtaab Sawhney. To appear in Annals of Probability. [arXiv:2005.08908]

Graph decompositions

1. Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings, joint with Huy Tuan Pham. [arXiv:2212.06109]
2. Towards the linear arboricity conjecture, joint with Asaf Ferber and Jacob Fox. Journal of Combinatorial Theory, Series B, Volume 142, May 2020, Pages 56--79. [Journal][arXiv:1809.04716]
3. Number of 1-factorizations of regular high-degree graphs, joint with Asaf Ferber and Benny Sudakov. Combinatorica, 2020. [Journal][arXiv:1803.10360]
4. On the k-planar local crossing number, joint with John Asplund, Thao Do, and Arran Hamm. Discrete Mathematics, vol. 342, issue 4, pp. 927--933 (2019). [Journal][arXiv:1804.02117]
5. 1-factorizations of pseudorandom graphs, joint with Asaf Ferber. 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018). Random Structures and Algorithms. [Conference][Journal][arXiv:1803.10361]
6. The probability of selecting k edge-disjoint Hamilton cycles in the complete graph, joint with Asaf Ferber and Kaarel Haenni. Not intended for publication. [arXiv:2001.01149]
7. Uniformity-independent minimum degree conditions for perfect matchings in hypergraphs, joint with Asaf Ferber. Not intended for publication. [arXiv:1903.12207]

Mean-field approximation

1. Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective, joint with Frederic Koehler and Andrej Risteski. 51st ACM Symposium on the Theory of Computing (STOC 2019). [Conference][arXiv:1808.07226]
2. The Vertex Sample Complexity of Free Energy is Polynomial, joint with Frederic Koehler and Elchanan Mossel. 31st Annual Conference on Learning Theory (COLT 2018). [Conference][arXiv:1802.06129]
3. The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity, joint with Frederic Koehler and Elchanan Mossel. 31st Annual Conference on Learning Theory (COLT 2018). [Conference][arXiv:1802.06126]

Anticoncentration

1. Anticoncentration versus the number of subset sums, joint with Ashwin Sah and Mehtaab Sawhney. Advances in Combinatorics, 2021:6. [Journal][arXiv:2101.07726]
2. On the number of Hadamard matrices via anti-concentration, joint with Asaf Ferber and Yufei Zhao. To appear in Combinatorics, Probability and Computing. [arXiv:1808.07222]

Universality of ESDs

1. Circular law for random block band matrices with genuinely sublinear bandwidth, joint with Indrajit Jana, Kyle Luh, and Sean O'Rourke. To appear in Journal of Mathematical Physics. [arXiv:2008.03850]
2. Universality and least singular values of random product matrices: a simplified approach, joint with Rohit Chaudhuri and Natesh Pillai. Bernoulli, vol. 27, no. 4, pages 2519-2531 (2021). [Journal][arXiv:2007.03595]
3. A note on the universality of ESDs of inhomogeneous random matrices, joint with Sandeep Silwal. Latin American Journal of Probability and Mathematical Statistics (ALEA), vol. 18, 1047–1059 (2021). [Journal][arXiv:2006.05418]
4. The strong circular law: a combinatorial view. Random Matrices: Theory and Applications, vol. 10, No. 03, 2150031 (2021). [Journal][arXiv:1904.11108]

Miscellaneous

1. Spencer's theorem in nearly input-sparsity time, joint with Ashwin Sah and Mehtaab Sawhney. To be submitted. [arXiv:2206.04549]
2. Optimal minimization of the covariance loss, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2205.01773]
3. Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation, joint with Frederic Koehler, Jingbo Liu, and Elchanan Mossel. 32nd Annual Conference on Learning Theory (COLT 2019). [Conference][arXiv:1905.10031]
4. On discontinuity of planar optimal transport maps, joint with Otis Chodosh, Michael Lindsey, Lyuboslav Panchev, and Yanir Rubinstein. Journal of Topology and Analysis, vol. 7, no. 2, pp. 239--260 (2015). [Journal][arXiv:1312.2929]
5. A Counterexample to the "Majority is Least Stable" Conjecture. Not intended for publication. [arXiv:1703.07657]

Expository

1. An expanded version of a MathOverflow comment by Nazarov, giving a simple proof of an inequality due to Feige.
2. Unedited and informal notes from a three-hour reading group talk on the Balogh-Morris-Samotij proof of the hypergraph containers theorem .
3. Unedited and informal notes from a two-hour reading group talk on Peter Keevash's Counting Designs.

Upcoming talks and conferences

Teaching, Mentoring, and TAing

• In Spring 2023, I taught MCS 421 (Combinatorics) and MCS 425 (Codes and Cryptography).
• In Winter 2022, I taught STATS 217 (Introduction to Stochastic Processes I).
• In Fall 2021, I taught STATS 60 (Introduction to Statistical Methods).
• In Spring 2021, I taught STATS 60 (Introduction to Statistical Methods).
• In Winter 2021, I taught STATS 217 (Introduction to Stochastic Processes I).
• In Spring 2020, I was a grader for 18.676 (Stochastic Calculus) and 18.455 (Advanced Combinatorial Optimization).
• In Summer 2019, I was a mentor for UROP+.
• In Spring 2019, I was a grader for 18.218 (Probabilistic Method in Combinatorics).
• In Fall 2018, I was a recitation instructor for 18.600 (Probability & Random Variables). Recitation handouts are available here.
• In Spring 2018, I was a recitation instructor for 18.04 (Complex Analysis with Applications). Recitation handouts are available here.
• In Fall 2017, I graded for 18.155 (Differential Analysis I).
• In Spring 2017, I graded for 18.117 (Hodge Theory).
• In IAP 2017, I was a mentor for the MIT math department's Directed Reading Program.
• In Fall 2016, I graded for 18.965 (Geometry of Manifolds I).
• In Summer 2016, I was a mentor for the Research Science Institute (RSI) .