Preprints
- An Ω̃(log n log m) Information-Theoretic Lower Bound for Randomized Online Set Cover
[arXiv]
Published Papers
-
Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness
with Anish Hebbar, Ravi Kumar, Seffi Naor, and Debmalya Panigrahi
SODA 2027
[arxiv] -
Dynamic Contention Resolution Schemes
with Moran Feldman, Gregory Kehne, and Sherry Sarkar
SODA 2027
[arxiv] -
Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems
with Joseph Koutsoutis, Jesse Lerner, and Jiawei Yu
FOCS 2026
[arXiv] -
Stochastic Caching via Subset Entropy
with Ravi Kumar, Seffi Naor, and Debmalya Panigrahi
APPROX 2026
[arXiv], [doi] -
Competitive Bundle Trading
with Yossi Azar, Niv Buchbinder and Or Vardi
ICALP 2026
[arXiv], [doi] -
Trading Prophets with Initial Capital
with Yossi Azar, Niv Buchbinder and Or Vardi
SOSA 2026
[arXiv], [doi] -
Competitively Consistent Clustering
with Niv Buchbinder and Yue Yang
ICML 2025
[arXiv], [OpenReview] -
Pairwise-Independent Contention Resolution
with Anupam Gupta, Jinqiao Hu, and Gregory Kehne
IPCO 2024
Math Programming Special Issue
[arXiv], [doi], [Math Programming version] -
Set Covering with Our Eyes Wide Shut
with Anupam Gupta and Gregory Kehne
SODA 2024
[arXiv], [doi], [slides] -
Chasing Positive Bodies
with Sayan Bhattacharya, Niv Buchbinder, and Thatchaphol Saranurak
FOCS 2023
[arXiv], [doi], [talk], [slides] -
Competitive Algorithms for Block-Aware Caching
with Christian Coester, Seffi Naor, and Ohad Talmon
SPAA 2022
[arXiv], [doi] -
Random Order Set Cover is as Easy as Offline
with Anupam Gupta and Gregory Kehne
FOCS 2021
[arXiv], [doi], [HIM talk], [CMU talk], [short talk], [slides] -
Streaming Submodular Matching Meets the Primal-Dual Method
with David Wajc
SODA 2021
[arXiv], [doi], [talk] -
Fully-Dynamic Submodular Cover with Bounded Recourse
with Anupam Gupta
FOCS 2020
[arXiv], [doi], [long talk], [short talk] -
Finding Skewed Subcubes Under a Distribution
with with Parikshit Gopalan and Udi Wieder
ITCS 2020
[arXiv], [doi] -
The Online Submodular Cover Problem
with Anupam Gupta
SODA 2020
[doi], [arxiv], [talk] -
Robust Subspace Approximation in a Stream
with Anish Sevekari and David Woodruff
NeurIPS 2018
[doi] -
Beyond Sentential Semantic Parsing: Tackling the Math SAT with a Cascade of Tree Transducers
with Mark Hopkins, Cristian Petrescu-Prahova, Ronan Le Bras, Alvaro Herrasti, and Vidur Joshi
EMNLP 2017
[doi] -
FigureSeer: Parsing Result-Figures in Research Papers
with Noah Siegel, Zachary Horvitz, Santosh Kumar Divvala, Ali Farhadi
ECCV 2016
[doi]
PhD Thesis
Submodular Optimization Under Uncertainty
[pdf], [slides]
Old Stuff
- PTAS for MAP Assignment on Pairwise Markov Random Fields in Planar Graphs
with Eli Fox-Epstein and David Meierfrankenfeld
2015
[arXiv]