HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
1999 IMA Summer Program:
Codes, Systems and Graphical Models
yong


Partially supported by the National Security Agency

August 2-13, 1999

Organizers:

G. David Forney, Jr.
Massachusetts Institute of Technology
LUSE27@email.mot.com
forney@lids.mit.edu

Brian Marcus
IBM Almaden Research Center
marcus@almaden.ibm.com

Joachim Rosenthal
University of Notre Dame
rosen@nd.edu

Alexander Vardy
University of California, San Diego
vardy@ece.ucsd.edu

Note: The registration for this summer workshop has been closed due to an overwhelming response.


The invention of turbo codes and other capacity-approaching codes has led to an exciting cross-fertilization of ideas between researchers from different backgrounds.

The aim of the workshop is to bring together mathematicians, computer scientists, and electrical engineers in the area of coding theory, systems theory and symbolic dynamics so that the techniques from one area can be applied to problems in the other area. The two weeks of the workshop will be subdivided into two main focus areas:

  Week 1:
Codes on Graphs and Iterative Decoding
Week 2:
Connections Among Coding Theory, System Theory and Symbolic Dynamics  

Week 1

CODES ON GRAPHS AND ITERATIVE DECODING

Belief propagation in Bayesian networks has been extensively studied in artificial intelligence since the work of Pearl a decade ago, and turbo codes have recently become a subject of much research in coding theory. In the past year or two it has been recognized that the iterative decoding algorithm used for turbo codes and other capacity-approaching schemes are instances of belief propagation. This has led to an explosion of work devoted to understanding and exploiting this connection. A related problem is that of representing a given code by a graph, such as a Bayesian network. A central impetus of much of this work is to understand why iterative algorithms work so well empirically on graphs with cycles, where practically no theoretical results are known. Experts in the dynamics of algorithms have also begun to be drawn into this work. The major focus of week 1 of the IMA workshop will be to bring together researchers in these various fields to better understand these emerging connections. This will be a natural follow-on to a special session on this subject at the upcoming 1998 MTNS conference (Mathematical Theory of Networks and Systems, among the most mathematical of the systems theory conferences).

Topics for week 1 include: Codes defined on graphs, iterative decoding algorithms, factor graphs, turbo codes, connections with Bayesian networks.

 

Week 2

CONNECTIONS AMONG CODING THEORY, SYSTEM THEORY AND SYMBOLIC DYNAMICS

Coding Theory, System Theory and Symbolic Dynamics have much in common as evidenced by the following list of research topics that play a prominent role in each:

  1. Construction of various types of finite- and finite-dimensional state representations of sequence spaces.
  2. Investigation of fundamental structural properties of sequence spaces, such as observability and controllability.
  3. Construction of input/output systems, i.e. mappings (or encoders) between sequence spaces.
  4. Understanding the special role that algebraic structure (in particular, linearity and duality) plays in 1,2 and 3.

Yet these subjects have developed somewhat independently, and each has its own language and points of view. Until recently there has been very little communication among researchers in these subjects. A main purpose of week 2 of the IMA workshop is to further the communication among researchers and stimulate connections among these subjects. Week 2 will aim to continue a successful series of interdisciplinary meetings that has included an IEEE Information Theory Workshop on Coding, Systems and Symbolic Dynamics in 1993 (Mansfield, MA), a special invited session at the IEEE Conference on Decision and Control in 1995 (New Orleans), and two special sessions at the MTNS in 1998 (Padova).

Topics for week 2 include: Behavioral system theory, input/output mappings between spaces of sequences, state space representations, group codes, trellis codes, multi-dimensional systems and codes.

The organizers plan a number of invited tutorial lectures specifically for interspecialty communication. Leading workers in each field will also be invited to present surveys of current research, with less emphasis on solved problems than on open ones. Finally, there will be both invited and contributed papers presenting recent research results.

We expect the attendees to represent electrical engineering, mathematics and computer science departments in both academia and industry. As coding theory is the glue that holds the two weeks together, we expect that it will mostly be a subset of the coding theory participants who will attend both weeks.

