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
-
Coboundary expansion inside Chevalley coset complex HDXs
Ryan O'Donnell and Noah G. Singer
In submission
-
Oblivious algorithms for Maximum Directed Cut: New upper and lower bounds
Samuel Hwang, Noah G. Singer, and Santhoshini Velusamy
In submission
Technical publications
-
Latency guarantees for caching with delayed hits
Keerthana Gurushankar, Noah G. Singer, Bernardo Subercaseaux
INFOCOM 2025
-
Streaming algorithms via local algorithms for Maximum Directed Cut
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, and Santhoshini Velusamy
SODA 2025
-
Improved streaming algorithms for Maximum Directed Cut via smoothed snapshots
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, and Santhoshini Velusamy
FOCS 2023
-
Oblivious algorithms for the Max-\(k\)AND Problem
Noah G. Singer
APPROX 2023
-
Streaming complexity of CSPs with randomly ordered constraints
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, and Santhoshini Velusamy
SODA 2023
-
On sketching approximations for symmetric Boolean CSPs
Joanna Boyland, Michael Hwang, Tarun Prasad, Noah G. Singer, and Santhoshini Velusamy
APPROX 2022
Talk -
Streaming approximation resistance of every ordering CSP
Noah G. Singer, Madhu Sudan, and Santhoshini Velusamy
APPROX 2021
Computational Complexity 33
Talk -
Point-hyperplane incidence geometry and the log-rank conjecture
Noah G. Singer and Madhu Sudan
ACM Transactions on Computation Theory 14.2
Miscellaneous writing
-
Better streaming algorithms for Maximum Directed Cut via 'snapshots'
Noah G. Singer
CMU CSD PhD 'Writing Skills' blog post
-
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)