Noah G. Singer (he/him)
Carnegie Mellon University
Gates 9009
first initial middle initial last name (at) cs (dot) cmu (dot) edu
@singerng_

About Me

I'm a fourth-year Ph.D. student in the Computer Science Department at Carnegie Mellon University, where I work on theoretical computer science advised by Ryan O'Donnell and Aayush Jain. I was previously supported by an NSF GRFP fellowship. For my CV, see here.

In Spring 2022, I graduated magna cum laude from Harvard with an A.B. in Computer Science and Math. At Harvard, I worked with Madhu Sudan.

Research interests

My work spans several areas, including high-dimensional expanders and (the hardness of) approximating constraint satisfaction problems (CSPs).

Selected publications

Here are some selected research papers; for a full list of my writings, see here.

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
A classical quadratic speedup for planted \(k\)XOR
Meghal Gupta, William R. He, Ryan O'Donnell, Noah G. Singer
SODA 2026
arXiv
Streaming complexity of CSPs with randomly ordered constraints
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
SODA 2023
arXiv

Teaching

At CMU, I have been a teaching assistant for the following courses:

15-459: Undergraduate Quantum Computation (Fall 2023)
15-754: Spectral Graph Theory (Fall 2025)

At Harvard, I was a teaching assistant for the following courses:

In CS 121 (Fall 2019 and 2020), I organized guest lectures in the "CS 121.5" advanced section. In Summer 2022, I was a teaching assistant for the 2022 New Horizons in TCS program at TTIC.

Hobbies

I love to read; play piano; listen to music and podcasts; watch TV and movies; bake and cook (photos here); play tennis; go on long walks; and watch hockey (go Caps!), basketball, and (American) football. See some of my favorite books, TV shows, and musicians here.

Miscellanea

Before college, I helped found an online high school cybersecurity competition called ångstromCTF (running since 2016!), and redesigned our school newspaper website SilverChips Online.

My brother Ethan studies statistics and public policy.