Overview: There has been a great deal of interest in high-dimensional inference problems including streaming, sketching, compressed sensing, and matrix completion. In particular, recent efforts have developed sharp theoretical performance bounds as well as efficient algorithms that closely approach these limits.
Canonical Problems: How can we reliably infer a property of a large data set while sampling as few points of the data set as possible? Sublinear algorithms have played an important role both in theoretical computer science and in applications. While very natural connections between information theory and these problems exist, they are not being presently fully exploited on the CS side, giving rise to new exciting opportunities.
Keywords: streaming, sketching, sublinear algorithms, compressed sensing, matrix completion.