WORKSHOP SCHEDULE

Week 1: August 2-6, 1999 Monday Tuesday Wednesday Thursday Friday
Week 2: August 9-13, 1999 Monday Tuesday Wednesday Thursday Friday

All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.

WEEK 1: CODES ON GRAPHS AND ITERATIVE DECODING
August 2-6, 1999
SCHEDULE for MONDAY, AUGUST 2
HISTORY AND TUTORIALS Day
G. David Forney, Jr. (chair)
8:30 am Registration and Coffee Reception Room EE/CS 3-176
9:10 am Willard Miller, Fred Dulles,
and G. David Forney
Introduction and Welcome
9:30 - 10:30 am R. Michael Tanner
University of California-Santa Cruz
Error-Correcting Codes and Graph-based Algorithms: Origins, Successes, the Current Quests
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am - 12:00 pm Stephen B. Wicker
Cornell University
Markov Chains, Error Control, and the Advent of Turbo Coding
12:00 pm Lunch  
2:00-3:00 pm Frank R. Kschischang
University of Toronto
Factor Graphs and the Sum-Product Algorithm
4:00 pm IMA Tea IMA East, 400 Lind Hall
A variety of appetizers and beverages will be served.
SCHEDULE for TUESDAY, AUGUST 3
LOW DENSITY PARITY CHECK CODES DAY
R. Michael Tanner (chair)
9:15 am Coffee Reception Room EE/CS 3-176
9:30-10:30 am David J.C. MacKay
Cambridge University
Sparse Graph Codes
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am - 12:00 pm Robert J. McEliece
California Institute of Technology
Some Simple Codes that Are Good in Both Theory and Practice
12:00 pm Lunch  
2:00 - 3:00 pm Thomas J. Richardson
(Lucent Bell Labs)
Ruediger Urbanke

(Lucent Bell Labs)
Analysis and Design of Iterative Decoding Systems
3:00 pm Coffee Break Reception Room EE/CS 3-176
Contributed Talks and Informal Discussions
 
3:30 pm Amin Shokrollahi
Bell Labs
Capacity Achieving Low-density Erasure Codes
4:00 pm Gilles Zemor
ENST, Paris
Iterative Decoding of Cycle Codes of Graphs
4:30 pm Dakshi Agrawal
University of Illinois-Urbana Champaign
On the Phase Trajectories of the Turbo Decoding Algorithm
SCHEDULE for WEDNESDAY, AUGUST 4
INFERENCE DAY
Brendan J. Frey (chair)
9:15 am Coffee Reception Room EE/CS 3-176
9:30 - 10:30 am Tommi Jaakkola
Massachusetts Institute of Technology
Variational Methods for Inference
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am - 12:00 pm Radford M. Neal
University of Toronto
Sparse Matrix Methods and Probabilistic Inference Algorithms
12:00 pm Lunch  
2:00 - 3:00 pm Brendan J. Frey
University of Waterloo
Yair Weiss

University of California at Berkeley
The Sum-Product Algorithm in Gaussian Networks with Cycles
3:00 am Coffee Break Reception Room EE/CS 3-176
Contributed Talks and Informal Discussions
 
