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
-
A dichotomy theorem for approximating CSPs in random-order streams
Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
In submission
-
Efficient fault-tolerant self-routing on constant-degree networks
Yinchen Liu, Ryan O'Donnell, Noah G. Singer
In submission
-
Sounder, shorter, and simpler PCPs from HDX neighborhoods
Yotam Dikstein, Irit Dinur, Max Hopkins, Noah G. Singer
In submission
Technical publications
-
Optimal single-pass streaming lower bounds for approximating CSPs
Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
FOCS 2026
arXiv -
Agreement testers and PCPs from coset complexes
Ryan O'Donnell, Noah G. Singer
FOCS 2026
arXiv -
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