Publications

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.