Bertinoro Workshop on Sublinear Algorithms 2011
The workshop was held in Bertinoro in May of 2011. 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 Piotr Indyk and Ilan Newman. Further details can be found at the workshop webpage.
Links
Open Problems
- Problem 36: Learning an $f$-Transformed Product Distribution
- Problem 37: Testing Submodularity
- Problem 38: Query Complexity of Local Partitioning Oracles
- Problem 39: Approximating Maximum Matching Size
- Problem 40: Testing Monotonicity and the Lipschitz Property
- Problem 41: Testing Acyclicity
- Problem 42: Graph Frequency Vectors
- Problem 43: Rank Lower Bound
- Problem 44: Approximating LIS Length in the Streaming Model
- Problem 45: Streaming Max-Cut/Max-CSP
- Problem 46: Fast JL Transform for Sparse Vectors
- Problem 47: Annotated Streaming
- Problem 48: Sketching Shift Metrics
- Problem 49: Sketching Earth Mover Distance
- Problem 50: Sparse Recovery for Tree Models
Workshop Participants
- Nir Ailon
- Noga Alon
- Alexandr Andoni
- Arnab Bhattacharyya
- Vladimir Braverman
- Amit Chakrabarti
- Graham Cormode
- Artur Czumaj
- Pierre Fraigniaud
- Oded Goldreich
- Nir Halman
- Sariel Har-Peled
- Piotr Indyk
- Tali Kaufman
- Robert Krauthgamer
- Oded Lachish
- Michael Mahoney
- Andrew McGregor
- Morteza Monemizadeh
- Jelani Nelson
- Ilan Newman
- Krzysztof Onak
- Ely Porat
- Sofya Raskhodnikova
- Ronitt Rubinfeld
- Rocco Servedio
- Madhu Sudan
- Ben Recht
- Justin Romberg
- Dana Ron
- C. Seshadhri
- Asaf Shapira
- Christian Sohler
- Gilad Tsur
- Paul Valiant
- Roger Wattenhofer
- David Woodruff
- Ning Xie
- Yuichi Yoshida
