Research

My papers are listed below by topic.

Additional links to my work: arXiv | MathSciNet | Google Scholar | CV

Research themes

• Graph regularity and additive combinatorics: Szemerédi’s graph regularity method is a powerful tool in modern graph theory research. The classical version of the regularity method only works in the dense setting, and my work extends the method to the sparse setting. Ideas arising from graph regularity can be transferred to the world of additive combinatorics. For example, our work on sparse graph/hypergraph regularity counting lemmas led to a simplification of the proof the Green–Tao theorem (see exposition). blog
  • Regularity and counting lemmas in sparse graphs
  • Arithmetic regularity, and applications to additive combinatorics
  • Popular differences
  • Property testing and algorithmic applications
  • Graph limits
• Graph inequalities: Many fundamental problems in extremal graph theory can be phrased in terms of inequalities between subgraph densities or graph homomorphism counts. My work develops new tools to solve such problems.
  • Independent sets, colorings, and graph homomorphisms
  • Sidorenko’s conjecture and related problems
  • Variational problems arising from large deviations in random graphs
• Discrete geometry: I am interested in extremal problems in discrete geometry, e.g., what is the largest size of a geometric configuration satisfying certain properties. Solutions often apply a variety of tools such as linear programming bounds, the polynomial method, spectral graph theory, group representation theory.
  • Sphere packing, spherical codes
  • Equiangular lines, spherical two-distance sets MIT News
  • Incidence geometry, e.g., the joints problem
  • The geometry of transitive sets, applications to Cayley graphs
  • Extension complexity of polytopes

Papers

The Green-Tao theorem and a relative Szemerédi theorem slides video

• A relative Szemerédi theorem (with David Conlon and Jacob Fox)
  Geometric and Functional Analysis 25 (2015), 733–762
  Companion note: Linear forms from the Gowers uniformity norm

• An arithmetic transference proof of a relative Szemerédi theorem
  Mathematical Proceedings of the Cambridge Philosophical Society 156 (2014), 255–261.

• The Green-Tao theorem: an exposition (with David Conlon and Jacob Fox)
  EMS Surveys in Mathematical Sciences 1 (2014), 249–282

• A short proof of the multidimensional Szemerédi theorem in the primes (with Jacob Fox)
  American Journal of Mathematics 137 (2015), 1139–1145

Sparse graph regularity and counting

• Extremal results in sparse pseudorandom graphs (with David Conlon and Jacob Fox)
  Advances in Mathematics 256 (2014), 206–290 slides

• The regularity method for graphs with few 4-cycles (with David Conlon, Jacob Fox, and Benny Sudakov)
  Journal of the London Mathematical Society 104 (2021), 2376–2401 slides

• Removal lemmas and approximate homomorphisms (with Jacob Fox)
  Combinatorics, Probability and Computing 31 (2022), 721–736

• Which graphs can be counted in $C_4$-free graphs? (with David Conlon, Jacob Fox, and Benny Sudakov)
  Pure and Applied Mathematics Quarterly 18 (2022), 2413–2432

Algorithmic graph regularity

• On regularity lemmas and their algorithmic applications (with Jacob Fox and László Miklós Lovász)
  Combinatorics, Probability and Computing 26 (2017), 481–505

• A fast new algorithm for weak graph regularity (with Jacob Fox and László Miklós Lovász)
  Combinatorics, Probability and Computing 28 (2019), 777–790

Popular differences

• Triforce and corners (with Jacob Fox, Ashwin Sah, Mehtaab Sawhney, and David Stoner)
  Mathematical Proceedings of the Cambridge Philosophical Society, 169 (2020), 209–223

• Patterns without a popular difference (with Ashwin Sah and Mehtaab Sawhney)
  Discrete Analysis, 2021:8, 30 pp. video slides

• Tower-type bounds for Roth’s theorem with popular differences (with Jacob Fox and Huy Tuan Pham)
  Journal of the European Mathematical Society 25 (2023), 3795–3831

Arithmetic regularity and applications

• Efficient arithmetic regularity and removal lemmas for induced bipartite patterns (with Noga Alon and Jacob Fox)
  Discrete Analysis 2019:3, 14 pp slides

• Induced arithmetic removal: complexity 1 patterns over finite fields (with Jacob Fox and Jonathan Tidor)
  Israel Journal of Mathematics 248 (2022), 1–38

• Testing linear-invariant properties (with Jonathan Tidor)
  IEEE Symposium on Foundations of Computer Science (FOCS 2020)
  SIAM Journal on Computing 51 (2022), 1230–1279

