Institute for Advanced Study

School of Mathematics

Princeton, New Jersey







Workshop on Asymptotic and Computational Aspects of Coding Theory

March 25, 2001 - March 30, 2001





Johan Hastad - Royal Institute of Technology/IAS

Ran Raz - The Weizman Institute of Science/IAS

Alex Samorodnitsky - Institute for Advanced Study

Madhu Sudan - MIT

Avi Wigderson - Institute for Advanced Study




The Workshop will be held in Simonyi Hall.


Messages for workshop guests may be left by calling (609) 734-8100 and will be placed on the bulletin board in the lobby of Simonyi Hall.




Sunday March 25


9:30   Welcome


9:35   Vladimir Levenshtein

       Coding theory and asymptotic efficiency of two-stage testing


10:30  Break


11:00  Alexander Barg

       Linear codes with many light vectors Paper


11:30  Alexei Ashikhkmin

       Estimates of the Distance Distribution of Codes and Designs Abstract, Slides1


12:00  Lunch


2:30  Nati Linial

       Codes and Girth


3:15  Refreshment Break


3:30  Iwan Duursma

       Good self-dual codes and curves with many points Papers


4:00  Patrick Sole Slides

       Good self-dual quasi-cyclic codes exist



Monday, March 26



 9:30  Patrick Sole

       On the algebraic structure of quasi-cyclic codes


10:30  Refreshment Break


11:00  Michael Mitzenmacher Paper

       Extending Gallager codes to channels with memory


11:30  Alexei Ashikhkmin Abstract, Slides

       Quantum Codes: Constructions and Parameters


12:00  Lunch (IAS Dining Hall)


2:00  Shlomo Hoory Abstract, Paper

       The Moore bound for irregular graphs.


2:45  Refreshment Break (Fuld Hall Common Room)


3:30  William Martin

       The biweight enumerator and Terwilliger's subconstituent algebra







Tuesday, March 27


 9:30  Madhu Sudan Paper, Other Papers

       Sublinear time (list-)decoding


10:30  Refreshment Break


11:00  Ralf Koetter Slides

       Error probability, minimum distance and setting weight in

       the algorithm of Guruswami Sudan.


12:00  Lunch (IAS Dining Hall)


2:00  Venkat Guruswami Slides, Paper

       List decoding: Combinatorics and some code constructions


2:30  Elchanan Mossel Abstract, Paper, Slides

       List decoding and VC-dimension of circuits.


3:00  Refreshment Break (Fuld Hall Common Room)


3:30  Tom Høeholdt Abstract

       Bounds on List Decoding of MDS-codes.


4:00  Jørn Justesen Slides

       General bounds for list decoding.


4:30  Yevgeniy Dodis Abstract, Paper, Slides

       Incremental Codes




Wednesday, March 28


 9:30  Louay Bazzi Abstract

       The Minimum Distance of Turbo Like Codes


10:00  Rudolf Ahlswede

       Concepts of performance parameters for channels


10:30  Refreshment Break


11:00  Noam Elkies Paper

        Nonlinear algebro-geometric code


12:00  Lunch (IAS Dining Hall)


2:00   Open Problem Session


6:30  Workshop dinner (Dilworth Room) (Reservation required by 3/19/01)






Thursday, March 29


12:00  Lunch (IAS Dining Hall)




Friday, March 30


12:00  Lunch (IAS Dining Hall)


2:00   Informal gathering (Simonyi Hall Seminar Room)