Research Experience

I've worked on two main projects in this area with Prof. Matt Weinberg.

Junior Paper: Matroid Prophet Inequalities [link]

For my Junior Paper at Princeton, I studied new lower bound constructions for the matroid intersection prophet inequality problem. 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 thus focused on investigating whether new generalization of the existing construction could improve the lower bound, leveraging tools from combinatorics, probability, and linear algebra given the diverse characterizations of matroids. I proved a number of new results that rule out generalizations and new constructions from improving the lower bound, providing new insights into the substructure of the existing hardness construction and narrowing down which directions are most promising for the future.

Senior Thesis: Sample Complexity of the ε-BIC-to-BIC Reduction

I'm now working on a senior thesis on improving the sample complexity of the so-called ε-truthful-to-truthful reduction in auction mechanisms for additive buyers, where truthfulness here means Bayesian incentive compatible (BIC). We are developing a more clever version of the existing replica-surrogate bipartite matching procedure, which currently requires exponentially many samples from the input distributions, that will only require polynomially many samples. Roughly, our idea is to leverage concentration to show that we need only look at smaller type space of the buyers, and to integrate this with techniques from the literature on Bernoulli factories and online primal-dual algorithms to complete the reduction.

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. We studied the degree sequence graphicality problem for 3-uniform hypergraphs, which asks whether a given degree sequence is realized by a 3-uniform hypergraph. We proved 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).

Publication: In submission to Journal of Combinatorial Theory. Upcoming presentation at Joint Mathematics Meeting 2025. Preprint on arXiv here

I worked on both theoretical research and implementations for new quantum compilation algorithms at IBM Quantum with Dr. Ali Javadi-Abhari. 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 for isometry synthesis 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.

Publication: Paper on theoretical results currently being drafted. Code used for benchmarks in another recent paper.