**Information
and Coding Theory Seminar** **
**

**Abstracts
of talks**

*Fall 2005*

**2/2 Grigory Kabatiansky (IPPI, Moscow), Collusion
secure digital fingerprinting: the case of two pirates revisited **

Abstract: We consider the problem of digital fingerprinting codes in the simplest case of two "pirates". We calculate the rate achievable via the family of random linear codes and discuss upper bounds in order to estimate the capacity of the corresponding channel. A related problem of so-called tracing traitors codes will be also discussed.

**2/9
Adrian Papamarcou (UMD), Writing on Dirty Paper: A Geometrical Approach**

Abstract: It was shown by Costa (1981) that the capacity of the power- limited AWGN channel is not reduced by the presence of additive Gaussian interference known to the transmitter but not the receiver. The proof of that result was based on a previously known single-letter characterization of the capacity (due to Gel'fand and Pinsker) which involved an auxiliary variable; the iid realization of that variable was also instrumental in the random coding argument of the proof. In this talk, we briefly review the role played by n- dimensional hyperspheres in the representation and visualization of codes for the AWGN, and proceed to develop and interpret the Costa result using a geometrical approach that does not rely on auxiliary variables or distributions.

**2/16
Jon Feldman (Columbia U.), Linear programming decoding**

Abstract:
In this talk we introduce the method of LP decoding, and show how the error
rate of an LP decoder can be characterized as the mass of a certain "normal
cone" under a probability distribution defined by the channel. We then apply
LP decoding to low-density parity-check (LDPC) codes, and study the relationship
between "polytope vertices" and "graph covers," (Koetter and Vontobel) unified
under the notion of a "pseudocodeword." We then use a "dual witness" to prove
a lower bound on the number of errors that can be corrected by an LP decoder,
as long as the graph expands sufficiently.

(Joint work with David Karger, Tal Malkin, Rocco Servedio, Cliff Stein, and
Martin Wainwright)

**3/2
Olgica Milenkovic (U. Colorado, Boulder), Constrained and Error-Control Coding
for DNA Computers**

Abstract:
The last century was marked by the birth of two outstanding scientific and engineering
disciplines: silicon based computing and the theory and technology of genetic
data analysis. The research field very likely to dominate the area of scientific
computing in the foreseeable future is the merger of these two disciplines,
leading to unprecedented possibilities for applications in varied areas of biology
and engineering. The first steps toward this goal were made in 1994, when Leonard
Adleman solved a quite unremarkable computational problem with an outstanding
method. The computational problem considered by Adleman was a simple instant
of the directed travelling salesmen problem. The technique used for solving
the problem was a new technological paradigm, termed DNA computing. Adleman's
experiment represents a landmark demonstration of data processing and communication
on the level of biological molecules.

Following Adleman's initial work, many other DNA computing schemes
were developed, including solvers for the 3-SAT problem, DNA systems for analyzing
chess games, DNA-based logical components, as well as an intelligent, interactive
DNA "game machine", called MAYA. Other applications of DNA techniques include
DNA-based storage, DNA biosensing, molecular signal processing and intra-cell
disease diagnostics and treatment.

One of the major obstacles to efficient DNA computing, storage
and signal processing is the very low reliability of DNA hybridization operations.
DNA computing experiments require the creation of a controlled environment that
allows for a set of DNA oligonucleotide strands (codewords) to hybridize with
their complements in an appropriate fashion. If the DNA codewords are not carefully
chosen, unwanted, or non-selective, hybridization may occur. Even more detrimental
is the fact that an oligonucleotide sequence may fold back onto itself, forming
a secondary structure which prevents the sequence from participating in the
computational process.

In this talk, we describe some new DNA code design methods which
meet the hybridization-constraint requirements. Several classes of such codes
are cyclic, which is a particularly useful property in light of the fact that
the presence of a cyclic structure reduces the complexity of testing DNA codes
for secondary structure formation. Based on some simple properties of a dynamic-programming
algorithm, known as Nussinov's method, which is an effective predictor of secondary
structure given the sequence of bases in a DNA codeword, we identify some code
design criteria that reduce the possibility of secondary structure formation
in a codeword. These design criteria can be formulated in terms of the requirement
that the Watson-Crick distance between a DNA codeword and a number of its shifts
be larger than a given threshold or that the DNA codewords do not contain long
subsequences and their reverse complements. In this talk we address both the
issue of enumerating DNA sequences with such properties and the problem of practical
DNA code construction under such constraints.

Joint work with Navin Kashyap from Queen’s University, Kingston, Canada.

**
3/9 Damianos Karakos (Johns Hopkins), An Introduction to Decision Trees
**Abstract:
Classification (decision) trees are usually built in a supervised manner, where
a set of observation-label pairs {(X,Y)} is provided. For each input observation
X, a series of decisions is taken, as to which branch of the tree X will follow
at each internal node. Once X reaches a leaf, a leaf-specific "label" hat{Y}
is chosen as the output. The tree is designed to minimize (at least approximately)
the expected loss between Y and hat{Y}. In this talk, we will present the fundamentals
of decision trees, and we will describe various locally optimal practical procedures
for growing them. We will also see some problems that have been successfully
tackled using decision trees.

**
4/1 Tom Richardson (Flarion Technologies), Design and Modeling Issues for Mobile
Wireless Data: An introduction to Flash OFDM** (CSHCN Colloquium)

Abstract: Recent experience in a deployment of Flash OFDM in the Raleigh area
by Nextel has shown that Flash OFDM offers the best technological solution for
mobile wireless data. The transition from wireless voice to wireless data necessitates
a reconsideration of both system networking design and the wireless channel.
This talk will introduce some of the key ideas that underpin and differentiate
the Flash OFDM system.

**4/6 Alexander Barg (UMD), Quantum
Codes: An Introduction**

Abstract: A tutorial on the basics of quantum algorithms and error correction.

**4/13 Alexander Barg (UMD), Quantum
Codes: An Introduction** (continued)

**4/20 Punarbasu Purkayastha (UMD), Weight
distributions of LDPC codes**

Abstract: This talk will mainly focus on how the asymptotic distance spectrum of regular LDPC codes can be estimated using saddle point approximation, and how these estimates can be used to provide bounds on the error rate under ML Decoding.

References: [1] David Burshtein, Gadi Miller,
"Asymptotic Enumeration Methods for Analyzing LDPC Codes", IEEE Transactions
on Information Theory, June 2004.

[2] Ohad Barak, David Burshtein, "Lower Bounds on the Spectrum and Error
Rate of LDPC Code Ensembles"

**4/27 Prakash Narayan (UMD), The
Minimum Description Length (MDL) Principle **

Abstract: Rissanen's Minimum Description
Length (MDL) principle, which lies at the interface of information theory and
statistics, states that the statistical information contained in data is best
extracted in terms of a possibly short and invertible description (code) of
the data. The statistical model (e.g., probability distribution) inferred from
the data (as best fitting the data) is the one that leads to the shortest description,
taking into account that the inferred model (e.g., probability distribution)
itself must also be described. The entrails of the MDL principle will be joyously
examined.

References:

**[1]** I. Csiszar and P.C. Shields, Notes on Information Theory and Statistics,
available in Foundations and Trends in Communications and Information Theory,
S. Verdu, Ed., 2004. (The relevant material appears in Section 7 - pdf)

**[2]** A. Barron, J. Rissanen
and B. Yu, "The Minimum Description Length Principle in Coding and Modeling",IEEE
Trans IT, vol. 44, no. 6, pp. 2743-2760, Oct. 1998.

**5/4 Martin Wainwright (UC Berkeley),
Tree-reweighted message-passing algorithms in graphical models: Some theory
and applications (CSPL seminar) **

Abstract: Graphical models (e.g., factor
graphs, Markov random fields) provide a flexible framework for capturing statistical
dependencies among large collections of random variables, and are widely used
in various fields, including statistical signal processing, coding and communication
theory, and machine learning. Central to the wide-spread use of graphical models
are distributed ``message-passing'' algorithms (e.g., sum-product, max-product),
in which nodes perform local computations and communicate with their neighbors.
The purpose of these algorithms is to solve various statistical inference problems
(e.g., image denoising, error-control decoding) that arise in applying a graphical
model. These methods are well-known to be exact for trees, but they are also
widely applied to graphs with cycles, where they yield approximate answers.

To motivate our work, we describe some potential pitfalls associated
with applying the standard forms of message-passing to graphs with cycles (sum-product:
multiple fixed points and instability; max-product: misleading outputs). We
then describe a novel family of tree-reweighted algorithms, and present some
theoretical guarantees on their behavior for graphs with cycles. The tree-reweighted
sum-product algorithm has a unique fixed point for any problem, and it can be
understood as computing an optimal upper bound on the log partition function.
On the other hand, the tree-reweighted max-product algorithm has the desirable
property of never deceiving the user; this behavior can be understood in terms
of a particular linear programming relaxation of the mode-finding problem. We
conclude with an overview of some applications of these modified algorithms.
Talk based on joint work with: Jon Feldman, Tommi Jaakkola, Alan Willsky.

**5/12 Pierre Moulin (UIUC)** (CSPL seminar,
note the unusual day), **Communication games with side information**

In this talk we consider some communication problems with channel uncertainty
and attempt to derive the worst noise distribution within a prescribed class of
distributions. For point-to-point communications this is a classical problem,
for which elegant solutions have been derived over the last forty years.

Motivated by problems such as data hiding and watermarking,
we have recently been interested in extending this work to communication problems
with side information. Optimal strategies for the communicator and the adversary
(jammer) may then be derived by selecting an appropriate cost function and solving
minmax optimization problems with respect to the variables of the game. The inner
maximization problem (over the noise distribution) is infinite-dimensional but
concave. For detection problems the worst noise distributions are strongly non-Gaussian;
in some cases exotic solutions are obtained. We also quantify the benefits of
randomized strategies for the communicator. This methodology is illustrated by
applications to scalar and hexagonal quantization codes for data hiding.