### 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
Presented under the auspices of the:
Special Focus on Computational Information Theory and Coding and the
Special Focus on Mathematics and the Foundations of Computer and Information Science.

#### Abstracts:


1.

Properties of Extrinsic Information Transfer Curves
Authors: Alexei Ashikhmin, Gerhard Kramer, and Stephan ten Brink

The extrinsic information transfer (EXIT) chart has been used to study
the convergence of iterative decoding of concatenated codes.  We study
some properties of EXIT charts for the case of the binary erasure
channel. In particular we show that for any block code the area under
the transfer curve of the outer code is the entropy of the code, e.g.,
the area is the code rate if the code is linear.  We further show that
the transfer curves of a linear code and its dual are connected by an
analytical expression.

2.

Amir Banihashemi, Carleton University
Iterative coding schemes: new schedulings and optical implementations

In the first part of this talk, we discuss new message-passing schedules
for the decoding of low-density parity-check (LDPC) codes. We show that
scheduling plays an important role in iterative decoding and that a
schedule that matches the structure of the Tanner graph and the reliability
of coding schemes considerably.

In the second part of the talk, we propose using optical components for
decoding digital information, based on the so-called iterative coding
schemes, such as turbo codes and LDPC codes. This suggests a significant
increase in speed compared to the conventional electronic decoding.

3.

Alexander Barg, Bell Labs
Error exponents of expander codes under linear-complexity decoding

A class of codes is said to reach capacity $\cC$ of the binary symmetric
channel (BSC) if for any rate $R<\cC$ and any $\epsilon>0$
there is a sufficiently large $N$ such that codes of length $\ge N$ from this
class provide error probability of decoding at most $\epsilon$, under some
decoding algorithm.

