Institute for Advanced Study

School of Mathematics

Princeton, New Jersey

 

 

 

 AGENDA

 

 

Workshop on Asymptotic and Computational Aspects of Coding Theory

March 25, 2001 - March 30, 2001

 

 

Organizers:

 

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)