DIMACS Workshop on Codes and Complexity

December 4-7, 2001
DIMACS Center, CoRE Bldg., Room 431, Rutgers University, Piscataway, NJ

Organizers:

Amin Shokrollahi, Digital Fountain, amin@digitalfountain.com

Daniel Spielman, MIT, spielman@math.mit.edu

Ruediger Urbanke, Ecole Polytechnique Federale de Lausanne (EPFL), rudiger.urbanke@epfl.ch

Special Focus on Computational Information Theory and Coding and the

Special Focus on Mathematics and the Foundations of Computer and Information Science.

Workshop Program:

Tuesday December 4, 2001

8:00 - 8:50     Breakfast and Registration

8:50 - 9:00     Welcome and Greeting: 
                Fred S. Roberts, DIMACS Director

9:00 - 9:15     Welcome and Greeting from the workshop organizers:
                Amin Shokrollahi, Digital Fountain
                Daniel Spielman, MIT
                Ruediger Urbanke, Ecole Polytechnique Federale 
                de Lausanne (EPFL)
   
9:15 - 10:15    Invited talk: Codes in Theoretical Computer Science

                SLIDES: Invited talk: Codes in Theoretical Computer Science
                David Zuckerman, University of Texas

10:15 - 10:45   Break

10:45 - 11:15   Extractor Codes
                Amnon Ta-Shma, Tel Aviv University

11:30 - 12:00   Some Codes Constructions from Group Actions
                Louay Bazzi, MIT

12:15 - 12:45   Cayley Expanders from linear codes
                Avi Wigderson, IAS

12:45 - 2:00    Lunch

2:00 - 3:00     Invited talk: Complexity of Capacity Achieving Codes
                Dan Spielman, MIT

3:15 - 3:45     Constant Degree Lossless Expanders and their Expander Codes
                Omer Reingold, IAS

3:45 - 4:15     Break

4:15 - 4:45     Bit-Optimal Decoding of Codes whose Tanner Graphs are Trees
                Emina Soljanin, Bell Labs

5:00 - 5:30     Iterative Coding Schemes: New Schedulings and
                Optical Implementations
                Amir Banihashemi, Carleton University


Wednesday December 5, 2001

8:30 - 9:00     Breakfast and Registration

9:00 - 10:00    Invited talk: Why "Practical" Decoding Algorithms are Not as Good as "Ideal" Ones?
                Andrea Montanari, ENS

10:15 - 10:45   Statistical Mechanics and Capacity Approaching Codes
                Nicolas Sourlas, ENS

10:45 - 11:15   Break

11:15 - 11:45   Statistical Physics, Error Correcting Codes and Cryptography
                Ido Kanter, Bar-Ilan University

12:00 - 12:30   MAP, Typical Set Decoding and the Magnetization Enumerator in LDPC
                 - A Statistical Physics View
                David Saad, NCRG

                SLIDES: MAP, Typical Set Decoding and the Magnetization Enumerator in LDPC
                 - A Statistical Physics View
                David Saad, NCRG

12:30 - 1:45    Lunch

1:45 - 2:45     Invited talk: Soft Decoding of Reed Solomon and AG Codes
                Under Different Optimality Criteria
                Ralf Koetter, UIUC

3:00 - 3:30     Applications of Local List-Decoding Algorithms
                Salil Vadhan, Harvard University

3:30 - 4:00     Break

4:00 - 4:45     Projection Algebra Analysis of Error-Correcting Codes
                Jonathan Yedidia, MERL 

5:00 - 5:30     Finite Length analysis of LDPC codes with large
                left degrees
                Junan Zhang, UCSD

                SLIDES: Finite Length analysis of LDPC codes with large
                left degrees
                Junan Zhang, UCSD


Thursday December 6, 2001

8:30 - 9:00     Breakfast and Registration

9:00 - 10:00    Invited talk: Complexity of AG codes
                Amin Shokrollahi, Digital Fountain

10:15 - 10:45   A [ N log(N) ]^3 Algorithm for the Construction of Algebraic
                Geometric Codes better than the Gilbert-Varshamov Bound
                Vijay Kumar, USC

10:45 - 11:15   Break

11:15 - 11:45   Algebraic Code constructions for iterative decoding
                Pascal Vontobel, ETH Zuerich

12:00 - 12:30   Error exponents of expander codes under linear-complexity
                decoding
                Alexander Barg, Bell Labs

12:30 - 2:00    Lunch

2:00 - 3:00     Invited talk: Network Coding for Capacity and Robustness
                Muriel Medard, MIT

3:15 - 3:45     Adversaries, Codes and Information
                Parikshit S. Gopalan, Georgia Tech

3:45 - 4:15     Break

4:15 - 4:45     Enhanced Iterative Decoding of Finite Length LDPC and Turbo
                Like Codes
                Marc Fossorier, University of Hawaii

5:00 - 5:30     Encoder Complexity Versus Minimum Distance
                Louay Bazzi, MIT


Friday December 7, 2001

8:30 - 9:00     Breakfast and Registration

9:00 - 10:00    Invited talk: Content distribution and Coding Theory
                Michael Luby, Digital Fountain

10:15 - 10:45   Verification Codes
                Michael Mitzenmacher, Harvard University

10:45 - 11:15   Break

11:15 - 11:45   Properties of Extrinsic Information Transfer Curves
                Alexei Ashikhmin, Bell Labs

12:00 - 2:00    Lunch

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage