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

**Abstracts
of talks**

*Fall 2008*

** 9/11 Anuj Rawat (UMD), Coloring Rooted Subtrees of a Bidirected Tree
**

ABSTRACT:

A bidirected tree is a directed graph obtained
from a tree by replacing all the edges of the tree
by pairs of directed anti-parallel edges. The
degree (depth) of a bidirected tree is defined to
be the degree (depth) of the tree from which it is
constructed.

We study the problem of assigning colors to a
given set of rooted subtrees of a given bidirected
tree such that if any two rooted subtrees share a
directed edge, then they are assigned different
colors. The objective is to minimize the total
number of colors used in the coloring. The problem
is NP hard even in the restricted cases when (i)
the degree of the bidirected tree is restricted to
being 2, and (ii) the depth of the bidirected tree
is restricted to being 2. This problem is
motivated by the problem of assigning wavelengths
to multicast traffic requests in all-optical tree
networks.

We present a greedy coloring scheme for the case
when the degree of the bidirected tree is
restricted to 3 and prove that it is a
5/2-approximation algorithm. We then present
another, simpler coloring scheme and prove that it
is an approximation algorithm for the problem with
approximation ratio 10/3, 3 and 2 for the cases
when the degree of the bidirected tree is
restricted to 4, 3 and 2, respectively.

**9/18. Himanshu Tyagi (UMD)**,
Proof of Converse of Burnashev's Reliability Function for DMC with Feedback

ABSTRACT:

The reliability function of a channel, for the rates below the capacity,
is defined as the maximum possible exponential decay rate of the
probability of error. In 1976, Burnashev determined the exact reliability
function of variable-length block codes over a discrete memoryless channel
(DMC) with feedback. Subsequently, Yammamoto and Itoh proposed a simple
achievability scheme to attain this reliability function. Their scheme
alternates between communication and confirmation phases until the receiver detects the codeword used by the sender to acknowledge that the message is correct.
We present the simple proof of converse of the reliability function given by
Berlin, Nakiboglu, Rimoldi and Teletar which shows that the confirmation phase of
Yammamoto-Itoh scheme is intrinsic to any coding scheme for this channel.

**10/2. Arya Mazumdar (UMD)**,
Compressed Sensing: A Coding Theoretic Perspective

ABSTRACT:

We will discuss the straightforward similarities between sparse signal recovery and decoding noisy data. We will see examples of how some well known results in coding theory generalize to solve the "compressed sensing problem."

Keywords: Decoding Reed Solomon Codes, Expander Graph, Sparse Representation.

**10/16. Sirin Nitinawarat (UMD)**,
Information-theoretic Limits on Sparsity Pattern Recovery in High-Dimensional and Noisy Setting

ABSTRACT:

The problem of recovering the sparsity pattern of a fixed but unknown vector in an $n$-dimensional complex vector space based on a set of $m$ noisy observations is considered.

In this talk, we focus on the information-theoretic limits of the sparsity pattern recovery. In particular, we present the result by Akçkaya and Tarokh for a noisy linear observation model based on measurement vectors drawn from the standard Gaussian ensemble. The result states that in the regime of linear sparsity (linear in $n$) and under a certain condition on the unknown vector, linear number of measurements is necessary and sufficient for sparsity pattern recovery.

Connections with previous works on compressive sensing will also be discussed.

**10/23.Professor Damianos Karakos (Johns Hopkins University)**,
Computation of Csiszár's Mutual Information of Order
Alpha

ABSTRACT:

Csiszár introduced the mutual information of order alpha as a parameterized version of Shannon’s mutual information. It involves a minimization over
the probability space, and it cannot be computed in closed form. An alternating minimization algorithm for its computation is presented in this paper, along with a proof of its convergence. Furthermore, it is proved that the algorithm is an instance of the Csiszár-Tusnády iterative minimization procedure.

The talk is based on a paper (co-authored with Sanjeev Khudanpur and Carey E. Priebe) that was presented at ISIT-08. The paper can be downloaded from
http://www.clsp.jhu.edu/~damianos/isit08_csiszar.pdf.

**10/30.Ravi Tandon (UMD)**,
Outer Bounds for the Multiple Access Channel with Feedback

ABSTRACT:

In this talk, we will present a new outer bound on the capacity region of the discrete
memoryless multiple access channel (MAC) with noiseless feedback. This outer bound will be shown to be
optimal for the cases where feedback capacity region is known. We will then consider a binary
additive noisy multiple access channel whose feedback capacity region is not known.
This channel can be viewed as a discrete counterpart of the Gaussian MAC. Ozarow established that the feedback capacity region of the two-user Gaussian MAC is given by the well known cut-set outer bound. We will
show that for a discrete counterpart, this is not the case.

Direct evaluation of our outer bound is intractable due to an involved auxiliary random variable,
whose large cardinality prohibits an exhaustive search. We will overcome this difficulty by using a
composite function and its properties to explicitly evaluate our outer bound.
This new outer bound is strictly less than the cut-set bound at all points on the feedback capacity region where
feedback increases capacity.

**11/05. Ghid Maatouk (EPFL)**, Recursions for the LT Decoder

ABSTRACT:

LT codes are the first class of universal Fountain codes. They are well-suited for fault-tolerant transmission of information over the Internet, modeled as a binary erasure channel. We briefly describe these codes and their decoding algorithms, introduce the concept of a state in which a decoder can be at any given instance during decoding, and describe a recursion for the state-generating function of the LT decoder derived by Karp, Luby
and Shokrollahi. Starting from this recursion, we will extend the analysis of Karp, Luby, and Shokrollahi to find explicit formulas for the variance of the main state parameters of the decoder. These formulas describe an explicit "corridor" within which the decoding state parameters can move, and lead to explicit good upper bounds on the decoding error. They can also be used to compute good finite length designs for LT-codes.
This is joint work with Amin Shokrollahi.

**12/04. Professor John S. Baras (UMD)**,
Dynamic Network Security Deployment under Partial
Information

ABSTRACT:

A network user’s decision to start and continue using security products is based on economic considerations. The cost of a security compromise (e.g., worm infection) is compared against the cost of deploying and maintaining a sufficient level of security. These costs are not necessarily the real ones, but rather the perceived costs, which depend on the amount of information available to a user at each time. Moreover, the costs (whether real or perceived) depend on the decisions of other users, too: the probability of a user getting infected depends on the security deployed by all the other users.

In this talk, we combine an epidemic model for malware propagation in a network with a game theoretic model of the users’ decisions to deploy security or not. Users can dynamically change their decision in order to maximize their currently perceived utility. We develop a mathematical model that evolves on the simplex in R3. We study the equilibrium points, and their dependence on the speed of the learning process through which the users learn the state of the network. We find that the faster the learning process, the higher the total network cost.

**12/11. A. Samorodnitsky
(Hebrew University)
**, What Makes the Linear Programming Bounds for Codes so Good?

ABSTRACT:

We will give a brief overview of Delsarte's
linear programming approach leading to the best known
upper bounds of on error-correcting codes due to
McEliece, Rodemich, Rumsey, and Welch (MRRW).

We will then discuss the "philosophical" question of
what makes this approach so powerful, and attempt
to give some (very partial answers) to this question.
In particular, we will describe an alternative
derivation of one of MRRW's bounds, interpreting it
as a covering rather than a packing bound.
Joint work with Michael Navon.