This workshop will get leading researchers from the areas of coding theory, complexity theory and sparse approximation together in order to foster collaborations among these communities. Efficient and effective transmission, storage, and retrieval of information on a large-scale are among the core technical problems in the modern digital revolution. Even areas of science and technology that traditionally generated and analyzed small ``analog'' data sets, such as biology, now routinely handle much larger, discrete data with sophisticated algorithmic processing. 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). These areas provide techniques for handling large data sets that contain a small number of interesting or anomalous items. Coding theory is a well established field. On the other hand, while significant progress on the SA problem has been made, much of that progress is concentrated on the feasibility of the problems and certain algorithmic solutions. A systematic understanding of the computational complexity of SA 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). This goal can be achieved only by bringing together researchers from a variety of area including coding theory which has much to offer.
The workshop will bring the coding theory, complexity theory and sparse approximation communities together. The workshop will potentially lead to fundamental progress in all the three areas. The graduate students and postdocs in the respective fields will be significant beneficiaries. The small size of the workshop and the format of the lectures series will allow them not only to listen to these researchers but also to interact with them in a small setting. We have several tutorial talks planned in coding theory and sparse approximation. The talks will be video-taped and lecture material will be posted on the workshop website.
In August, 2011, the PI and other organizers held a successful workshop. Approximately 50 people attended. As of report submission time, the workshop URL was accessible at www.math.lsa.umich.edu/conferences/coding/index.html . The participants were surveyed and were found to be generally enthusiastic. Example responses to "What did you hope to achieve by attending the workshop?" are below: • present new research, receive feedback, seek new ideas; • learn new techniques and ideas in sparsity, compressed sensing; • relations between compressed sensing to my own areas of interest, in particular pseudo randomness and explicit constructions; • to learn more about algorithmic problems arising in sparse approximation and compressed sensing; • learn more about recent work/ideas in compressed sensing and coding. A deeper understanding will help me in my current research, as well as increase the breadth of my knowledge in CS theory; A problem posed in an "open problem session" of our workshop was thereby brought to the attention of a participant, who later solved the problem; two conference papers resulted within a year. Tutorials were presented that were of interest to the local University community, including junior researchers and researchers from under-represented gropus. All of the survey respondents said they were "some what" or "very" likely to attend in 2012 if the workshop were to be held for a second time. Accordingly, the workshop will indeed be held again in 2012.
