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

About Me

I'm a Ph.D. student in the Computer Science Department at Carnegie Mellon University, where I'm supported by an NSF GRFP fellowship. My research interests are in theoretical computer science.

In Spring 2022, I graduated with an A.B. in Computer Science and Math from Harvard (in Pforzheimer House!), where I was fortunate to work with Prof. Madhu Sudan on streaming and communication complexity. Here is my CV.


Interests

I have broad theoretical interests, including in complexity, cryptography, algorithms, and combinatorics. One general theme of interest is applications of mathematical techniques, such as algebra, Boolean Fourier analysis, or spectral methods, to answer questions about computation. My undergrad research centered on the complexity of constraint satisfaction problems, and specifically on lower bounds and algorithms in the streaming setting.

Papers

  • Streaming complexity of CSPs with randomly ordered constraints
    Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy
    In submission
  • On sketching approximations for symmetric Boolean CSPs
    Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, and Santhoshini Velusamy
    APPROX 2022
  • Streaming approximation resistance of every ordering CSP
    Noah Singer, Madhu Sudan, and Santhoshini Velusamy
    APPROX 2021
  • Point-hyperplane incidence geometry and the log-rank conjecture
    Noah Singer and Madhu Sudan
    ACM Transactions on Computation Theory
A full list of my papers and other writing may be found here.

Activities

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.

Community. Since 2020, I have been 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.

Hobbies

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, 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, and Ologies.

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