Topics in additive combinatorics

• Common and Sidorenko linear equations (with Jacob Fox and Huy Tuan Pham)
  The Quarterly Journal of Mathematics 72 (2021), 1223–1234

• A short proof of the canonical polynomial van der Waerden theorem (with Jacob Fox and Yuval Wigderson)
  Comptes Rendus Mathématique 358 (2020), 957–959

• Uniform sets with few progressions via colorings (with Mingyang Deng and Jonathan Tidor)

• Uncommon linear systems of two equations (with Dingding Dong and Anqi Li)

Hypergraph expanders

• Hypergraph expanders of all uniformities from Cayley graphs (with David Conlon and Jonathan Tidor)
  Proceedings of the London Mathematical Society 121 (2020), 1311–1336

Cayley graphs and transitive sets

• Quasirandom Cayley graphs (with David Conlon)
  Discrete Analysis 2017:6, 14 pp

• Group representations that resist worst-case sampling

• Cayley graphs without a bounded eigenbasis (with Ashwin Sah and Mehtaab Sawhney)
  International Mathematics Research Notices. IMRN 2022 (2022), 6157–6185

  

• The cylindrical width of transitive sets (with Ashwin Sah and Mehtaab Sawhney)
  Israel Journal of Mathematics 253 (2023), 647–672 blog

• Quantum Unique Ergodicity for Cayley graphs of quasirandom groups (with Michael Magee and Joe Thomas)
  Communications in Mathematical Physics 402 (2023), 3021–3044

• Cayley graphs that have a quantum ergodic eigenbasis (with Assaf Naor, Ashwin Sah, and Mehtaab Sawhney)
  Israel Journal of Mathematics 256 (2023), 599–617

  

Equiangular lines and eigenvalue multiplicities

• Equiangular lines with a fixed angle (with Zilin Jiang, Jonathan Tidor, Yuan Yao, and Shengtong Zhang)
  Annals of Mathematics 194 (2021), 729–743 slides blog MIT News

  

• Spherical two-distance sets and eigenvalues of signed graphs (with Zilin Jiang, Jonathan Tidor, Yuan Yao, and Shengtong Zhang)
  Combinatorica 43 (2023), 203–232

• Graphs with high second eigenvalue multiplicity (with Milan Haiman, Carl Schildkraut, and Shengtong Zhang)
  Bulletin of the London Mathematical Society 54 (2022), 1630–1652. blog

• Uniacute Spherical Codes (with Saba Lepsveridze and Aleksandre Saatashvili)
  Combinatorica, to appear

• Spectral non-concentration near the top for unimodular random graphs (with Mikolaj Fraczyk, Ben Hayes, and Madhu Sudan)

• Equiangular lines and eigenvalue multiplicities,
  Notices of the American Mathematical Society 71 (2024), 1151–1159

Incidence geometry

• Joints tightened (with Hung-Hsun Hans Yu) blog
  American Journal of Mathematics 145 (2023), 569–583.

• Joints of varieties (with Jonathan Tidor and Hung-Hsun Hans Yu) blog video slides
  Geometric and Functional Analysis 32 (2022) 302–339

Extension complexity and nonnegative rank

• Extension complexity of low-dimensional polytopes (with Matthew Kwan and Lisa Sauermann)
  Transactions of the American Mathematical Society 375 (2022), 4209–4250

Plank problem

• Exploring a planet, revisited,
  American Mathematical Monthly 129 (2022), 678–680

Independent sets and graph homomorphisms

• Extremal regular graphs: independent sets and graph homomorphisms
  American Mathematical Monthly 124 (2017), 827–843 blog

• The number of independent sets in a regular graph
  Combinatorics, Probability and Computing 19 (2010), 315–320 poster

• The number of independent sets in a graph with small maximum degree (with David Galvin)
  Graphs and Combinatorics 27 (2011), 177–186

• The bipartite swapping trick on graph homomorphisms
  SIAM Journal on Discrete Mathematics 25 (2011), 660–680 poster

• The number of independent sets in an irregular graph (with Ashwin Sah, Mehtaab Sawhney, and David Stoner)
  Journal of Combinatorial Theory Series B 138 (2019), 172–195 blog MIT News

• A reverse Sidorenko inequality (with Ashwin Sah, Mehtaab Sawhney, and David Stoner)
  Inventiones Mathematicae 221 (2020), 665–711 slides blog

Sphere packing and energy minimization

• Sphere packing bounds via spherical codes (with Henry Cohn)
  Duke Mathematical Journal 163 (2014), 1965–2002

