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 third-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 Ryan O'Donnell 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 combinatorics and cryptography.

One of my projects is understanding the approximability of constraint satisfaction problems in streaming and sublinear models. I was introduced to these questions during my undergrad by Santhoshini Velusamy and Madhu Sudan, and with them and other wonderful collaborators we have several papers, appearing in APPROX 2021, 2022, and 2023, SODA 2023, and FOCS 2023. The first few of these works were the subject of my undergraduate thesis, which was awarded a Hoopes Prize at Harvard. See also my talk on streaming DICUT algorithms at CMU Theory Lunch.

Teaching

In Fall 2023, I was a teaching assistant for 15-459: Undergraduate Quantum Computation at CMU, taught by Ryan O'Donnell.

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.