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?

Low-Degree ECC Decoding and Relative Rank slides

These are some slides for a reading group I met with this semester. The first of these is primarily explaining the result from this paper that $\text{NC}^0[\oplus]$ circuits can’t decode error-correcting codes with constant success probability. The second is disccusing the preliminaries on relative rank and Nisan-Wigderson design polynomials for this paper. I don’t know if I would actually recommend looking at these slides, since they’re sort of designed to be presented in the context of other things, but I put them up here because a friend asked me to.

Stochastic Block Model Matching Paper and Slides

From the REU I did last summer. This is the current draft of the conference version; there’s also a more verbose version on arxiv here. The project is about matching numbers in random graphs – I thought it was a very neat problem, and the online setting might even have applications (although to be fair we didn’t prove very much about the online setting). This was my first proper experience with self-driven math research; I think regardless of the results we ended up with I discovered that I really enjoyed the journey.

Quantum Analogs of the Canadian Traveler Problem

This was the final project for my quantum information science class. It’s basically just me making up a type of pathfinding problem, and then showing a quadratic speedup with quantum search. I ended up having to do a nested binary-search-y thing though, so my query complexity looked like $\mathcal{O}(\sqrt{k d} \cdot \log d \log \log k)$, which made me happy because needing $\log \log$ terms makes me feel fancy. I’m not sure yet how much quantum work I’ll do in the future, but I’m glad this project let me learn about things like adversary bounds and span programs, because I thought those were cool ideas.

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.

PCP slides

Here are some slides for a presentation I gave for MIT’s directed reading program sophomore year. It defines the PCP theorem and walks through Irit Dinur’s proof – I kinda doubt it’ll be followable without the presentation aspect, but hey you never know.

What You Can’t Do With Math

These slides are probably a little more followable without the presentation (although still probably still not ideal). This is for a class I taught for high schoolers about a couple of my favourite impossibility results.

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. I still only kinda understand the proof, but if you read this poster you’ll know approximately as much as I do.

Ramsey Theory Notes

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