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.