2020

A Lower Bound for Parallel Submodular Minimization
Eric Balkanski and Yaron Singer
STOC 2020

2019

Secretary Ranking with Minimal Inversions
Sepehr Assadi, Eric Balkanski, and Renato Paes Leme
NeurIPS 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.