Workshop on Coding Theory, Complexity Theory and Sparse Recovery

本次研讨会将汇集编码理论、复杂性理论和稀疏近似领域的主要研究人员，以促进这些社区之间的合作。大规模信息的高效传输、存储和检索是现代数字革命的核心技术问题之一。即使是传统上生成和分析小型“模拟”数据集的科学和技术领域，如生物学，现在也经常使用复杂的算法处理更大的离散数据。 大量的数据需要寻求数学和算法的方法来有效地描述，总结，合成，并越来越重要的是，决定何时以及如何丢弃数据之前存储或传输它。这样的方法已经在两个领域发展：编码理论和稀疏近似（SA）（及其变体称为压缩感知（CS）和流算法）。 这些领域提供了处理包含少量有趣或异常项的大型数据集的技术。编码理论是一个成熟的领域。 另一方面，虽然SA问题已经取得了重大进展，但大部分进展都集中在问题的可行性和某些算法解决方案上。对SA问题的计算复杂性的系统理解是非常缺乏的。研讨会的组织者旨在开发SA和CS的通用计算理论（以及相关领域，如组测试）。这一目标只能通过汇集来自各个领域的研究人员来实现，包括编码理论，它可以提供很多东西。该研讨会将把编码理论，复杂性理论和稀疏近似社区聚集在一起。讲习班将有可能导致在所有三个领域取得根本进展。在各自领域的研究生和博士后将是重要的受益者。 研讨会的规模和系列讲座的形式很小，这将使他们不仅能够听取这些研究人员的意见，而且能够在一个小的环境中与他们互动。我们计划在编码理论和稀疏近似方面进行几次辅导讲座。 讲座将进行录像，讲座材料将张贴在讲习班网站上。

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.