2019
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
STOC 2019
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
SODA 2019
2018
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
On the Construction of Substitutes
Eric Balkanski and Renato Paes Leme
EC 2018
Journal version in Mathematics of Operations Research (MOR)
The Adaptive Complexity of Maximizing a Submodular Function
Eric Balkanski and Yaron Singer
STOC 2018
2017
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 Limitations of Optimization from Samples
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
STOC 2017
2016
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
2015
Mechanisms for Fair Attribution
Eric Balkanski and Yaron Singer
EC 2015
2014
Simultaneous Cake Cutting
Eric Balkanski, Simina Brânzei, David Kurokawa, and Ariel D. Procaccia
AAAI 2014
2013
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.