Monday (May 26)
|
Tuesday (May 27)
|
Wednesday (May 28)
|
Thursday (May 29)
|
9:00
Introduction
9:15
David Woodruff
Turnstile Streaming Algorithms
Might as Well Be Linear Sketches
Edo Liberty
Simple and Deterministic Matrix
Sketching
Dan Feldman
Sublinear Systems using Core-sets
10:45 BREAK
11:15
Ryan O’Donnell
Testing Surface Area
Deeparnab Chakrabarty
Property Testing under
Product Distributions
Sofya Raskhodnikova
L_p-Testing
|
9:00
Venkatesan Guruswami
Reed-Muller testing:
implications for small set expansion & hypergraph
coloring
Shubhangi Saraf
Breaking the quadratic barrier for
3-LCCs over the Reals
Elena Grigorescu
Tight lower bounds for testing
linear isomorphism
10:30 BREAK
11:00
Amit Chakrabarti
Submodular Maximization in a
Data Streaming Setting
Robert Krauthgamer
The Sketching Complexity of
Graph Cuts
Graham Cormode
Parameterized Streaming
Algorithms for Vertex Cover
|
9:00
Greg Valiant
Finding correlations in
subquadratic time: new thoughts and applications
Suresh Venkatasubramanian
A directed
isoperimetric inequality with application to Bregman
near neighbor lower
Alexandr Andoni
Parallel Algorithms for Geometric
Graph Problems
10:30 BREAK
11:00
Ronitt Rubinfeld
Testing distributions in a
kinder, gentler world
Paul Valiant
Instance Optimal Identity
Testing
|
9:00
Eldar Fischer
Partial testing, universal
testing and decomposability
Yuichi Yoshida
A Characterization of Locally
Testable Affine-Invariant Properties via Decomposition
Theorems
Qin Zhang
New Directions in Distributed
Monitoring
10:30 BREAK
11:00
Valerie King
Impromptu Updating of a Dynamic
Network
Shiri Chechik
Approximate Distance Oracles with
Constant Query Time
Andrew McGregor
Graph
Algorithms in the Sliding Window Model
|
13:00 Lunch
|
13:00 Lunch
|
13:00 Lunch
|
13:00 Lunch
|
15:00
Jelani Nelson
Dimensionality reduction via sparse
matrices
Rachel Ward
Linear dimension reduction in the l1
norm: When is it possible? How is it possible?
16:00 BREAK
16:30
Artur Czumaj
Testing Cluster Structure of
Graphs
Krzysztof Onak
A Near-Optimal Algorithm for
Testing Isomorphism of Two Unknown Graphs
17:30 SHORT BREAK
17:45
Short announcements
|
15:00
Ely Porat
Group Testing, Compressed Sensing
and Algorithmic Applications
Mark Davenport
Adaptive sensing of sparse
signals in noise
16:00 BREAK
16: 30
Michael Mahoney
Implicit regularization in
sublinear approximation algorithms
Venkat Chandrasekaran
Computational and
Statistical Tradeoffs via Convex Relaxation
|
15:00
Eric Price
Sharp bounds for learning a mixture
of two Gaussians
Andrea Montanari
Principal Component Analysis
with Structured Factors
16:00 BREAK
16:30
Vladimir Braverman
Approximating Large Frequency
Moments with $O(n^{1−2/k})$ Bits
17:00 SHORT BREAK
17:15
Open problems
|
Workshop adjourns
|
19:30 Dinner
|
19:30 Dinner
|
19:30 Dinner
|
|