I am a postdoc with Nathan Klein at Boston University. Previously, I was a postdoc with Daniel Dadush at CWI Amsterdam. I completed my PhD in mathematics at the London School of Economics, under the supervision of László Végh. Before that, I studied mathematics at the University of Waterloo, where I was advised by Laura Sanità.

My research interests are in algorithms, optimization and game theory.

Publications

• Abstract
• arXiv

We show that the circuit diameter of a polyhedron can be bounded in terms of the straight line complexity of its associated LPs. We also give a circuit augmentation algorithm with matching iteration complexity.

• Abstract
• arXiv
• Slides

We give a nearly linear work parallel approximation scheme for the Held–Karp bound for metric TSP. Our method also yields a parallel approximation scheme for the k-edge-connected spanning subgraph LP, with similar work and depth bounds.

• Abstract
• arXiv

We study the online matching problem on k-uniform hypergraphs with one-sided vertex arrivals. The greedy algorithm is 1/k-competitive, whereas no algorithm is 2/k-competitive. For k = 3, we give a fractional algorithm which is (e − 1)/(e + 1)-competitive, and prove that this is optimal. For k ≥ 3, we give a simple integral algorithm which performs better than greedy when the online nodes have bounded degree.

• Abstract
• Slides
• Video

We give a strongly polynomial algorithm for minimum cost generalized flow, and as a consequence, for all LPs with at most two nonzero entries per row or column.

• Abstract
• arXiv
• Slides

We derive an improved bound on the correlation gap of matroid rank functions, parameterized by the rank and girth of the matroid. We also show that for any matroid, the correlation gap of its weighted matroid rank function is the worst under uniform weights.

• Abstract
• arXiv
• Slides

We propose a strategy iteration framework for parity games, which pivots based on the valuation given by any universal tree.

• Abstract
• arXiv
• Slides

We show that the circuit diameter of a polyhedron can be bounded in terms of the circuit imbalance measure of its constraint matrix. We also give a circuit augmentation algorithm with similar iteration complexity.

• Abstract
• arXiv
• Slides

We give an accelerated, or 'look-ahead' version of the Newton–Dinkelbach method, and demonstrate its efficacy in 3 application domains: (i) An improved convergence bound for linear fractional combinatorial optimization; (ii) A strongly polynomial label-correcting algorithm for solving the feasibility of linear systems with at most two variables per inequality; (iii) A simplified variant of the parametric submodular function minimization result by Goemans et al. (2017).

• Abstract
• arXiv
• Slides

We study the minimum-cost spanning tree game, a classic model in cooperative game theory. We show how to check whether an instance of the game is convex/submodular in polynomial time.

• Abstract
• arXiv
• Slides
• Video

An edge-weighted graph G is stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. We give a polynomial-time algorithm for finding a smallest set of vertices whose removal from G yields a stable graph. In contrast, we show that the problem of finding a smallest set of edges whose removal from G yields a stable graph does not admit any constant-factor approximation, unless P = NP.