The Power of Greedy for Online Minimum Cost Matching on the Line
Eric Balkanski, Yuri Faenza, and Noemie Perivier
EC 2023
Strategyproof Scheduling with Predictions
Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan
ITCS 2023
Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan
EC 2022
Learning Low Degree Hypergraphs
Eric Balkanski, Oussama Hanguir, and Shatian Wang
COLT 2022
The Simultaneous Semi-Random Model for TSP
Eric Balkanski, Yuri Faenza, and Mathieu Kubik
IPCO 2022
Deterministic Budget-Feasible Clock Auctions
Eric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tan
SODA 2022
The Limitations of Optimization from Samples
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
JACM (2022)
STOC 2017
Instance Specific Approximations for Submodular Maximization
Eric Balkanski, Sharon Qian, and Yaron Singer
ICML 2021
Robust Repeated First Price Auctions
Shipra Agrawal, Eric Balkanski, Vahab Mirrokni, and Balasubramanian Sivan
EC 2021
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
Operations Research (2021)
STOC 2019
The Adaptive Complexity of Maximizing a Gross Substitutes Valuation
Ron Kupfer, Eric Balkanski, Sharon Qian, and Yaron Singer
NeurIPS 2020 (Spotlight)
The FAST Algorithm for Submodular Maximization
Adam Breuer, Eric Balkanski, and Yaron Singer
ICML 2020
A Lower Bound for Parallel Submodular Minimization
Eric Balkanski and Yaron Singer
STOC 2020
On the Construction of Substitutes
Eric Balkanski and Renato Paes Leme
Mathematics of Operations Research (2020)
EC 2018
Secretary Ranking with Minimal Inversions
Sepehr Assadi, Eric Balkanski, and Renato Paes Leme
NeurIPS 2019
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
SODA 2019
Non-monotone Submodular Maximization in Exponentially Fewer Iterations
Eric Balkanski, Adam Breuer, and Yaron Singer
NeurIPS 2018
Approximation Guarantees for Adaptive Sampling
Eric Balkanski and Yaron Singer
ICML 2018
Learning to Optimize Combinatorial Functions
Nir Rosenfeld, Eric Balkanski, Amir Globerson, and Yaron Singer
ICML 2018
The Adaptive Complexity of Maximizing a Submodular Function
Eric Balkanski and Yaron Singer
STOC 2018
The Importance of Communities for Learning to Influence
Eric Balkanski, Nicole Immorlica, and Yaron Singer
NIPS 2017
Minimizing a Submodular Function from Samples
Eric Balkanski and Yaron Singer
NIPS 2017
Statistical Cost Sharing
Eric Balkanski, Umar Syed, and Sergei Vassilvitskii
NIPS 2017
The Sample Complexity of Optimizing a Convex Function
Eric Balkanski and Yaron Singer
COLT 2017
The Power of Optimization from Samples
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
NIPS 2016
Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization
Eric Balkanski, Andreas Krause, Baharan Mirzasoleiman, and Yaron Singer
ICML 2016
Bayesian Budget Feasibility with Posted Pricing
Eric Balkanski and Jason D. Hartline
WWW 2016
Mechanisms for Fair Attribution
Eric Balkanski and Yaron Singer
EC 2015
Simultaneous Cake Cutting
Eric Balkanski, Simina Brânzei, David Kurokawa, and Ariel D. Procaccia
AAAI 2014
Partial Word DFAs
Eric Balkanski, Francine Blanchet-Sadri, Matthew Kilgore, and Benjamin J. Wyatt
CIAA 2013, Best paper award
Journal version: “On the State Complexity of Partial Word DFAs” Theoretical Computer Science, 2015.