Schedule of Activities

Thursday, August 2 (Microsoft Research, Building 99, Room 1919)

9am -- 10:30am: Welcome + Short Talks (10 mins each)
- Shayan Oveis Gharan -- Rounding by Sampling Method and the Traveling Salesman Problem
- Anna Blasiak -- Broadcasting with Side Information
- Anindya De -- Computing Some Optimal Constants in Fourier Analysis
- Michael Forbes -- On Identity Testing of Tensors, Low-rank recovery and Compressed Sensing
- Zhiyi Huang -- The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
10:20 -- 10:50am: Break
10:50 -- 11:00am: Welcome from Peter Lee, Corporate Vice President, Microsoft Research Redmond.
11:00 -- 12:00pm: Special invited talk: Uri Feige -- How To Refute Random Nonsatisfiable Formulas
12:00 -- 1:30pm: Lunch
1:30 -- 1:55pm: Anna Karlin -- Strong Truthfulness and Externality-Resistant Mechanisms
2:00 -- 2:25pm: Yuval Peres -- Planted Cliques and Local Partitioning in Massive Graphs
2:30 -- 2:55pm: Anup Rao -- Recovering from Adversarial Error in Boolean Circuits
3:00 -- 3:30pm: Tea Break
3:30 -- 5:30pm: Short Talks (10 mins each)
- Mohammad Moharrami -- Max-flow min-cut gap in node-capacitated networks
- Bernhard Haeupler -- Optimal Communication in Radio Networks
- Huy Nguyen -- On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
- Eric Price -- Nearly Optimal Sparse Fourier Transform
- Alina Ene -- Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
- Ankit Sharma -- Welfare and Profit maximization with Procurement costs
- Anand Louis -- Higher Order Cheeger Inequalities
- Balasubramanian Sivan -- Auctions vs Negotiations in Irregular Markets
6:30pm: Dinner

Friday, August 3 (outing + University of Washington, Computer Science Building, Gates Commons)

9am -- 3:30pm : Hike to Snow lake trail, Snoqualmie Pass.

6pm -- 8:00pm : Dinner + Short Talks (10 mins each)
- Piyush Srivastava -- Lee-Yang theorems and the complexity of computing averages
- Elette Boyle -- Multiparty Computation Secure Against Continual Memory Leakage
- Li-Yang Tan -- Attribute-efficient learning and weight-degree tradeoffs for polynomial threshold functions
- Jonathan Ullman -- Answering n^{2 + o(1)} Counting Queries with Differential Privacy is Hard
8:00 -- 9pm: Open Problem Session I

Saturday, August 4 (University of Washington, Computer Science Building, Gates Commons)

9am -- 9:25am: Nikhil Devanur -- Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching
9:30 -- 9:55am: James Lee -- Discrete differentiation and local rigidity
10:00 -- 10:25am: Mohit Singh -- Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
10:30 -- 11:00am: Break
11:00 -- 11:25am: Richard Peng -- Algorithm Design using Spectral Graph Theory
11:30 -- 11:55am: Yuan Zhou -- Approximability and Proof Complexity
12:00 -- 12:25pm: Justin Thaler -- Practical Verified Computation with Streaming Interactive Proofs
12:30 -- 2:30pm: Lunch
2:30 -- 3:30pm: Special invited talk: László Lovász -- Optimization in very large graphs
3:30 -- 3:45pm: Break
3:45 -- 5:30pm: Group Discussions/Speed Networking

Sunday, August 5; (University of Washington, Computer Science Building, Gates Commons)

9:15am -- 10am: Short Talks (10 mins each)
- Liana Yepremyan -- Sparse Halves in Triangle-Free Graphs
- Yufei Zhao -- The sparse regularity method
- Sushant Sachdeva -- Fast algorithms for Balanced Separator by simulating random walks
10:00 -- 10:25am: Matt Weinberg -- Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization
10:30 -- 11:00am: Break
11:00 -- 11:25am: Kostya Makarychev -- Algorithms for Semi-random Graph Partitioning Problems
11:30 -- 11:55am: Eyal Lubetzky -- Mixing for colorings, independent sets, random walks: sharp transition or steady convergence?
12:00 -- 12:25pm: Paul Beame -- Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
12:30 -- 12:55pm: Rafael Frongillo -- Minimax Option Pricing Meets Black-Scholes in the Limit
1:00 -- 2:30pm: Lunch
2:30 -- 2:55pm: Sigal Oren -- On Bitcoin and Red Balloons
3:00 -- 3:30pm: Tea Break
3:30 -- 5:00pm: Open Problem Session II

Hike -- Friday, August 3

Summary: The Snow Lake trail is one of the most heavily used in the Northwest, and for good reason! It has beautiful scenery, and great views of the Snoqualmie Valley. Once you arrive at the top of the ridge, you hike down into a bowl, with Snow Lake, awaiting, as your reward. This is one of the largest lakes in the Alpine Lakes Wilderness Area. Bring a bathing suit if you like cold water.

Trail Data: Snow Lake is eight miles round trip, elevation gain 1,700 feet. Check out the photos here.

If you wish to go on the hike, please bring some decent shoes and a small backpack. You will need the backpack to carry a boxed lunch and a liter of water that we will be providing to those students attending the hike.