| 1:00 - 1:30pm |
Coffee |
| 1:30 - 2:00pm |
Vitaly Feldman, Google |
A General Characterization of the Statistical Query Complexity |
| 2:00 - 2:30pm |
Luca Trevisan, UC Berkeley |
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification |
| 2:30 - 3:00pm |
David Woodruff, Carnegie Mellon University |
Sublinear Time Low Rank Approximation of PSD Matrices |
| 3:00 - 3:30pm |
Coffee break |
| 3:30 - 4:00pm |
Danupon Nanongkai, KTH Royal Institute of Technology |
Distributed Shortest Paths |
| 4:00 - 4:30pm |
Sanjam Garg, UC Berkeley |
Identity-Based Encryption from the Diffie-Hellman Assumption |
| 4:30 - 5:00 |
Aaron Sidford, Stanford University |
The Complexity of Submodular Function Minimization |
