I have moved. Redirecting to jainvishesh.github.io.

Vishesh Jain



Simons Institute for the Theory of Computing
Office:
Email:   visheshj at stanford dot edu
CV (Last updated: October 2020)

I am a Simons-Berkeley Research Fellow for the Fall 2020 program on Probability, Geometry, and Computation in High Dimensions. Starting Winter 2021, I will be a Stein Fellow at 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 be advised by Elchanan Mossel. In June, 2015, I received a B.S. in mathematics from Stanford University. I spent the 2013-14 academic year at Math in Moscow.

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

Publications and Preprints

Invertibility of random matrices

  1. On the smallest singular value of symmetric random matrices, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2011.02344]
  2. Singularity of discrete random matrices II, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2010.06554]
  3. Singularity of discrete random matrices I, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2010.06553]
  4. The smallest singular value of dense random regular digraphs, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2008.04755]
  5. Quantitative invertibility of random matrices: a combinatorial perspective. Submitted. [arXiv:1908.11255]
  6. Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices. To appear in Israel Journal of Mathematics. [arXiv:1904.10592]
  7. On the counting problem in inverse Littlewood-Offord theory, joint with Asaf Ferber, Kyle Luh, and Wojciech Samotij. To appear in Journal of London Mathematical Society. [arXiv:1904.10425]
  8. 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 and sampling

  1. Towards the sampling Lovász Local Lemma, joint with Huy Tuan Pham and Thuy Duong Vuong. [arXiv:2011.12196]
  2. Perfectly sampling \(k \geq (8/3 + o(1))\Delta\)-colorings in graphs, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2007.06360]

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. Submitted. [arXiv:2009.01699]
  3. On the real Davies' conjecture, joint with Ashwin Sah and Mehtaab Sawhney. Submitted. [arXiv:2005.08908]

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. Submitted. [arXiv:2007.03595]
  3. A note on the universality of ESDs of inhomogeneous random matrices, joint with Sandeep Silwal. Submitted. [arXiv:2006.05418]
  4. The strong circular law: a combinatorial view. To appear in Random Matrices: Theory and Applications. [arXiv:1904.11108]

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]

Graph decompositions

  1. 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]
  2. Number of 1-factorizations of regular high-degree graphs, joint with Asaf Ferber and Benny Sudakov. Combinatorica, 2020. [Journal][arXiv:1803.10360]
  3. 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]
  4. 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]

Miscellaneous

  1. 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]
  2. 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]
  3. On the number of Hadamard matrices via anti-concentration, joint with Asaf Ferber and Yufei Zhao. Submitted. [arXiv:1808.07222]
  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]

Preprints not intended for publication

  1. The probability of selecting k edge-disjoint Hamilton cycles in the complete graph, joint with Asaf Ferber and Kaarel Haenni. [arXiv:2001.01149]
  2. Uniformity-independent minimum degree conditions for perfect matchings in hypergraphs, joint with Asaf Ferber. [arXiv:1903.12207]
  3. A Counterexample to the "Majority is Least Stable" Conjecture. [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

Teaching, Mentoring, and TAing