• Click on the titles of individual talks for abstract, slides and archived video (available approximately one week after the conclusion of the workshop).

–
Coffee and Check-In
–
Opening Remarks
–
A Brief Intro to Analysis Beyond the Worst Case
Avrim Blum, Carnegie Mellon University
–
Learning Probabilistic Models for Graph Partitioning in the Presence of Noise
Aravindan Vijayaraghavan, Northwestern University
–
Break
–
Clustering Under Perturbation Resilience
Colin White, Carnegie Mellon University
–
Lunch
–
On the Effect of Randomness on Planted 3-Coloring Models
Uriel Feige, Weizmann Institute
–
Analyzing Algorithms on Real World Data
Cliff Stein, Columbia University
–
Break
–
Applied Mixed Integer Programming: Beyond 'The Optimum'
Pawel Lichocki, Google
–
Impromptu Talks Session
–
Reception
–
Coffee and Check-In
–
Distribution-Specific Analysis of Nearest Neighbor Search and Classification
Sanjoy Dasgupta, UC San Diego
–
Spectral Approaches to Nearest Neighbor Search
Robert Krauthgamer, Weizmann Institute
–
Break
–
Timing Matters: Online Dynamics in Broadcast Games
Shuchi Chawla, University of Wisconsin - Madison
–
Lunch
–
A Theoretical Approach to Semantic Coding and Hashing
Sanjeev Arora, Princeton University
–
Automatic Resource Bound Analysis and Linear Optimization
Jan Hoffmann, Carnegie Mellon University
–
Break
–
Beyond Big-O: Statistical Analysis of Performance Scaling
Holger Hoos, University of British Columbia
–
Impromptu Talks Session
–
Coffee and Check-In
–
Self-Improving Algorithms for Sorting and Geometric Problems
Ken Clarkson, IBM Almaden
–
A PAC Approach to Application-Specific Algorithm Selection
Rishi Gupta, Stanford University
–
Break
–
Learning the Best Agorithm for Max-Cut, Clustering, and Other​ ​Partitioning Problems
Vaishnavh Nagarajan, Carnegie Mellon University
–
Learning as a Tool for Algorithm Design and Beyond-Worst-Case Analysis
Kevin Leyton-Brown, University of British Columbia
–
Lunch
–
Breakout Groups
–
The Computational Benefit of Correlated Instances
Shafi Goldwasser, Massachusetts Institute of Technology
–
Discussion
–
Coffee and Check-In
–
Recovery Guarantee of Non-Negative Matrix Factorization via Alternating Updates
Yingyu Liang, Princeton University
–
Characterizing the Typical Case Complexity of Formal Verification and Synthesis
Sanjit Seshia, UC Berkeley
–
Break
–
Beyond Worst Case: When Complex Feedback Can Improve the Label Complexity of Active Learning
Kamalika Chaudhuri (UC San Diego)
–
Lunch
–
Exploiting Myopic Prediction Models in Reinforcement Learning
Craig Boutilier, Google and University of Toronto
–
Follow the Leader with Dropout Perturbations
Manfred Warmuth, UC Santa Cruz
–
Break
–
When Does Clustering Become Easy, and Should We Care About Other Cases?
Shai Ben-David, University of Waterloo
–
Sketching and Randomization for Distributed Submodular and Coverage Optimization
Vahab Mirrokni, Google
–
Impromptu Talks Session
–
Coffee and Check-In
–
Automated Scientific Discovery Using Insights from Problem Structure
Bart Selman, Cornell University
–
How Hard Is Inference for Structured Prediction?
Tim Roughgarden, Stanford University
–
Break
–
Monotone Estimation Framework and its Applications for Scalable Analytics of Large Data Sets
Edith Cohen, Google Research
–
Lunch
–
Above Average-Case Analysis?
Ankur, Moitra, Massachusetts Institute of Technology
–
When Existing Techniques in Linear Regression Preserve Differential Privacy
Or Sheffet, University of Alberta 
–
Break
–
The Power of Predictions in Online Optimization
Adam Wierman, California Institute of Technology
–
Impromptu Talks Session