• Energy-minimizing error-correcting codes (with Henry Cohn)
  IEEE Transactions on Information Theory 60 (2014), 7442–7450

• Exponential improvements for superball packing upper bounds (with Ashwin Sah, Mehtaab Sawhney, and David Stoner)
  Advances in Mathematics, 365 (2020), 107056

Asymptotic enumeration

• Enumerating $k$-SAT functions (with Dingding Dong and Nitya Mani)
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2022) blog

• On the number of error correcting codes (with Dingding Dong and Nitya Mani)
  Combinatorics, Probability and Computing, 32 (2023), 819–832

• Nearly all $k$-SAT functions are unate (with József Balogh, Dingding Dong, Bernard Lidický, and Nitya Mani)
  ACM Symposium on Theory of Computing (STOC 2023)

Large deviations in random graphs slides

• On replica symmetry of large deviations in random graphs (with Eyal Lubetzky)
  Random Structures & Algorithms 47 (2015), 109–146 blog

• On the variational problem for upper tails in sparse random graphs (with Eyal Lubetzky)
  Random Structures & Algorithms 50 (2017), 420–436 blog

• On the lower tail variational problem for random graphs
  Combinatorics, Probability and Computing 26 (2017), 301–320

• Upper tails and independence polynomials in random graphs (with Bhaswar B. Bhattacharya, Shirshendu Ganguly, and Eyal Lubetzky)
  Advances in Mathematics 319 (2017), 313–347

• Upper tails for arithmetic progressions in a random set (with Bhaswar B. Bhattacharya, Shirshendu Ganguly, and Xuancheng Shao)
  International Mathematics Research Notices. IMRN 2020, 167–213 video

• On the upper tail problem for random hypergraphs (with Yang Liu)
  Random Structures & Algorithms 58 (2021), 179–220

Graph limits

• Hypergraph limits: a regularity approach
  Random Structures & Algorithms 47 (2015), 205–226

• An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions (with Christian Borgs, Jennifer T. Chayes, and Henry Cohn)
  Transactions of the American Mathematical Society 372 (2019), 3019–3062

• An $L^p$ theory of sparse graph convergence II: LD convergence, quotients, and right convergence (with Christian Borgs, Jennifer T. Chayes, and Henry Cohn)
  Annals of Probability 46 (2018), 337–396

• On derivatives of graphon parameters (with László Miklós Lovász)
  Journal of Combinatorial Theory, Series A 145 (2017), 364–368

• A counterexample to the Bollobás-Riordan conjectures on sparse graph limits (with Ashwin Sah, Mehtaab Sawhney, and Jonathan Tidor)
  Combinatorics, Probability and Computing 30 (2021), 796–799

Random matrices

• On the number of Hadamard matrices via anti-concentration (with Asaf Ferber and Vishesh Jain)
  Combinatorics, Probability and Computing (2022), 455–477

Extremal subgraph density problems in directed graphs and tournaments

• Impartial digraphs (with Yunkun Zhou)
  Combinatorica 40 (2020), 875–896 blog

• Paths of given length in tournaments (with Ashwin Sah and Mehtaab Sawhney)
  Combinatorial Theory 3 (2023), #5

Extremal and Ramsey graph theory

• The critical window for the classical Ramsey-Turán problem (with Jacob Fox and Po-Shen Loh)
  Combinatorica 35 (2015), 435–476

• Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold (with David Conlon, Jacob Fox, and Huy Tuan Pham)
  IEEE Transactions on Information Theory 70 (2024), 4074–4078

Intersecting families of graphs

• $K_4$-intersecting families of graphs (with Aaron Berger)
  Journal of Combinatorial Theory, Series B 163 (2023), 112–132

More sums than differences sets slides

• Constructing MSTD sets using bidirectional ballot sequences
  Journal of Number Theory 130 (2010), 1212–1220 extended version

• Counting MSTD sets in finite Abelian groups
  Journal of Number Theory 130 (2010), 2308–2322

• Sets characterized by missing sums and differences
  Journal of Number Theory 131 (2011), 2107–2134

Miscellaneous topics

• Constructing numerical semigroups of a given genus
  Semigroup Forum 80 (2010), 242–254

• The coefficients of a truncated Fibonacci power series
  Fibonacci Quarterly 46/47 (2009), 53–55

Older expository papers and notes

• Szemerédi’s theorem via ergodic theory

• Biased riffle shuffles, quasisymmetric functions, and the RSK algorithm

• Young tableaux and the representations of the symmetric group
  Harvard College Mathematics Review 2 (2008), 33–45