Expander codes are known to reach capacity
of the binary symmetric channel under linear-complexity iterative
decoding. Error probability for iterative decoding of expander codes
was shown by Barg and Z{\'e}mor (2001) to decrease exponentially with
code length for all code rates $0<R<\cC$.
In this work we focus on the most important region of code rates,
close to the channel capacity. For this region
we estimate the error exponent for a randomized ensemble of expander codes,
obtaining the best known error exponent provided by binary codes
under linear-time decoding.

Joint work with Gilles Zemor.

4.

Louay Bazzi, MIT
Encoder Complexity versus Minimum distance

The general  problem under investigation is the study of  the minimum
distance of  a code given constraints on the computational complexity
of it's encoder.

We argue  that if the encoder  is a branching program  of linear depth
and  subexponential width  -- or  equivalently,  if the  encoder is  a
(nonuniform)  RAM with  sublinear space  and linear  time --  then the
minimum  relative distance  of  the code  must  go to  zero.  We  give
applications  to   Turbo-Like  codes.  Our   argument  uses  Branching
Techniques introduced by Ajtai.

We  investigate  also  the case  when  the  encoder  is a  cascade  of
branching programs or a bounded depth circuit, in the addition to case
when the testing whether a given string is a a codeword is doable by a
bounded depth circuit.

Joint Work with Sanjoy Mitter and Dan Spielman.

5.

Louay Bazzi, MIT
Some Codes Constructions from  Group Actions

The general problem under investigation is the randomized and explicit
constructions of binary linear codes that are invariant under the
action of some group on the bits of the codewords.  We analyze an
Abelian randomized construction, a related explicit construction
connected to hyperelliptic curves, and a nonabelian randomized
construction.

We started by looking at one of the simplest randomized constructions
of such codes, namely rate half quasi-cyclic codes of prime message
length. So we have a cyclic Abelian group of prime order acting on two
disjoint copies of itself.  There is an old result on such codes that
says that a random rate half codes from this ensemble achieves the
Gilbert-Varshamov (GV) assuming that the Extended Riemann Hypothesis
(ERH) holds to get infinitely many special primes.  We argue that this
result holds without the need to assume the Extended Riemann
Hypothesis. Namely, for almost all primes a random quasi-cyclic code
achieves the GV bound.

In this ensemble of codes there is a natural explicit code based on
quadratic residues.  We conjecture that this codes achieves the binary
GV bound.  We show that the codewords in this codes are in one to one
correspondence with special hyperelliptic curves over a finite field
of prime order.  We can express the minimum distance of the code in
terms of the maximum numbers of rational points on a curves from this
family of curves, or equivalently in terms of the corresponding
character sums.  This leads to a conjecture about a bound tighter than
the general estimates from Weil's theorem for a special class of
curves.  Finally, we relate the code to a special cyclic quadratic
residue code over a nonbinary alphabet.

Next, we move to a slightly more general randomized construction.  We
consider the randomized construction of codes that are in invariant
under the action of an abelian group on a constant number of disjoint
copies of itself.  We argue that (when the order of the group is odd)
: If the smallest dimension of a nontrivial irreducible
$\F_2$-representation of the group grows faster than logarithmically
in terms of the number of elements in the group, then the resulting
codes achieve the Gilbert-Varshamov bound with a high probability.
We list many infinite families of groups satisfying the above
property.

When the group is nonabelian, we note that the story sounds different
since we can establish by counting arguments that the action of the
group on a single copy to itself can lead to asymptotically good codes
in the case of one of first nontrivial nonabelian groups -- namely the
dihedral group. We argue that for infinitely many block lengths a
random rate half ideal in the binary group algebra of the dihedral
group is asymptotically good with a high probability. Our result is
the first provably good randomized construction of codes that are
ideals in the group algebra of a group.  This leads to the question of
looking at randomized constructions in the group algebra of other
nonabelian groups.

Joint work with  Sanjoy Mitter and  Dan Spielman

6.

Marc Fossorier, University of Hawaii
Enhanced Iterative Decoding of Finite Length LDPC and Turbo Like Codes

In this presentation, the use of a reliability-based decoding algorithm
is examined to address and overcome the suboptimality of iterative decoding
for finite length codes. The a posteriori probabilities fed by the iterative
decoding are regarded as reliability information and an efficient algorithm for
the overall linear block code is applied at certain iterations.
Simulation results show that the suboptimality of iterative decoding
for moderate length codes can be at least partially compensated by this
achievable by the combined approach are investigated based on the
characteristics of the constituent decoders, which highlights the nature
of suboptimality in iterative decoding.

Joint work with Motohiko Isaka and Hideki Imai.

7.

Parikshit Gopalan, Georgia Tech

Abstract:  In this  talk  we describe  simple  techniques called  Code
Scrambling that allow  us to relate the average  performance of a code
to  the  worst-case performance  of  its  scrambled  version C'.   The
performance  of  a  scrambled  code  against  any  adversary  (even  a
computationally  unbounded   one),  equals  the   performance  of  the
unscrambled code against a symmetric channel. A symmetric channel is a
Markov chain that makes  random changes to random positions. Scrambled
versions of some  codes can correct errors beyond  the classical error
correction distance with negligible probability of failure.

We will show that Scrambled Reed Solomon codes of low rate can correct
nearly twice the number of errors that conventional Reed Solomon codes
can. We  discuss other  codes whose performance  is likely  to improve
with scrambling. We discuss some open questions that this work raises.

Joint work with Richard J. Lipton and Yan Zong Ding.

8.

Ido Kanter, Bar-Ilan University
Statistical Physics, Error Correcting Codes and Cryptography

Gallager-type  error-correcting codes  that nearly  saturate Shannon's
bound are  constructed using insight  gained from mapping  the problem
onto that of an Ising spins  system.  The construction is based on the
introduction of complex matrices,  used in both encoding and decoding,
which comprise sub-matrices of cascading connection values. The finite
size effects are estimated for comparing the results to the bounds set
by Shannon.  The critical noise level achieved  for certain code-rates
and  infinitely  large systems  nearly  saturates  the  bounds set  by
Shannon even  when the connectivity  used is low.  The  performance of
the  suggested  codes  is  evaluated  for  both  Gaussian  and  binary
symmetric channels.

In the  second part of the  talk a public-key cryptosystem  based on a
Gallager-type  parity-check error-correcting  code is  presented.  The
complexity  of  the  encryption  and the  decryption  processes  scale
linearly with  the size  of the plaintext.   The linear  complexity is
based on  the observation  that as long  as the  average connectivity,
(number  of non-zero  elements per  column) of  a square  matrix  B is
smaller  than  2, the  graph  representing  the  matrix is  below  the
percolation threshold and $B^{-1}$ is sparse too.

9.

Ralf Koetter, UIUC
Soft Decoding of Reed Solomon and AG Codes

Reed Solomon codes and algebraic geometric codes play a prominent role
in the construction of concatenated codes. The recent list decoding
algorithm of Guruswami-Sudan extends the correction radius of Reed
Solomon codes substantially beyond half the minimum distance.  The
central problem in using this algorithm in a concatenated coding
system is to find an assignment of weights to the received positions
for discrete channels and in particular channels that correspond to
concatenation with simple inner codes. Using these optimized weights
we can construct codes that on a binary symmetric channel and for
rates less that 0.125 perform essentially as well as codes achieving
the Gilbert-Varshamov bound.

10.

P. Vijay Kumar, University of Southern California - Los Angeles

A [ N log(N) ]^3 Algorithm for the Construction of Algebraic
Geometric Codes better than the Gilbert-Varshamov Bound

Since the proof in 1982, by Tsfasman Vladut and Zink of the
existence of algebraic geometric (AG) codes with asymptotic performance
exceeding the Gilbert-Varshamov (G-V) bound, one of the challenges in
coding theory has been to provide explicit constructions for these
codes.  In a major step forward in 1995-96, Garcia and Stichtenoth
(G-S) provided an explicit description of algebraic curves, such that
AG codes constructed on them would have performance better than the
G-V bound.  We present here the first low-complexity algorithm for
obtaining the generator matrix for AG codes on the curves of G-S.  The
symbol alphabet of the AG code is the finite field of q^2 >= 49,
elements.  The complexity of the algorithm, as measured in terms
of multiplications and divisions over the finite field GF(q^2), is
upper bounded by [N log_q(N)]^3 where N is the length of the
code.  An example of code construction using the above algorithm is
presented.

By concatenating the AG code with short binary block codes, it is
possible to obtain binary codes with asymptotic performance close to
the G-V bound.  Some examples of such concatenation are included.

This is joint work with K. Shum, I. Aleshnikov, H. Stichtenoth and
V. Deolalikar.

This research is supported by NSF under grant CCR-0073555.

11.

Michael Luby, Digital Fountain
Invited talk: Content distribution and Coding Theory

This talk will describe a new class of codes, called LT codes in the
commercial world.  The basic properties of the codes, and their
commercial applications to reliable massively scalable data
distribution, will be described.

12.

Muriel Medard, MIT
Network Coding for Capacity and Robustness

We present an overview of results in the area of network coding for
capacity and for robustness against permanent network failures. We also address
the relation between network coding and network management.

The first part of the talk addresses network capacity. Recent work by
Li, Yeung, Ahlswede and Cai examined the issue of network capacity for
multicast networks. These results showed that linear network coding is
sufficient for multicast networks and showed that the min-cut max-flow theorem
determines feasibility of multicast connections. More recently, Koetter and
Medard considered an algebraic approach to network coding and extended the
results to non-multicast networks. In particular, they showed that min-cut
max-flow necessary and sufficient conditions can be extended to a much larger
class of connections than multicast connections, but also showed that in
general min-cut max-flow conditions are necessary but not sufficient. In
general, the feasiblity of a connection can be found in polynomial time,
athough the complexity of finding network codes that satisfy these conditions
may not be polynomially bounded.

Network codes may be used not only to achieve capacity, but also to
provide robustness from permanent (non-ergodic) link or node failures. The
second part of the talk examines the issue of coding for robustness. We
overview traditional means of providing recovery in networks using switching
rather than coding. All of these methods can be shown to reduce to codes.
Koetter and Medard have shown the rather surprising fact that, for multicast
networks, recovery can be achieved using static codes in the interior of
the network. Thus, only the terminal nodes need to react to network changes
for multicast connections.

The issue of network codes for recovery is tightly linked to that of
network management, the topic of the third and final part of our talk. The log
of the number of codes that we may need to use in order to respond to
different failure scenarios may be taken to represent the number of network
management bits necessary to recover from network failures. We present some new
results by Ho, Medard and Koetter regarding the number of codes needed to
recover from failures. In particular,  they have shown some tight upper and
lower bounds for the number of codes necessary when using receiver-based and
network-wide codes.

13.

Michael Mitzenmacher, Harvard University
Title:  Verification codes

Current LDPC codes for error-correction focus on the bit level or on
symbols consisting only of a few bits.  We introduce new LDPC codes
designed to handle data at the packet level, where a packet consists
of a large number of bits.  By using a pseudorandom transformation of
the input data, we find simple linear time LDPC codes that can cope
with a large number of packet level errors with high probability.  Our
novel framework uses check packets to verify the correctness of
message packets as well as correct erroneous message packets.  We
provide an analysis of our verification codes and suggest several open
problems.

Joint work with Michael Luby.

14.

Andrea Montanari, ENS
Why "practical" decoding algorithms are not as good as "ideal" ones?

Good codes are usually characterized by the critical noise $n_c$ for
perfect error correction under ideal decoding. The conceptual frame
for understanding the abrupt phenomenon occurring at the critical
noise (namely the transition from an error-free regime to a
noise-dominated regime) is given by the Shannon theory.

On the other hand many practical (i.e. linear time) algorithms
have a no-error regime which ends at a lower "dynamical" critical noise.

We shall argue that one can define an optimal dynamical noise $n_d$
and that $n_d$ is characterized by an algorithm independent phenomenon.

Our argument is based on the analysis of simulated annealing decoding
and its comparison with belief propagation decoding.

15.

Omer Reingold, IAS
Constant Degree Lossless Expanders and their Expander Codes

We present the first explicit construction of constant degree
"lossless" expanders. In these graphs, the expansion factor is
almost as large as possible: (1-e)D, where D is the degree and e
is an arbitrarily small constant. The best previous explicit
constructions gave expansion factor D/2. The D/2 bound was
obtained via the eigenvalue method, and is the best possible using
this method [Kahale95].

We then discuss the expander codes [Gallager, Tanner,
Sipser-Spielman] that correspond to our lossless expanders. These
are new explicit linear codes of relative rate (1-delta) and
minimum distance (delta / polylog(1/delta)), which is quite close
to the Gilbert-Varshamov bound for small delta. Moreover, the
losslessness of our graphs implies a very simple linear-time
decoding algorithm (taken from [Sipser-Spielman]).

16.

MAP, Typical Set Decoding and the Magnetization Enumerator in LDPC
- A Statistical Physics View

We study the roles of both weight and magnetization enumerators in
decoding corrupted messages encoded using low density parity check
error correcting codes, using the methods of statistical physics. The
analysis, based on the replica method [1], provides an intuitive
interpretation of the relation between different decoding schemes such
as typical pairs decoding, MAP, and finite temperature decoding (MPM).
The predictions obtained for the critical noise level below which
successful decoding is theoretically possible, are more optimistic
than those derived via the methods of information theory and are in
excellent agreement with results obtained elsewhere, combining
Gallager's method and the statistical physics approach [2].  We also
show that the critical noise levels for typical pairs, MAP and MPM
decoding must coincide (as also proved in [3]), and provide an
intuitive explanation to the difference between MAP and MPM decoding
within the statistical physics framework.

[1] Nishimori, H.: Statistical Physics of Spin Glasses and Information
Processing. Oxford University Press, Oxford UK (2001).

[2] Kabashima, Y., Sazuka, N., Nakamura, K., Saad, D.: Tighter
Decoding Reliability Bound for Gallager's Error-Correcting Code:
Phys.Rev.E 64, 046113 (2001).

[3] MacKay, D.J.C.: On Thresholds of Codes: unpublished,
http://wol.ra.phy.cam.ac.uk/~mackay/CodesTheory.html  (2000).

Joint work with Jort van Mourik and Yoshiyuki Kabashima.

17.

Amin Shokrollahi, Digital Fountain
Complexity of AG codes

In this talk we will review some of the results on the running times
of various algorithms pertaining to Algebraic-Geometric codes.

18.

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

We introduce a group algebra formulation for bit optimal
decoding of binary block codes. We use this new framework
to give a simple algebraic proof that Pearl's and Gallager's
belief propagation decoding algorithms are bit-optimal
when the Tanner graph of the code is a tree.
We believe that these derivations of known results give new i
nsights into the issues of decoding on graphs from the algebraic
coding theorist's point of view.

19.

Nicolas Sourlas, ENS
Statistical Mechanics and Capacity Approaching Codes

It is known that there is a deep relation between error-correction codes
and certain mathematical models of spin glasses. I will show how the
recently discovered (or rediscovered) capacity approaching codes (turbo
codes and low density parity check codes) can be analysed
using statistical mechanics. It is possible to show, using statistical
mechanics, that these codes allow error-free communication for signal to
noise ratio above a certain threshold. This threshold, which corresponds
to a phase transition in the spin model, depends on the particular code,
and can be computed analytically in many cases.

20.

Amnon Ta-Shma, Tel Aviv University
Extractor Codes

Shannon showed that data can be communicated over  every channel with
positive  capacity. In  particular even  highly noisy  channels, e.g.,
when every received signal can originate from some half of the symbols
in the alphabet, can be used  to transmit information as long as noise
on different symbols is independent.

Hamming studied  the adversarial noise model where  noise on different
symbols may  be correlated and may  depend on the  whole message being
sent. In this  paper we study error correcting  codes for highly noisy
channels (as the one above) in this adversarial model.

Our  main  conceptual contribution  is  an  equivalence between  error
correcting codes for such  channels and extractors. Our main technical
contribution  is  a  new  explicit  error  correcting  code  based  on
Trevisan's  extractor   that  can  handle  such   (and  even  noisier)
channels.  Our  new  code   has  both  polynomial  time  encoding  and
polynomial  time  soft-decision  decoding  algorithms.  We  note  that
Reed-Solomon codes can not handle such channels, and our study exposes
some limitations on list decoding Reed-Solomon codes.

Our  results are  also the key tool in a recent work solving the
seemingly unrelated  question of  storing a set  of elements in  a way
that membership  in the set can  be determined by looking  at only one
bit  of the  representation.  We  also show  that our results improve
previous results on the hardcore bits problem.

Joint work with David Zuckerman and Shmuel Safra.

21.

Applications of Local List-Decoding Algorithms

In the past few years, very fast "local" list-decoding algorithms for
Reed-Muller codes have been found. These probabilistic decoding algorithms
manage to meaningfully solve the list-decoding problem while only reading
a tiny portion of the received word.

In this talk, we will focus on some recent applications of these
algorithms in complexity theory.  In particular:

- Strong results relating worst-case complexity and average-case
complexity, with applications to derandomization.

- Extracting nearly uniform bits from sources of biased and correlated
bits, for sources which are generated by an efficient sampling algorithm.

Joint works with Madhu Sudan and Luca Trevisan.

22.

Pascal Vontobel, ETH Zuerich
Algebraic Code constructions for iterative decoding

Channel codes can be pictorally represented with the help of so-called
Tanner/factor graphs. Decoding of these codes with the help of the
sum-product algorithm can then be represented as message-passing along
the edges and processing at the vertices. For codes whose graphs
fulfill certain properties this decoding algorithm gives near
maximum-likelihood performance. Among the desirable properties of
these graphs is that they look locally tree-like or equivalently that
they have no short cycles.

Starting from graphs with large girth (the girth is the length of the
smallest cycle), we discuss several different possibilities to
construct regular and irregular low-density parity-check (LDPC) and
turbo codes.

23.

Avi Wigderson, IAS
Cayley Expanders from Linear Codes

Theorem: The cyclic shifts of almost every two n-vectors over F_2
form a generating matrix of an assymptotivally good linear code

In this theorem, the cyclic group on n elements acts on the
coordinates of the vector space, and the generating matrix is the
orbit of only two vectors. More generally, we consider the action of
any group with n elements on the coordinates. We study when such
constant number of orbits can generate an assymptotically good code.

We give a sufficient condition on the distribution of
dimensions of the irreducible representations of G which ensures the
existence of such succinctly described codes. We then relate this
condition to the expansion properties of the group G. Finally we show
how to use such orbits in an iterative construction of expanding
Cayley graphs of near-constant degree.

Joint work with Roy Meshulam.

24.

Jonathan Yedidia, MERL
Projection Algebra Analysis of Error-Correcting Codes

We explain how  to use the projection algebra  technique to analyze an
arbitrary parity-check code as  decoded by the belief propagation (BP)
algorithm on  the binary erasure channel (BEC).  Using this technique,
we can exactly  compute the block error rates and  the bit error rates
of every bit at every iteration of the decoding process.

Our motivation is  that the results of such  computations can serve as
an objective function in a search for good codes. The pioneering paper
by Luby,  Mitzenmacher, Shokrollahi, and Spielman,  which analyzed and
optimized irregular low-density parity-check (LDPC) codes decoded by a
BP decoder and  used over the BEC, demonstrated  that one could design
capacity-approaching   codes  by  optimizing   the  codes   for  their
performance  as measured  using the  density evolution  technique. Our
technique builds on density  evolution, but ameliorates its major flaw
by exactly  accounting for the statistical dependencies  that exist in
finite blocklength codes.

Recently, Di, Proetti, Teletar, Richardson, and Urbanke have shown how
to perform  a finite length analysis  of regular LDPC  codes used over
the  BEC. They  were  able to  analyze  both BP  decoding and  maximum
likelihood decoding,  but their analyses was limited  to averages over
ensembles of regular  LDPC codes. Our analysis as  presented here also
only applies  to the BEC, and  we are further limited  to BP decoding,
but the advantage of our technique  is that we are able to analyze the
performance of a single, specific, parity-check code.

Although  the exact  projection algebra  technique  is computationally
intractable  for codes of  large block-length,  it can  be efficiently
approximated in a way that  give results that are still asymptotically
exact in the  limit of small erasure rates. We discuss  how to use the
information  obtained  by our  techniques  to  optimize finite  length
parity check codes.

Joint  work  with  Erik  Sudderth (MIT)  and  Jean-Philippe  Bouchaud
(Saclay).

25.

Junan Zhang, UCSD
Finite Length Analysis of LDPC Codes with Large Left Degrees

The asymptotic performance of LDPC codes under density evolution
was studied in a number of papers. However, the finite block
length behavior of LDPC codes is less understood. A recent paper
by C.Di, D.Proietti, T.J. Richardson, E.Telatar and R.Urbanke
considered this finite-length error probability when the codes are
used over erasure channels and decoded iteratively. The authors
derived recursions for maximum stopping sets to yield the
(average) block- and bit- error probability for a given regular
(ensemble) LDPC codes. Although these recursions apply to all
regular LDPC codes, their computational complexity rendering them
feasible only for small block lengths. To calculate the error
probability for large block lengths, the authors derived efficient
recursions for left degrees 2 and 3. In this paper we extend their
work and derive an efficient recursion for general left degree,
which can be used to determine the block- and bit- error probability
of two types of LDPC codes: regular codes with large left degree and irregular
codes with simple left degree sequences. We apply this recursion
to determine the block error probability of several codes for
different block lengths and relate the behavior of their error
floors, when the block length increases, to their lowest left
degrees.

26.

Codes in Theoretical Computer Science
David Zuckerman, UT Austin

We survey applications of error-correcting codes in theoretical computer
science.  The most natural applications are to fault tolerance; we focus
on more unexpected applications in pseudorandomness and other areas.
We explore which properties of codes are used, notably minimum distance,
list decodability, and local decodability.


Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center