Surveys / Class Projects

Power from Random Strings Survey

There’s a really neat line of work examining what problems can be reduced resource-efficiently to the (resource-unbounded) Kolmogorov random strings; this is a survey of some of the main results / open directions there. Written as the final project for Ryan Williams’ complexity theory class.

Limits of Preprocessing

This is my final project for boolean functions class; it’s an attempt at a more friendly presentation of this paper, which gives partial progress towards showing that inner product remains hard for $\mathsf{AC}^0$ circuits even after arbitrary preprocessing of both inputs independently.

The art gallery problem has been shown to be complete for $\exists \mathbb{R}$; here we give an overview of that result, and give some thoughts on hardness of related problems. Final project for computational geometry class.

Quantum Analogs of the Canadian Traveler Problem

This was the final project for my quantum information science class. TLDR: some new pathfinding problem has quadratic speedup with quantum search.

Canadian Traveler Problem Survey

The reason I was thinking about CTP for that quantum project was because a couple friends and I had earlier written a survey of the (classical) problem for our advanced algorithms class. Most of this is not original research, but should be a reasonably nice introduction to the problem.

MIP* = RE poster

This is a poster I made for my quantum computation class, giving a very rough overview of the breaktrough MIP* = RE result in quantum complexity.

Ramsey Theory Notes

These are notes from my Ramsey theory class spring 2023 (taught by Lisa Sauermann). They’re not especially proofread or anything, but I find myself referring back to them a fair amount, so I put them up on the internet in case they’re useful to other people.

Slides

Low-Degree ECC Decoding and Relative Rank slides

These are some slides for a reading group I met with fall 2023. The first of these explains the result from this paper that $\mathsf{NC}^0[\oplus]$ circuits can’t decode error-correcting codes with constant success probability. The second discusses the preliminaries on relative rank and Nisan-Wigderson design polynomials for this paper.

Intro to Information Theory slides

Some slides explaining the basics of information theory (entropy, KL divergence, Shannon/Huffman coding) in terms of a game of Guess Who?

PCP slides

Here are some slides for a presentation I gave for MIT’s directed reading program sophomore year. We define the PCP theorem and walks through Irit Dinur’s proof.

What You Can’t Do With Math

This is for a class I taught fall 2021 for high schoolers about a couple of classic impossibility results.

Music

Banach-Tarski

My dad used to sing a version of this song as a “musical ditty for math loving kiddies”, so for Christmas last year I put together this full version.

The Scream

I recorded this for my jazz class last spring. I wanted to make something based around augmented 7ths, and it sounded so angsty that I decided to put a spoken-word excerpt from Edvard Munch’s diary over the solo section.

Vexations

This is a jazz arrangement of Erik Satie’s Vexations, also for that class. Trying to fit vaguely tonal-sounding chords to this was a bit of a nightmare, but I think the result ended up sounding decent (largely thanks to the jazz combo that performed this, led by my lovely professor Lihi Haruvi on alto sax).

Ancylid

This is another class project that I was lucky enough to have sight-read by some real professional musicians. I’d never tried to write a string quartet before – was a fun experience.

Wollaston

I took a class called “Electronic Music Composition” – here’s an example of the sort of thing we did. The degree to which this counts as music is perhaps open to debate, but I definitely learned some useful DAW tricks as the class progressed.

Gåte for Døden

I made this in high school as part of an elaborate prank on a friend of mine. It’s a bit of a long story, but we were learning some Norwegian together, so I made a website for a fake Norwegian indie band and then hid a string of puzzles in a song that eventually led to a rickroll. The puzzle chain isn’t followable anymore, but I still think the song is fun (if you can excuse my terrible Norwegian pronunciation).