IMA Annual Program Year Workshop

Complexity, Coding, and Communications

Description:

Algebraic Geometry is by now well known to have fundamental applications to the theory of error-correcting codes and computational complexity. The connection to computational complexity dates back to the seminal works of A. Schönhage and V. Strassen in the 1960s, where they established fundamental links between notions and results in algebraic geometry with the complexity of computing algebraic functions. In the theory of error-correcting codes, the first significant links were established by V. D. Goppa, leading to the remarkable constructions due to Tsfasman, Vladuts and Zink of codes based on modular curves.

Such connections between algebraic geometry, computational complexity and coding theory have continued to be a rich source of inspiration for new results in coding and complexity theory through the decades, with major breakthroughs in computational complexity (cf. Mulmuley, SIAM J. Computing 1999), simpler constructions of error-correcting codes, as well as simpler decoding algorithms emerging from this connection. Furthermore, the two connections are being further intensified by a new generation of researchers working in the nexus of all three areas, The aim of this workshop is to enable further interaction and research along these lines.

LIST OF CONFIRMED PARTICIPANTS