Efficient and effective transmission, storage, and retrieval of information on a large-scale are among the core technical problems in the modern digital revolution. The massive volume of data necessitates the quest for mathematical and algorithmic methods for efficiently describing, summarizing, synthesizing, and, increasingly more critical, deciding when and how to discard data before storing or transmitting it. Such methods have been developed in two areas: coding theory, and sparse approximation (SA) (and its variants called compressive sensing (CS) and streaming algorithms).

Coding theory and computational complexity are both well established fields that enjoy fruitful interactions with one another. On the other hand, while significant progress on the SA/CS problem has been made, much of that progress is concentrated on the feasibility of the problems, including a number of algorithmic innovations that leverage coding theory techniques, but a systematic computational complexity treatment of these problems is sorely lacking. The workshop organizers aim to develop a general computational theory of SA and CS (as well as related areas such as group testing) and its relationship to coding theory. This goal can be achieved only by bringing together researchers from a variety of areas. We will have several tutorial lectures that will be directed to graduate students and postdocs.

The first workshop in this series was held last year from August 1-4 at Ann Arbor.


Instructional Tutorials:
These will be hour-long lectures designed to give students an introduction to the area.

  • Mark Braverman, Communication/Information Complexity
  • Piotr Indyk, Compressed Sensing/Data stream algorithms
  • Shubhangi Saraf, Coding theory
  • Chris Umans, Pseudorandomness

Confirmed speakers:

Eric  Allender Rutgers 
Mark  Braverman  Princeton 
Amit     ChakrabartiDartmouth College
Mahdi  Cheraghchi  Carnegie Mellon University  
Anna  Gal  The University of Texas at Austin 
Piotr  Indyk  MIT 
Swastik  Kopparty  Rutgers 
Dick  Lipton  Georgia Tech 
Andrew  McGregor  University of Massachusetts, Amherst 
Raghu  Meka  IAS 
Eric  Price  MIT 
Ronitt  Rubinfeld  MIT 
Shubhangi  Saraf  IAS 
Chris  Umans  Caltech 
David  Woodruff  IBM 

All talks will be held in 411 West Hall. 

Travel support and Poster Session

Please see the page for students and postdocs for more details on travel support and the poster session. The poster session will be in the upper atrium of East Hall (on the second floor).



This material is based upon work supported by the National Science Foundation under Grant Numbers CCF-1161196 and CCF-1161233. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.