Sublinear Algorithms Workshop 2016 at Johns Hopkins University

The workshop was held at the Johns Hopkins University in Baltimore in January 2016. This list contains open problems suggested by participants during the open problems session. The list of open problems was scribed by Clément Canonne, Gautam Kamath, and authors of the problems. Further information can be found at the workshop webpage.

Links

• Workshop webpage

Open Problems

• Problem 69: Correcting Independence of Distributions
• Problem 70: Open Problems in $L_p$-Testing
• Problem 71: Metric TSP Cost Approximation
• Problem 72: Communication Complexity of Approximating Set-Intersection Join
• Problem 73: Streaming Online Algorithms
• Problem 74: Succinct Representation for Functions on Graphs