The following papers are roughly organized (reverse) chronologically. You can also find my work on DBLP and Google Scholar. My ORCID is 0000-0002-0076-521X. See also this YouTube playlist of my research talks. Authors are ordered alphabetically (as is the convention in mathematics and theoretical computer science), unless noted otherwise.

Technical manuscripts

• Optimal single-pass streaming lower bounds for approximating CSPs
  Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
  arXiv
• Agreement testers and PCPs from coset complexes
  Ryan O'Donnell, Noah G. Singer
  arXiv
• Sketching approximations and LP approximations for finite CSPs are related
  Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
  arXiv
• The relative Dehn method for coboundary expansion
  Ryan O'Donnell, Noah G. Singer
  PDF

Technical publications

• Streaming complexity separations for dense and sparse graphs
  Yang P. Liu, Hoaian Nguyen, Noah G. Singer, David P. Woodruff
  ICALP 2026
  
• A classical quadratic speedup for planted \(k\)XOR
  Meghal Gupta, William R. He, Ryan O'Donnell, Noah G. Singer
  SODA 2026
  arXiv
• Algebra is half the battle: Verifying presentations for graded unipotent Chevalley groups
  Eric Wang, Arohee Bhoja, Cayden Codel, Noah G. Singer
  ITP 2025
  
• Latency guarantees for caching with delayed hits
  Keerthana Gurushankar, Noah G. Singer, Bernardo Subercaseaux
  INFOCOM 2025
  arXiv
• Streaming algorithms via local algorithms for Maximum Directed Cut
  Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
  SODA 2025
  arXiv
• Improved streaming algorithms for Maximum Directed Cut via smoothed snapshots
  Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
  FOCS 2023
  arXiv
• Oblivious algorithms for the Max-\(k\)AND Problem
  Noah G. Singer
  APPROX 2023
  arXiv
• Streaming complexity of CSPs with randomly ordered constraints
  Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
  SODA 2023
  arXiv
• On sketching approximations for symmetric Boolean CSPs
  Joanna Boyland, Michael Hwang, Tarun Prasad, Noah G. Singer, Santhoshini Velusamy
  APPROX 2022
  arXiv Talk
• Streaming approximation resistance of every ordering CSP
  Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
  APPROX 2021
  Computational Complexity 33
  arXiv Talk
• Point-hyperplane incidence geometry and the log-rank conjecture
  Noah G. Singer, Madhu Sudan
  ACM Transactions on Computation Theory 14.2
  arXiv

Miscellaneous writing

• Nine lower bound conjectures on streaming approximation algorithms for CSPs
  Noah G. Singer
  SIGACT News Open Problems
  arXiv
• Better streaming algorithms for Maximum Directed Cut via 'snapshots'
  Noah G. Singer
  CMU CSD PhD 'Writing Skills' blog post
  PDF
• Borges and the aesthetics of computation
  Noah G. Singer
  Variaciones Borges 56
  
• On streaming approximation algorithms for constraint satisfaction problems
  Noah G. Singer
  Harvard College Senior Thesis
  Hoopes Prize (Harvard College)
  PDF