Workshop on coding theory, complexity and sparsity

Atri Rudra asks me to post an announcement for the second incarnation of the workshop on coding theory, complexity and sparsity. The first event went off quite well - I was sure that Dick Lipton had a post on it but I couldn't find it (Update: here it is, thanks to Atri). At any rate, do attend and get your students to attend: they have a great roster of speakers and travel support for students.

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.
These will be hour-long lectures designed to give students an introduction to coding theory, complexity theory/pseudo-randomness, and compressive sensing/streaming algorithms.

We will have a poster session during the workshop and everyone is welcome to bring a poster but graduate students and postdocs are especially encouraged to give a poster presentation.

Confirmed speakers:

• Eric         Allender          Rutgers
• Mark       Braverman      Princeton
• 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 

We have some funding for graduate students and postdocs. For registration and other details, please look at the workshop webpage: https://sites.google.com/site/umccsworkshop2012/