# Vishesh Jain

 Department of Statistics, Stanford University Office: Email:   visheshj at stanford dot edu Accessibility

I am a Stein Fellow in the Department of Statistics at Stanford University. Starting Fall 2022, I will be an Assistant Professor in Mathematical Computer Science at the University of Illinois at Chicago. In May, 2020, I received a Ph.D. in mathematics from MIT, where I was fortunate to have been advised by Elchanan Mossel.

I am broadly interested in probability, combinatorics, and theoretical computer science.

## 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. Submitted. [arXiv:2106.04049]
2. Rank deficiency of random matrices, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2103.02467]
3. On the smallest singular value of symmetric random matrices, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2011.02344]
4. Singularity of discrete random matrices, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2010.06554]
5. Sharp invertibility of random Bernoulli matrices, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2010.06553]
6. The smallest singular value of dense random regular digraphs, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2008.04755]
7. Quantitative invertibility of random matrices: a combinatorial perspective. To appear in Discrete Analysis. [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. Entropic Independence in High-Dimensional Expanders: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Polynomials and the Ising Model, joint with Nima Anari, Frederic Koehler, Huy Tuan Pham, and Thuy Duong Vuong. Submitted. [arXiv:2106.04105]
2. Spectral independence, coupling with the stationary distribution, and the spectral gap of the Glauber dynamics, joint with Huy Tuan Pham and Thuy Duong Vuong. Not intended for publication. [arXiv:2105.01201]
3. 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]
4. Towards the sampling Lovász Local Lemma, joint with Huy Tuan Pham and Thuy Duong Vuong. Submitted. [arXiv:2011.12196]
5. 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]
6. Fast and memory-optimal dimension reduction using Kac's walk, joint with Natesh Pillai, Ashwin Sah, Mehtaab Sawhney, and Aaron Smith. Submitted. [arXiv:2003.10069]

### Numerical analysis

1. Optimal and algorithmic norm regularization of random matrices, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [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. 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]
2. Uniformity-independent minimum degree conditions for perfect matchings in hypergraphs, joint with Asaf Ferber. Not intended for publication. [arXiv:1903.12207]
3. 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]
4. Number of 1-factorizations of regular high-degree graphs, joint with Asaf Ferber and Benny Sudakov. Combinatorica, 2020. [Journal][arXiv:1803.10360]
5. 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]
6. 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]

### 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. [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. Submitted. [arXiv:2008.03850]
2. Universality and least singular values of random product matrices: a simplified approach, joint with Rohit Chaudhuri and Natesh Pillai. To appear in Bernoulli. [arXiv:2007.03595]
3. A note on the universality of ESDs of inhomogeneous random matrices, joint with Sandeep Silwal. To appear in Latin American Journal of Probability and Mathematical Statistics (ALEA). [arXiv:2006.05418]
4. The strong circular law: a combinatorial view. To appear in Random Matrices: Theory and Applications. [arXiv:1904.11108]

### Miscellaneous

1. 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]
2. 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]
3. 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.

## Teaching, Mentoring, and TAing

• 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) .