Publications

We study equitable colorings of vertex-weighted graphs, where the goal is to find a proper coloring in which the color classes have approximately equal total weight.

Improved algorithms and approximation bounds for partitioning a graph into fair and balanced parts.

The paper studies the best-of-both-worlds framework for fair allocation of indivisible goods, with a focus on stronger ex-post guarantees.

The paper studies two sided matching where one side has matroid rank valuations and the other side has unit demand valuations.

A new dictator test for allocation problems with applications to Nash welfare, budgeted allocation and GAP.

A framework that implies efficient algorithms for almost all fairness objectives when agents have binary submodular valuations. Subsumes our AAMAS 2023 and EC 2023 papers.

Hardness results for fair allocation under ternary valuations. We also prove an important result about order neutral submodular valuations, generalizing a result from our WINE 2023 paper.

Improved results on multi-draft speculative decoding. This paper contains a surprising connection between multi-draft speculative decoding and total unimodularity.

How to assign a set of numbers to the vertices of a graph so as to minimize the sum of absolute differences along the edges? Subsumes our AAMAS 2023 paper.

A new method to generate counterfactual explanations for machine learning models.

Approximation algorithms for the graphical house allocation problem studied in our AAMAS 2023 paper. Also, Ramanujan graphs and a cool connection between graph cuts and bitstrings.

Cooperative game theory meets formal logic meets model explanations!

Thanks to Arpita, I got to be co-author of a book chapter!

Fair allocation of indivisible items when agents valuations are submodular and each item has a marginal contribution of -1, 0 or some positive integer c.

Algorithms for fair allocation of indivisible items when agents valuations are submodular and each item has a marginal contribution of 1 or some positive integer c.

A framework that implies efficient algorithms for almost all fairness objectives when agents have binary submodular valuations. Superseded by our TEAC 2025 paper.

A fast algorithm to compute leximin allocations when agents have binary submodular valuations. Superseded by our TEAC 2025 paper.

How to assign a set of numbers to the vertices of a graph so as to minimize the sum of absolute differences along the edges? Superseded by our JAAMAS 2024 paper.

Can we compute allocations that satisfy the envy-free up to any good (EFX) condition only for certain pairs of agents?

Can we hide the vulnerabilities of a web application by randomizing over multiple implementations?

Algorithms to compute approximate market equilibria when the only knowledge of agent preferences comes from samples.

Allocating scarce firefighting resources to different regions under uncertainty.