Workshops

Fall 2016

Learning, Algorithm Design and Beyond Worst-Case Analysis

Nov 14, 2016 to Nov 18, 2016

Return to event »

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

Monday, November 14th, 2016
9:00 am–9:20 am		Coffee and Check-In
9:20 am–9:30 am		Opening Remarks
9:30 am–10:10 am		A Brief Intro to Analysis Beyond the Worst Case Avrim Blum, Carnegie Mellon University
10:10 am–10:50 am		Learning Probabilistic Models for Graph Partitioning in the Presence of Noise Aravindan Vijayaraghavan, Northwestern University
10:50 am–11:20 am		Break
11:20 am–12:00 pm		Clustering Under Perturbation Resilience Colin White, Carnegie Mellon University
12:00 pm–2:00 pm		Lunch
2:00 pm–2:40 pm		On the Effect of Randomness on Planted 3-Coloring Models Uriel Feige, Weizmann Institute
2:40 pm–3:20 pm		Analyzing Algorithms on Real World Data Cliff Stein, Columbia University
3:20 pm–3:50 pm		Break
3:50 pm–4:30 pm		Applied Mixed Integer Programming: Beyond 'The Optimum' Pawel Lichocki, Google
4:40 pm–5:00 pm		Impromptu Talks Session
5:00 pm–6:00 pm		Reception

Tuesday, November 15th, 2016
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:10 am		Distribution-Specific Analysis of Nearest Neighbor Search and Classification Sanjoy Dasgupta, UC San Diego
10:10 am–10:50 am		Spectral Approaches to Nearest Neighbor Search Robert Krauthgamer, Weizmann Institute
10:50 am–11:20 am		Break
11:20 am–12:00 pm		Timing Matters: Online Dynamics in Broadcast Games Shuchi Chawla, University of Wisconsin - Madison
12:00 pm–2:00 pm		Lunch
2:00 pm–2:40 pm		A Theoretical Approach to Semantic Coding and Hashing Sanjeev Arora, Princeton University
2:40 pm–3:20 pm		Automatic Resource Bound Analysis and Linear Optimization Jan Hoffmann, Carnegie Mellon University
3:20 pm–3:50 pm		Break
3:50 pm–4:30 pm		Beyond Big-O: Statistical Analysis of Performance Scaling Holger Hoos, University of British Columbia
4:40 pm–5:00 pm		Impromptu Talks Session

Wednesday, November 16th, 2016
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:10 am		Self-Improving Algorithms for Sorting and Geometric Problems Ken Clarkson, IBM Almaden
10:10 am–10:50 am		A PAC Approach to Application-Specific Algorithm Selection Rishi Gupta, Stanford University
10:50 am–11:20 am		Break
11:20 am–12:00 pm		Learning the Best Agorithm for Max-Cut, Clustering, and Other Partitioning Problems Vaishnavh Nagarajan, Carnegie Mellon University
12:00 pm–12:40 pm		Learning as a Tool for Algorithm Design and Beyond-Worst-Case Analysis Kevin Leyton-Brown, University of British Columbia
12:40 pm–2:00 pm		Lunch
2:00 pm–3:20 pm		Breakout Groups
3:20 pm–4:00 pm		The Computational Benefit of Correlated Instances Shafi Goldwasser, Massachusetts Institute of Technology
4:00 pm–5:00 pm		Discussion

Thursday, November 17th, 2016
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:10 am		Recovery Guarantee of Non-Negative Matrix Factorization via Alternating Updates Yingyu Liang, Princeton University
10:10 am–10:50 am		Characterizing the Typical Case Complexity of Formal Verification and Synthesis Sanjit Seshia, UC Berkeley
10:50 am–11:20 am		Break
11:20 am–12:00 pm		Beyond Worst Case: When Complex Feedback Can Improve the Label Complexity of Active Learning Kamalika Chaudhuri, UC San Diego
12:00 pm–2:00 pm		Lunch
2:00 pm–2:40 pm		Exploiting Myopic Prediction Models in Reinforcement Learning Craig Boutilier, Google and University of Toronto
2:40 pm–3:20 pm		Follow the Leader with Dropout Perturbations Manfred Warmuth, UC Santa Cruz
3:20 pm–3:50 pm		Break
3:50 pm–4:30 pm		When Does Clustering Become Easy, and Should We Care About Other Cases? Shai Ben-David, University of Waterloo
4:30 pm–5:10 pm		Sketching and Randomization for Distributed Submodular and Coverage Optimization Vahab Mirrokni, Google
5:10 pm–5:30 pm		Impromptu Talks Session

Friday, November 18th, 2016
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:10 am		Automated Scientific Discovery Using Insights from Problem Structure Bart Selman, Cornell University
10:10 am–10:50 am		How Hard Is Inference for Structured Prediction? Tim Roughgarden, Stanford University
10:50 am–11:20 am		Break
11:20 am–12:00 pm		Monotone Estimation Framework and its Applications for Scalable Analytics of Large Data Sets Edith Cohen, Google Research
12:00 pm–2:00 pm		Lunch
2:00 pm–2:40 pm		Above Average-Case Analysis? Ankur Moitra, Massachusetts Institute of Technology
2:40 pm–3:20 pm		When Existing Techniques in Linear Regression Preserve Differential Privacy Or Sheffet, University of Alberta
3:20 pm–3:50 pm		Break
3:50 pm–4:30 pm		The Power of Predictions in Online Optimization Adam Wierman, California Institute of Technology
4:40 pm–5:00 pm		Impromptu Talks Session