what am i up to?

go back ↰

# COLT!

I’m at COLT to present a paper about the largest common induced subgraph problem. Come up and say hi!

↸ Back to top

# on my mind

I’ve been thinking a lot about how research projects tend to fall into three consecutive phases.

1. Study/Exploration: You are just learning about the area, trying to develop intuition and learn techniques. This can take a long time, and sometimes you explore for a while and ultimately realize there is no path towards interesting results.
2. Discovery: Now you have a lot of intuition for the area and can prove things! This is a very exciting interval, but often short (or you get stuck here and it never ends, until you decide to give up).
3. Communication: You’ve basically determined your results but are trying to figure out how to communicate it — organizing/simplifying results, writing the paper, developing talks, etc. This phase always takes longer than I think, but I really enjoy it. It’s interesting to see how the act of communicating can help you refine the results themselves.

For my own sanity, it’s helpful to keep track of the states of my various projects:

Communication

• The BUD Walk
• Average-case hardness of LCIS
• Flexible Range-Searchable Encryption
• 10x10 enumeration (on hold)

Discovery

• BUD irreducibility
• Algorithms for planted random subgraph
• Online algorithms for binary perceptron
• ReCom on dense random graphs
• Impeaching “mayors” of universal covers (gave up for now)

Study/Exploration

• Cryptography from graph theoretic assumptions
• The overlap gap property
• Prophet inequalities with cancellation costs (on hold)
• AI and the Fourth Amendment (on hold)
• Actuarially fair insurance pricing (on hold)
• Distinguishing permutations from functions (on hold)
• Job scheduling lower bound (on hold)

↸ Back to top

# big (TCS) questions

• What makes polynomial-time algorithms so hard to analyze? (My guess is that such algorithms are defined by a property that has nothing to do with how they find solutions.)
• Given that the low-degree conjecture is false, how can we build a good theory of average-case hardness?
• Is structure necessary for public-key cryptography?

Last updated June 2026.

↸ Back to top