Research

Our work focuses on improving the sample complexity of blackbox reductions from mechanism design to algorithm design (in particular, the so-called epsilon-BIC-to-BIC reduction). Existing reductions are based on the replica-surrogate bipartite matching procedure, which requires exponentially-many samples from input distributions.

We show that under some natural structural assumptions (independent items, and a Lipschitz-ness condition on valuation functions), we can improve the sample complexity to polynomial in the relevant parameters. This resolves the central open question from a FOCS'18 paper. Our mechanism is based on a new variant of replica-surrogate matching, and our analysis uses concentration specific to product distributions as well as a few neat tricks to handle small errors and failure probabilities.

I worked on this project for my senior thesis at Princeton, advised by Prof. Matt Weinberg and Eric Xue. Stay tuned for a paper on our results! Meanwhile, slides from my thesis talk and a poster from EC'25 (both with a preliminary version of our current results) are available here: [slides] and [poster].

Oblivious algorithms are a class of privacy-preserving algorithms whose memory access patterns must leak no information about secret input data. Most real-world deployments of oblivious algorithms naturally follow an external-memory model, where the I/O cost of block transfers between external memory (i.e. some untrusted memory) and cache (i.e. a hardware enclave) becomes significant for performance. However, few algorithms that are both oblivious and external-memory-friendly are known.

We present an oblivious SSSP algorithm with I/O and work bounds nearly matching the non-private baseline. This is the first oblivious SSSP algorithm to achieve any non-trivial I/O cost. To bypass the polylog overhead incurred by generic oblivious RAM solutions, we designed a new oblivious graph-regularization primitive (to hide adjacency information) and strengthened existing oblivious priority queues. Our algorithm carefully intertwines these building blocks to achieve privacy---at, remarkably, almost no performance overhead!

I worked on this project with Prof. Elaine Shi at CMU.

Prophet inequalities are a class of online selection problems that ask how well an agent choosing online from a sequence of items, under some set of feasibility constraints, can approximate the offline optimal feasible subset of items. The prophet inequality for matroid intersection constraints is a decade-old open problem, with an asymptotic gap between linear upper bounds and roughly-square-root lower bounds on the approximation ratio, and what's especially intriguing is that the existing lower bound construction satisfies many special conditions that need not hold in general—yet no alternate constructions have been explored.

My research focused on studying whether new generalization of the existing construction could improve the lower bound. I proved a couple new results that rule out some classes of constructions from improving the lower bound. For instance, I showed that partition matroids are optimal for expressing the existing lower bound construction -- we can't hope to improve it by generalizing to arbitrary matroids. This particular result completes the reverse direction of a reduction in a 2022 paper to show an equivalence between the current lower bound construction and graph-theoretic product dimension bounds.

I worked on this project for my Junior Paper at Princeton, advised by Prof. Matt Weinberg.

Our work studies the degree sequence graphicality problem for 3-uniform hypergraphs, which asks whether a given degree sequence is realized by a 3-uniform hypergraph. We prove a dichotomy theorem on the complexity of this decision problem over all possible degree intervals, showing that the problem is either solvable in linear time (very easily) or NP-complete (and characterizing exactly when each case happens).

I worked on this project with Prof. István Miklós (Rényi Institute) and two other students while at the Budapest Semesters in Mathematics in 2024.

This project consisted of research and software implementations for new quantum compilation algorithms. I proved a new result on the space-depth tradeoff between additional qubits and additional depth in parity synthesis for Hamiltonian simulation circuits. Specifically, I devised a new algorithmic framework for extending the block algorithm of de Brugière et al. in a way that enables finer-grained control of the space-depth tradeoff than previously possible, by leveraging additional ancilla to proportionally parallelize the existing computations.

I worked on this project as a quantum computing intern at IBM Research in 2023, mentored by Dr. Ali Javadi-Abhari and Dr. Simon Martiel. Slides from a short talk I gave on the theoretical framework are available here: [slides].