Schedule & Slides


The theory workshop on streaming algorithms and related topics took place on July 23-27 at TU Dortmund University, Germany. The workshop roughly followed the schedule of a Dagstuhl seminar starting at Monday morning and ending Friday around noon, with plenty of space for discussions.

Here you can download the slides from the workshop.

Monday, July, 23rd



Time Speaker Title
09:30 – 10:00 - Welcome
10:00 – 11:00 Sudipto Guha Streaming, Certificates, and Near Linear Time Algorithms
11:00 – 11:30 - Break
11:30 – 12:15 Andrew McGregor Analyzing Graphs via Linear Sketching
12:15 – 15:00 - Lunch break
15:00 – 15:30 Christiane Lammersen (1+eps)-Approximation for Facility Location in Data Streams
15:30 – 16:00 Melanie Schmidt Constant-size Coresets for k-means and Projective Clustering
16:00 – 16:30 Dan Feldman Google your life: From Big (GPS) Data to a Searchable Diary
16:30 – 17:00 - Break
17:00 – 17:30 David P. Woodruff Low rank Approximation and Regression in Input Sparsity Time
17:30 – 18:00 Rina Panigrahy Efficient distance measures for Social Networks






Tuesday, July, 24th



Time Speaker Title
10:00 – 10:30 Eric Price Nearly Optimal Sparse Fourier Transform
10:30 – 11:00 Martin Strauss Sublinear Time, Measurement-Optimal, Sparse Recovery, For All
11:00 – 11:30 - Break
11:30 – 12:15 Atri Rudra One hammer to (algorithmically) rule them all: One Join at a time
12:15 – 15:00 - Lunch break
15:00 – 15:30 Anna Gilbert Sublinear Fourier Sampling Off the Grid
15:30 – 16:00 Alexandr Andoni Estimating eigenvalues in the streaming model
16:00 – 16:30 Ely Porat Homomorphic Signature (keynote file incl. animations)
16:30 – 17:00 - Break
17:00 – 17:45 Joshua Brody Streaming Algorithms with One-Sided Estimation
18:00 – open end - Open Problem Session




Wednesday, July, 25th



Time Speaker Title
10:00 – 10:30 Mikhail Kapralov On the communication and streaming complexity of maximum bipartite matching
10:30 – 11:00 Mert Saglam Lp Sampling from Streams
11:00 – 11:30 - Break
11:30 – 12:00 Xiaoming Sun Space Bounded Communication Complexity
12:00 – 12:30 Amit Chakrabarti Why data stream researchers should learn Talagrand's inequality
12:30 – 15:00 - Lunch break
15:00 – open end - Excursion






Thursday, July, 26th



Time Speaker Title
10:00 – 10:30 He Sun Counting Arbitrary Subgraphs in Data Streams
10:30 – 11:00 Christian Konrad Matching in randomly ordered graph streams
11:00 – 11:30 - Break
11:30 – 12:00 Krzysztof Onak Lower Bounds for Shortest Paths and Matchings
12:00 – 12:30 Hossein Jowhari Fast Protocols for Edit Distance through Locally Consistent Parsing
12:30 – 15:00 - Lunch break
15:00 – 15:30 Qin Zhang Rademacher Embedding, with an application to Earth-Mover Distance
15:30 – 16:00 Suresh Venkatasubramanian Distributed protocols for classification and optimization
16:00 – 16:30 - Break
16:30 – 17:00 Jelani Nelson On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
17:00 – 17:30 Lasse Kliemann Matching in Bipartite Graph Streams
17:30 – 18:00 Sumit Ganguly Polynomial Estimators for Data Stream Computations






Friday, July, 27th



Time Speaker Title
10:15 – 11:00 Frederic Magniez On the Streaming Complexity of Language Recognition
11:00 – 11:30 - Break
11:30 – 12:00 Sangkyun Lee Manifold Identification in Dual Averaging for Regularized Stochastic Online Learning
12:00 – 12:30 Chris Schwiegelshohn Clustering in Data Streams: Improving BIRCH
12:30 –
the end
- Open space for lunch, discussions, etc.