Workshop on Coding Theory, Complexity Theory and Sparse Recovery

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

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.