Ashwin Sah

Research

Publications

  • Dor Minzer, A. Sah, and Mehtaab Sawhney. On Perfectly Friendly Bisections of Random Graphs. Annals of Probability, accepted.
    (pdf) (arXiv)

  • A. Sah and Mehtaab Sawhney. The intransitive dice kernel: \(\frac{\mathbf{1}_{x\ge y}-\mathbf{1}_{x\le y}}{2} - \frac{3(x-y)(1-xy)}{4}\). Probability Theory and Related Fields, accepted.
    (pdf) (arXiv)

  • A. Sah and Mehtaab Sawhney. Distribution of the threshold for the symmetric perceptron. IEEE Symposium on Foundations of Computer Science 2023, accepted.
    (pdf) (arXiv)

  • Matthew Kwan, A. Sah, Lisa Sauermann, and Mehtaab Sawhney. Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture. Forum of Mathematics, Pi, 11:e21, 1-74.
    (pdf) (online) (arXiv)

  • A. Sah and Mehtaab Sawhney. Subgraph distributions in dense random regular graphs. Compositio Mathematica, 159, 2125-2148.
    (pdf) (online) (arXiv)

  • A. Sah, Mehtaab Sawhney, and Yufei Zhao. Paths of given length in tournaments. Combinatorial Theory, accepted. (Appendix by Dingding Dong and Tomasz Ślusarczyk)
    (pdf) (arXiv)

  • A. Sah, Mehtaab Sawhney, and Michael Simkin. Threshold for Steiner triple systems. Geometric and Functional Analysis, 33(4), 1141-1172.
    (pdf) (online) (arXiv)

  • Assaf Naor, A. Sah, Mehtaab Sawhney, and Yufei Zhao. Cayley graphs that have a quantum ergodic eigenbasis. Israel Journal of Mathematics, 256, 599-617.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. Spencer's theorem in nearly input-sparsity time. ACM-SIAM Symposium on Discrete Algorithms 2023, 3946-3958.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. Optimal minimization of the covariance loss. IEEE Transactions on Information Theory, 69(2), 813-818.
    (pdf) (online) (arXiv)

  • Asaf Ferber, Matthew Kwan, Bhargav Narayanan, A. Sah, and Mehtaab Sawhney. Friendly bisections of random graphs. Communications of the American Mathematical Society, 2, 380-416.
    (pdf) (online) (arXiv)

  • Matthew Kwan, A. Sah, and Mehtaab Sawhney. Enumerating Matroids and Linear Spaces. Comptes Rendus Mathématique, 361, 565-575.
    (pdf) (online) (arXiv)

  • Asaf Ferber, A. Sah, Mehtaab Sawhney, and Yizhe Zhu. Sparse recovery properties of discrete random matrices. Combinatorics, Probability and Computing, 32(2), 316-325.
    (pdf) (online) (arXiv)

  • Matthew Kwan, A. Sah, Mehtaab Sawhney, and Michael Simkin. Substructures in Latin squares. Israel Journal of Mathematics, 256, 363-416.
    (pdf) (online) (arXiv)

  • A. Sah and Mehtaab Sawhney. Enumerating coprime permutations. Mathematika, 68(4), 1120-1134.
    (pdf) (online) (arXiv)

  • Asaf Ferber, Matthew Kwan, A. Sah, and Mehtaab Sawhney. Singularity of the \(k\)-core of a random graph. Duke Mathematical Journal, 172(7), 1293-1332.
    (pdf) (online) (arXiv)

  • Asaf Ferber, Vishesh Jain, A. Sah, and Mehtaab Sawhney. Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial. Mathematical Proceedings of the Cambridge Philosophical Society, 174(2), 233-246.
    (pdf) (online) (arXiv)

  • A. Sah and Mehtaab Sawhney. Majority Dynamics: The Power of One. Israel Journal of Mathematics, accepted.
    (pdf) (arXiv)

  • A. Sah. Diagonal Ramsey via effective quasirandomness. Duke Mathematical Journal, 172(3), 545-567.
    (pdf) (online) (arXiv) (Article in Quanta Magazine)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. Rank deficiency of random matrices. Electronic Communications in Probability, 27, 1-9.
    (pdf) (online) (arXiv)

  • Janardhan Kulkarni, Yang P. Liu, A. Sah, Mehtaab Sawhney, and Jakub Tarnawski. Online Edge Coloring via Tree Recurrences and Correlation Decay. ACM Symposium on Theory of Computing 2022, 104-116.
    (pdf) (online) (arXiv)

  • Vishesh Jain, Will Perkins, A. Sah, and Mehtaab Sawhney. Approximate counting and sampling via local central limit theorems. ACM Symposium on Theory of Computing 2022, 1473-1486.
    (pdf) (online) (arXiv)

  • Vishesh Jain, Natesh S. Pillai, A. Sah, Mehtaab Sawhney, and Aaron Smith. Fast and memory-optimal dimension reduction using Kac's walk. The Annals of Applied Probability, 32(5), 4038-4064.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. Optimal and algorithmic norm regularization of random matrices. Proceedings of the American Mathematical Society, 150(10), 4503-4518.
    (pdf) (online) (arXiv)

  • Matthew Kwan, A. Sah, and Mehtaab Sawhney. Large deviations in random Latin squares. Bulletin of the London Mathematical Society, 54(4), 1420-1438.
    (pdf) (online) (arXiv)

  • Yang P. Liu, A. Sah, and Mehtaab Sawhney. A Gaussian fixed point random walk. Innovations in Theoretical Computer Science 2022, 101:1-10. Best Student Paper.
    (pdf) (online) (arXiv)

  • Aaron Berger, A. Sah, Mehtaab Sawhney, and Jonathan Tidor. Non-classical polynomials and the inverse theorem. Mathematical Proceedings of the Cambridge Philosophical Society, 173(3), 525-537.
    (pdf) (online) (arXiv)

  • Aaron Berger, A. Sah, Mehtaab Sawhney, and Jonathan Tidor. Popular differences for matrix patterns. Transactions of the American Mathematical Society, 375(4), 2677-2704.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. On the smallest singular value of symmetric random matrices. Combinatorics, Probability and Computing, 31(4), 662-683.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. Singularity of discrete random matrices. Geometric and Functional Analysis, 31(5), 1160-1218.
    (pdf) (online) (arXiv)

  • A. Sah, Mehtaab Sawhney, and Yufei Zhao. The cylindrical width of transitive sets. Israel Journal of Mathematics, 253, 647-672.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. On the smoothed analysis of the smallest singular value with discrete noise. Bulletin of the London Mathematical Society, 54(2), 369-388.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. The smallest singular value of dense random regular digraphs. International Mathematics Research Notices, 2022(24), 19300-19334.
    (pdf) (online) (arXiv)

  • A. Sah and Mehtaab Sawhney. Local limit theorems for subgraph counts. Journal of the London Mathematical Society, 105(2), 950-1011.
    (pdf) (online) (arXiv)

  • A. Sah, Mehtaab Sawhney, and Yufei Zhao. Patterns without a popular difference. Discrete Analysis, 2021:8.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. Anticoncentration versus the number of subset sums. Advances in Combinatorics, 2021:6.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. On the real Davies' conjecture. Annals of Probability, 49(6), 3011-3031.
    (pdf) (online) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. Perfectly Sampling \(k\ge(8/3+o(1))\Delta\)-Colorings in Graphs. ACM Symposium on Theory of Computing 2021, 1589-1600.
    (pdf) (online) (arXiv)

  • A. Sah, Mehtaab Sawhney, Jonathan Tidor, and Yufei Zhao. A counterexample to the Bollobás-Riordan conjectures on sparse graph limits. Combinatorics, Probability and Computing, 30(5), 796-799.
    (pdf) (online) (arXiv)

  • A. Sah, Mehtaab Sawhney, and Yufei Zhao. Cayley graphs without a bounded eigenbasis. International Mathematics Research Notices, 2022(8), 6157-6185.
    (pdf) (online) (arXiv)

  • A. Sah. An improved bound on the least common multiple of polynomial sequences. Journal de Théorie des Nombres de Bordeaux, Tome 32 (2020) no. 3, pp. 891-899.
    (pdf) (online) (arXiv)

  • Ross Berkowitz, A. Sah, and Mehtaab Sawhney. Number of arithmetic progressions in dense random subsets of \(\mathbb{Z}/n\mathbb{Z}\). Israel Journal of Mathematics, 244, 589-620.
    (pdf) (online) (arXiv)

  • A. Sah. Improving the \(\frac{1}{3}-\frac{2}{3}\) Conjecture for Width Two Posets. Combinatorica, 41(1), 99-126.
    (pdf) (online) (arXiv)

  • Colin Defant, Noah Kravitz, and A. Sah. Supertrees. Electronic Journal of Combinatorics, 27(2), P2.7.
    (pdf) (online) (arXiv)

  • Noah Kravitz and A. Sah. Linear extension numbers of \(n\)-element posets. Order, 38(1), 49-66.
    (pdf) (online) (arXiv)

  • A. Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao. Exponential improvements for superball packing upper bounds. Advances in Mathematics, 365, 107056.
    (pdf) (online) (arXiv)

  • A. Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao. A reverse Sidorenko inequality. Inventiones mathematicae, 221(2), 665-711.
    (pdf) (online) (arXiv) (Article in MIT News)

  • Michael Kural, Vaughan McDonald, and A. Sah. Möbius formulas for densities of sets of prime ideals. Archiv der Mathematik, 115, 53-66.
    (pdf) (online) (arXiv)

  • Nate Gillman, Michael Kural, Alexandru Pascadi, Junyao Peng, and A. Sah. Patterns of primes in the Sato-Tate conjecture. Research in Number Theory, 6, 9.
    (pdf) (online) (arXiv)

  • Noah Kravitz and A. Sah. A Stronger Connection Between the Erdős-Burgess and Davenport Constants. Journal of Number Theory, 210(May), 373-388.
    (pdf) (online) (arXiv)

  • Jacob Fox, A. Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao. Triforce and corners. Mathematical Proceedings of the Cambridge Philosophical Society, 169(1), 209-223.
    (pdf) (online) (arXiv)

  • A. Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao. The number of independent sets in an irregular graph. Journal of Combinatorial Theory, Series B, 138(Sep), 172-195.
    (pdf) (online) (arXiv) (Article in MIT News)

  • Mitchell Lee and A. Sah. Constraining Strong c-Wilf Equivalence Using Cluster Poset Asymptotics. Advances in Applied Mathematics, 103(Feb), 43-57.
    (pdf) (online) (arXiv)

  • A. Sah and Mehtaab Sawhney. On the Discrepancy Between Two Zagreb Indices. Discrete Mathematics, 341(9), 2575-2589.
    (pdf) (online) (arXiv)

