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.