3:30 pm John B. Anderson
University of Lund
Properties of the Tailbiting BCJR Decoder
4:00 pm Amir Banihashemi
Carleton University
Tanner Graphs for Group Block Codes and Lattices: Construction and Complexity
4:30 pm Heeralal Janwa and Oscar Moreno
University of Puerto Rico
New Constructions of Ramanujan Graphs and Good Expander Graphs from Codes, Exponential Sums and Sequences
SCHEDULE for THURSDAY, AUGUST 5
Robert J. McEliece (chair)
9:15 am Coffee Reception Room EE/CS 3-176
9:30 - 10:30 am Randall E. Bryant
Carnegie Mellon University
Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am - 12:00 pm John Lafferty
Carnegie Mellon University
Trellises, Decision Diagrams, and Factor Graphs
12:00 pm Lunch  
2:00 - 3:00 pm James L. Massey
ETH Zurich and Lund University
Linear Systems over Fields and Rings, Linear Complexity, and Fourier Transforms
3:00 am Coffee Break Reception Room EE/CS 3-176
6:00 pm Workshop Dinner Bona Vietnamese Restaurant
Located near the IMA and the Day's Inn at 802 Washington Avenue, the south side of Washington very near the intersection of Washington and Oak St.
Phone: 612-331-5011
SCHEDULE for FRIDAY, AUGUST 6
CODING THEORY DAY Alexander Vardy (chair)
8:45 am Coffee Reception Room EE/CS 3-176
9:00 - 10:00 am G. David Forney, Jr.
Massachusetts Institute of Technology
Codes and Systems on Graphs: Generalized State Realizations
10:00 am Coffee Break Reception Room EE/CS 3-176
10:15 - 11:15 am Ralf Koetter
University of Illinois at Urbana-Champaign
Factor Graphs, Trellis Formations, and Generalized State Realizations
11:15 am Coffee Break Reception Room EE/CS 3-176
11:30 am Hans-Andrea Loeliger
Endora Tech AG, Switzerland
Decoding and Equalization: Iterative Algorithms and Analog Networks

Week 1: August 2-6, 1999 Monday Tuesday Wednesday Thursday Friday
Week 2: August 9-13, 1999 Monday Tuesday Wednesday Thursday Friday

All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.

WEEK 2: CONNECTIONS AMONG CODING THEORY, SYSTEM THEORY AND SYMBOLIC DYNAMICS
August 9-13, 1999

SCHEDULE for MONDAY, AUGUST 9
8:30 am Registration and Coffee Reception Room EE/CS 3-176
9:10 am Willard Miller, Fred Dulles,
Joachim Rosenthal, and Brian Marcus
Introduction and Welcome
Automata and Systems
Jorn Justesen (Chair)
9:30 am Roger W. Brockett
Harvard University
Dynamical Systems and their Associated Automata
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am - 12:00 pm Dominique Perrin
Université de Marne-la-Vallée
Symbolic Dynamics and Automata
Algebra and Geometry Applied to Systems
Ethan Coven (Chair)
1:30 pm Paul A. Fuhrmann
Ben Gurion University
A Polynomial Module Approach to Linear Systems Theory
2:30 pm Clyde Martin
Texas Tech University
Linear Systems as Vector Bundles on Spheres
3:30 pm Coffee Break Reception Room EE/CS 3-176
4:00 pm M.S. Ravi
Eastern Carolina University
An Algebraic Geometric Point of View to Linear Systems Theory
5:00 pm IMA Tea IMA East, 400 Lind Hall
A variety of appetizers and beverages will be served.
SCHEDULE for TUESDAY, AUGUST 10
8:45 am Coffee Reception Room EE/CS 3-176
Convolutional Codes
Karl Petersen (Chair)
9:00 am Rolf Johannesson
University of Lund
Woven Convolutional Codes: Encoder Properties and Error Exponents
10:00 am Roxana Smarandache
University of Notre Dame
Construction of Convolutional Codes with Large Free Distance
11:00 am Coffee Break Reception Room EE/CS 3-176
11:30 am Fabio Fagnani
Politecnico di Torino

Joint talk with Sandro Zampieri
Universita di Padova

On Convolutional Codes over Rings
Contributed Talks
Joachim Rosenthal (Chair)

All talks will be 25 minutes long, including questions.