Expositions

  • Matthew Kwan, A. Sah, and Mehtaab Sawhney. Note on random Latin squares and the triangle removal process.
    (pdf) (arXiv)

  • Vishesh Jain, A. Sah, and Mehtaab Sawhney. Sharp invertibility of random Bernoulli matrices.
    (pdf) (arXiv)

Preprints

  • James Leng, A. Sah, and Mehtaab Sawhney. Improved Bounds for Szemerédi's Theorem, preprint.
    (pdf) (arXiv)

  • James Leng, A. Sah, and Mehtaab Sawhney. Quasipolynomial bounds on the inverse theorem for the Gowers \(U^{s+1}[N]\)-norm, preprint.
    (pdf) (arXiv)

  • Margalit Glasgow, Matthew Kwan, A. Sah, and Mehtaab Sawhney. A central limit theorem for the matching number of a sparse random graph, preprint.
    (pdf) (arXiv)

  • James Leng, A. Sah, and Mehtaab Sawhney. Improved bounds for five-term arithmetic progressions, preprint.
    (pdf) (arXiv)

  • A. Sah, Julian Sahasrabudhe, and Mehtaab Sawhney. The limiting spectral law for sparse iid matrices, preprint.
    (pdf) (arXiv)

  • A. Sah, Julian Sahasrabudhe, and Mehtaab Sawhney. The sparse circular law, revisited, preprint.
    (pdf) (arXiv)

  • Sarah Peluse, A. Sah, and Mehtaab Sawhney. Effective bounds for Roth's theorem with shifted square common difference, preprint.
    (pdf) (arXiv)

  • Margalit Glasgow, Matthew Kwan, A. Sah, and Mehtaab Sawhney. Rank of a random sparse graph, preprint.
    (pdf) (arXiv)

  • Peter Keevash, A. Sah, and Mehtaab Sawhney. The existence of subspace designs, preprint.
    (pdf) (arXiv) (Article in Quanta Magazine)

  • Huy Tuan Pham, A. Sah, Mehtaab Sawhney, and Michael Simkin. A Toolkit for Robust Thresholds, preprint.
    (pdf) (arXiv)

  • Matthew Kwan, A. Sah, Mehtaab Sawhney, and Michael Simkin. High-Girth Steiner Triple Systems, preprint.
    (pdf) (arXiv) (Article in Quanta Magazine) (Article by IST Austria)

Manuscripts in preparation