Welcome to my site! I’m Andrew Krapivin, a second-year PhD student in computer science at CMU, advised by William Kuszmaul and Elaine Shi. Broadly, I am interested in developing theory, particularly for data structures and security, and finding new applications in which it can be useful. My recent work spans space-efficient hashing, oblivious data structures, and SAT solving: open-addressed hash tables that beat long-standing bounds (the first paper in this series was featured in Quanta), optimal statistically secure ORAM and oblivious search trees, compact SAT encodings, and optimal hypergraph (biclique) decompositions. I also created PointSAT and used it to resolve an open problem in discrete geometry. Beyond that, I have worked on improving the performance of hash tables at high load factors, on a computational model to capture out of order execution on modern CPUs, on comparing encoders and (reasoning) decoders from a theoretical perspective, and more.

I previously completed an MPhil in Advanced Computer Science at Cambridge University, funded by a Churchill Scholarship. Before that, I received a BS in mathematics and computer science from Rutgers University.

If you want to discuss anything, feel free to reach out!

Recent news

• Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing, with William Kuszmaul, will appear at SODA 2027.
• New preprint with Elaine Shi: Optimal Statistical Oblivious RAM and Search Tree in the External-Memory Model.
• New preprint with William Kuszmaul and Yixuan Wang: Interlinear Probing: Linear Probing with Non-Greedy Insertions.
• Papers this year at STOC (two), SIGMOD, SAT, and CICM; see my publications.
• Named a Hertz Fellowship finalist (2026).
• Our hash table work was featured in Quanta’s 2025’s Biggest Breakthroughs in Computer Science.