Publications
All publications
Research papers and preprints, newest first.
- Coresets for Capacitated Clustering via Dual Concentration SODA 2027
- Fault Tolerant Coresets NeurIPS 2026Coresets compress large datasets into small weighted summaries, but standard constructions assume the summary remains intact during storage and transmission. We show that sensitivity sampling yields coresets that can recover from up to $f$ adversarial corruptions with only an additive $O(fk/\varepsilon)$ size overhead for $k$-means, and prove that this dependence is optimal.
- Non-Clairvoyant Scheduling is Hard Even for Trees Preprint 2026We study online non-clairvoyant scheduling of DAG jobs on $m$ identical processors. Each job consists of unit-time subjobs connected by precedence constraints, but its DAG is initially unknown and each subjob is revealed only when it becomes ready. We show that the optimal competitive ratio for minimizing maximum flow time is $\Theta(\min\{m,\mathrm{OPT}\})$, even when every job is an out-forest. This is surprising because FIFO was previously known to be $O(\log m)$-competitive in several natural settings and was believed to retain this guarantee more generally.
- The Cube-Root Phenomenon in Online Carpooling Preprint 2026In online carpooling, edges arrive one at a time and must be oriented immediately, while keeping the imbalance between incoming and outgoing edges at every vertex small. We show that the natural greedy algorithm achieves $O(\min\{T^{1/3},n\})$ discrepancy, matching the known lower bound and resolving the longstanding cube-root versus square-root gap. We also obtain analogous cube-root improvements for random arrivals on regular graphs.
The classic power of two choices phenomenon says that when placing $n$ balls into $n$ bins, sampling two uniformly random bins for each ball and placing it in the less-loaded one keeps the maximum load across bins below $O(\log\log n)$.
We ask what happens when the two choices come from an arbitrary, possibly highly non-uniform distribution over bins. We observe that in this setting, surprisingly, the greedy strategy fails badly! The main contribution is a different algorithm that still keeps the maximum load within an $O(\log\log n)$ factor of the best possible.
- Approximation Preserving Coresets ICML 2026Standard coresets preserve the cost of every possible clustering solution, which can force pessimistic size bounds. We introduce approximation-preserving coresets, which focus on preserving good solutions and help explain why much smaller coresets often work well in practice.
- Coresets compress a large k-means instance into a small weighted sample that preserves the clustering objective. We show that sensitivity sampling achieves nearly optimal bounds for constructing k-means coresets, both in worst-case instances and in well-clustered data.
- Learning Multiple Secrets in Mastermind ICML 2024A set of binary strings is hidden. Each query is another binary string, and the response is whichever hidden string is closest in Hamming distance. How many queries are needed to recover the full hidden set? This simple question is wide open; we make partial progress on it.
- In classical makespan minimization, the goal is to assign jobs to machines so that no machine receives too much total load. We study a broad generalization where each machine measures its load using a different norm. While many special cases admit good approximation algorithms, we show that the general problem is much harder.
- The Greenwald-Khanna algorithm estimates quantiles in a data stream using little memory. We extend it to weighted streams, where each item may stand for many copies, without explicitly expanding those copies.