publications

2024

  1. From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection
    Vaggos Chatziafratis, Ishani Karmarkar, and Ellen Vitercik
    2024
    arXiv Video Slides
  2. MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
    Alexandre Hayderi, Amin Saberi, Ellen Vitercik, and Anders Wikum
    In International Conference on Machine Learning (ICML) , 2024
    arXiv Slides
  3. Bandit Profit-maximization for Targeted Marketing
    Joon Suk Huh, Ellen Vitercik, and Kirthevasan Kandasamy
    In ACM Conference on Economics and Computation (EC) , 2024
    arXiv
  4. Learning to Branch: Generalization Guarantees and Limits of Data-Independent Discretization
    Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik
    Journal of the ACM. Supersedes the ICML’18 paper below , 2024
    HTML
  5. New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
    Siddharth Prasad, Ellen Vitercik, Maria-Florina Balcan, and Tuomas Sandholm
    Preliminary version: poster at the Mixed Integer Programming Workshop (MIP) , 2024
    arXiv
  6. How Much Data Is Sufficient to Learn High-performing Algorithms?
    Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik
    Journal of the ACM. To appear. Supersedes the STOC’21 paper below , 2024
    HTML

2023

  1. Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms
    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
    Operations Research. To appear. Supersedes the EC’18 paper below , 2023
    arXiv
  2. Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty
    Wenshuo Guo, Nika Haghtalab, Kirthevasan Kandasamy, and Ellen Vitercik
    In ACM Conference on Economics and Computation (EC) , 2023
    Exemplary AI Track Award arXiv Video Slides
  3. Disincentivizing Polarization in Social Networks
    Christian Borgs, Jennifer Chayes, Christian Ikeokwu, and Ellen Vitercik
    In ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO) , 2023
    arXiv

2022

  1. Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
    Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik
    In Conference on Neural Information Processing Systems (NeurIPS) , 2022
    arXiv
  2. No-Regret Learning in Partially-Informed Auctions
    Wenshuo Guo, Michael Jordan, and Ellen Vitercik
    In International Conference on Machine Learning (ICML) , 2022
    arXiv
  3. Improved Sample Complexity Bounds for Branch-and-Cut
    Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik
    In International Conference on Principles and Practice of Constraint Programming , 2022
    arXiv

2021

  1. Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond
    Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik
    In Conference on Neural Information Processing Systems (NeurIPS) , 2021
    arXiv Poster Slides
  2. Revenue Maximization via Machine Learning with Noisy Data
    Ellen Vitercik, and Tom Yan
    In Conference on Neural Information Processing Systems (NeurIPS) , 2021
    PDF
  3. How Much Data Is Sufficient to Learn High-performing Algorithms? Generalization Guarantees for Data-driven Algorithm Design
    Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik
    In Proceedings of the Annual Symposium on Theory of Computing (STOC) , 2021
    arXiv PDF Video Poster Slides
  4. Private Optimization Without Constraint Violations
    Andrés Muñoz Medina, Umar Syed, Sergei Vassilvitskii, and Ellen Vitercik
    In International Conference on Artificial Intelligence and Statistics (AISTATS) , 2021
    arXiv Poster Slides
  5. Generalization in Portfolio-based Algorithm Selection
    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
    In AAAI Conference on Artificial Intelligence , 2021
    arXiv Poster Slides

2020

  1. Refined Bounds for Algorithm Configuration: The Knife-edge of Dual Class Approximability
    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
    In International Conference on Machine Learning (ICML) , 2020
    arXiv Video Slides
  2. Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees
    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
    In AAAI Conference on Artificial Intelligence , 2020
    arXiv Poster

2019

  1. Estimating Approximate Incentive Compatibility
    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
    In ACM Conference on Economics and Computation (EC) , 2019
    Exemplary AI Track Award and Best Presentation Award arXiv Video Poster Slides
  2. Learning to Prune: Speeding up Repeated Computations
    Daniel Alabi, Adam Tauman Kalai, Katrina Ligett, Cameron Musco, Christos Tzamos, and Ellen Vitercik
    In Conference on Learning Theory (COLT) , 2019
    arXiv Video Poster Slides
  3. Algorithmic Greenlining: An Approach to Increase Diversity
    Christian Borgs, Jennifer Chayes, Nika Haghtalab, Adam Tauman Kalai, and Ellen Vitercik
    In AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society (AIES) , 2019
    Poster Slides

2018

  1. Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
    Maria-Florina Balcan, Travis Dick, and Ellen Vitercik
    In Symposium on Foundations of Computer Science (FOCS) , 2018
    arXiv Poster Slides
  2. Learning to Branch
    Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik
    In International Conference on Machine Learning (ICML) , 2018
    arXiv Video Slides
  3. A General Theory of Sample Complexity for Multi-Item Profit Maximization
    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
    In ACM Conference on Economics and Computation (EC) , 2018
    arXiv Video Slides
  4. Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions
    Bernhard Haeupler, Amirbehshad Shahrasbi, and Ellen Vitercik
    In International Colloquium on Automata, Languages and Programming (ICALP) , 2018
    arXiv

2017

  1. Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
    Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White
    In Conference on Learning Theory (COLT) , 2017
    arXiv Slides

2016

  1. Sample Complexity of Automated Mechanism Design
    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
    In Conference on Neural Information Processing Systems (NeurIPS) , 2016
    arXiv Video Slides
  2. Learning Combinatorial Functions from Pairwise Comparisons
    Maria-Florina Balcan, Ellen Vitercik, and Colin White
    In Conference on Learning Theory (COLT) , 2016
    arXiv