Noah Singer (he/him)
Carnegie Mellon University
Gates 9009
first initial g last name (at) cs (dot) cmu (dot) edu

About Me

I'm a first-year Ph.D. student in the Computer Science Department at Carnegie Mellon University. My research interests are in theoretical computer science, and I'm lucky to be advised by Pravesh Kothari and Aayush Jain. I'm supported by an NSF GRFP fellowship. For my CV, see here, and for a list of my papers, see here.

In Spring 2022, I graduated magna cum laude from Harvard with an A.B. in Computer Science and Math. At Harvard, I was fortunate to be mentored by Madhu Sudan, and I was a proud resident of Pforzheimer House.

Research Overview

I have broad interests throughout complexity and algorithms, centered around combinatorial optimization and average-case complexity, with applications to cryptography, coding theory, and combinatorics. Recently, I've been thinking about things including Sum-of-Squares relaxations, high-dimensional expanders, and various random models.

Specific Projects

I have ongoing interest in understanding approximations for CSPs in streaming models. I was introduced to the area during my undergrad by Santhoshini Velusamy and Madhu Sudan. With them and other wonderful collaborators I have several papers on the subject, appearing in APPROX 2021 and 2022 and SODA 2023. Some of these works were the subject of my undergraduate thesis, which was awarded a Hoopes Prize at Harvard.


Teaching. 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. During Fall 2022, I'm volunteering to edit scribe notes for Madhu Sudan's CS 229R: Information Theory for Computer Science.

Community. At Harvard, from 2020-2022 I was a CS Peer Concentration Adviser and Women in CS (WiCS) mentor. In Spring 2019, I worked with Harvard's Digital Literacy Project to teach Scratch and Processing.js to Boston-area middle school students.

Work Experience. In Summer 2019, I worked as a software engineering intern at Airbnb in San Francisco on the Host Growth & Traffic team, where I built a production data pipeline to discover and manage large quantities of Google search advertising keywords targeting Airbnb hosts.


Literature. I love science fiction! My favorite short story is William Gibson's Fragments of a Hologram Rose. Some of my favorite novels are Gibson's Neuromancer, Le Guin's The Dispossessed, Jemisin's The Fifth Season, Robinson's Red Mars, García Márquez' Cien años de soledad, and Murakami's The Wind-Up Bird Chronicle.

Music. I listen to a lot of music, including indie rock, electronica, and hip hop; my favorite artists include The Strokes, Ratatat, Gorillaz, and Daft Punk. I also play classical piano.

Podcasts. I like listening to podcasts, and some of my favorites are You're Wrong About, Maintenance Phase, Ologies, Radio Ambulante, Cautionary Tales, One Year, and Radiolab.

Other. I love to watch TV shows; bake and cook; play tennis and go on long walks; and watch hockey (go Caps!) and basketball.