2:00 pm Thomas Mittelholzer
IBM Zurich Research Laboratory
Duals over Artinian Rings and the MacWilliams Identity
2:30 pm Sergio R. Lopez-Permouth
Ohio University
Finite Fields, Permutations and Trellis
3:00 pm Coffee Break Reception Room EE/CS 3-176
3:30 pm Danrun Huang
St. Cloud State
Period Three, Chaos, and the Golden Mean Shift
4:00 pm Dharmendra S. Modha
IBM Almaden Research Center
Art of Constructing Low-complexity Encoders/Decoders for Constrained Block Codes
4:30 pm Natasha Jonoska
University of South Florida
On Encoding in DNA Words
SCHEDULE for WEDNESDAY, AUGUST 11
8:45 am Coffee Reception Room EE/CS 3-176
Multidimensional Systems
Jon Hall (Chair)
9:00 am Klaus Schmidt
University of Vienna
Multi-dimensional Symbolic Dynamical Systems
10:00 am Paul H. Siegel
University of California-San Diego
Capacity of Constrained Systems in One and Two Dimensions
11:00 am Coffee Break Reception Room EE/CS 3-176
11:30 am Paul A. Weiner
Saint Mary's University of Minnesota
Multidimensional Convolutional Codes
Systems Theory
Roy Adler (Chair)
2:00 pm Jan C. Willems
University of Groningen
Systems, States and their Representations
3:00 pm Coffee Break Reception Room EE/CS 3-176
3:30 pm Sanjoy Mitter
MIT
Path Space View of Probabilistic Systems
SCHEDULE for THURSDAY, AUGUST 12
8:45 am Coffee Reception Room EE/CS 3-176
Symbolic Dynamics and Applications
Uwe Helmke (Chair)
9:00 am M. Michael Boyle
University of Maryland
Applications of Symbolic Dynamics to the Structure Theory of Nonnegative Matrices
10:00 am Natasha Jonoska
University of South Florida
Multiplicities of SFT Covers
11:30 am Selim Tuncel
University of Washington
Codings of Markov Chains and Weighted Graphs
Contributed Talks
Brian Marcus (Chair)
2:00 pm Marie-Pierre Béal
Université de Marne-la-Vallée
A Finite State Version of the Kraft-McMillan Theorem
2:30 pm Olivier Carton
Université de Marne-la-Vallée
Asynchronous Sliding Block Maps
3:00 pm Coffee Break Reception Room EE/CS 3-176
3:30 pm Christiane Frougny
LIAFA
Deterministic Synchronization of Bounded Delay 2-tape Finite Automata
4:00-4:30 pm Michael E. O'Sullivan
University College Cork
The Key Equation for One-point Codes
4:30 - 5:00 pm Fernando Guzmán
Binghamton University
Ambiguity in Codes
6:00 pm Workshop Dinner Campus club
Located on the 4th floor of Coffman Student Union and serves a wide-ranging buffet. Coffman Union is located on the opposite side of Washington Avenue from the IMA and slightly to the west.
SCHEDULE for FRIDAY, AUGUST 13
8:45 am Coffee Reception Room EE/CS 3-176
Decoding and Interpolation
Zhe-Xian Wan (Chair)
9:00 am Margreet Kuijper
University of Melbourne
Algorithms for Decoding and Interpolation
10:00 am Patrick Fitzpatrick
National University of Ireland, Cork

Realization and Interpolation via Gröbner Bases
11:00 am Coffee Break Reception Room EE/CS 3-176
11:30 am Brian M. Allen
University of Notre Dame
Linear Systems Decoding of Convolutional Codes
Informal Contributed Talks
Lind Hall 409 with an option to switch to Lecture Hall EE/CS 3-180 contingent on the participants size

2:00 pm Karl Petersen
University of North Carolina
Good Measures for Bad Codes between SFT's
2:30 pm Ethan Coven
Wesleyan University
The Symbolic Dynamics of Tiling the Integers
3:00 pm Coffee Break IMA East Lind Hall room 400
3:15 pm Kimberly Johnson
University of North Carolina
Automata, and Pumping Lemmas for Beta-shifts
3:45 pm Paul Trow
University of Memphis
Mappings between Group Shifts

Week 1: August 2-6, 1999 Monday Tuesday Wednesday Thursday Friday
Week 2: August 9-13, 1999 Monday Tuesday Wednesday Thursday Friday

Connect With Us:
Go