# Dortmund Workshop on Algorithms for Data Streams 2012

From Open Problems in Sublinear Algorithms

The workshop was held in Dortmund in July of 2012. Many open problems and research directions were discussed at the workshop or were posed during presentations. The original list of open problems was scribed by Alexandr Andoni and Alexander Munteanu. Further details can be found at the workshop webpage.

## Contents

## Links[edit]

## Open Problems[edit]

- Problem 51: “For All” Guarantee for Computationally Bounded Adversaries
- Problem 52: TSP in the Streaming Model
- Problem 53: Homomorphic Hash Functions
- Problem 54: Faster JL Dimensionality Reduction
- Problem 55: Applications of Clifford Algebras in Graph Streams
- Problem 56: Efficient Measures of “Surprisingness” of Sequences
- Problem 57: Coding Theory in the Streaming Model
- Problem 58: Signatures for Set Equality
- Problem 59: Low Expansion Encoding of Edit Distance
- Problem 60: Single-Pass Unweighted Matchings

## Workshop Speakers[edit]

- Alexandr Andoni
- Amit Chakrabarti
- Andrew McGregor
- Anna Gilbert
- Atri Rudra
- Chris Schwiegelshohn
- Christian Konrad
- Christiane Lammersen
- Dan Feldman
- David P. Woodruff
- Ely Porat
- Eric Price
- Frederic Magniez
- He Sun
- Hossein Jowhari
- Jelani Nelson
- Joshua Brody
- Krzysztof Onak
- Lasse Kliemann
- Martin Strauss
- Melanie Schmidt
- Mert Seglam
- Mikhail Kapralov
- Qin Zhang
- Rina Panigrahy
- Sangkyun Lee
- Sudipto Guha
- Sumit Ganguly
- Suresh Venkatasubramanian
- TS Jayram
- Xiaoming Sun