# Bertinoro Workshop on Sublinear Algorithms 2014

The workshop was held in Bertinoro in May 2014. Many open problems and research directions were discussed at the workshop or were posed during presentations. The list of open problems was scribed by Suresh Venkatasubramanian and authors of the problems. Further information can be found at the workshop webpage.

## Links[edit]

## Open Problems[edit]

- Problem 61: RNA Folding
- Problem 62: Principal Component Analysis with Nonnegativity Constraints
- Problem 63: Submodular Matching Maximization
- Problem 64: Matchings in the Turnstile Model
- Problem 65: Communication Complexity of Connectivity
- Problem 66: Distinguishing Distributions with Conditional Samples
- Problem 67: Difficult Instance for Max-Cut in the Streaming Model
- Problem 68: Approximating Rank in the Bounded-Degree Model

## Workshop Participants[edit]

- Alexandr Andoni
- Vladimir Braverman
- Amit Chakrabarti
- Deeparnab Chakrabarty
- Venkat Chandrasekaran
- Moses Charikar
- Shiri Chechik
- Graham Cormode
- Artur Czumaj
- Mark Davenport
- Danny Feldman
- Eldar Fischer
- Elena Grigorescu
- Venkat Guruswami
- Piotr Indyk
- Valerie King
- Robert Krauthgamer
- Edo Liberty
- Michael Mahoney
- Claire Mathieu
- Andrew McGregor
- Andrea Montanari
- Jelani Nelson
- Ilan Newman
- Ryan O'Donnell
- Krzysztof Onak
- Ely Porat
- Eric Price
- Sofya Raskhodnikova
- Philippe Rigollet
- Ronitt Rubinfeld
- Shubhangi Saraf
- Christian Sohler
- Greg Valiant
- Paul Valiant
- Suresh Venkatasubramanian
- Rachel Ward
- David Woodruff
- Yuichi Yoshida
- Qin Zhang