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

**Abstracts
of talks**

*Spring 2008*

** 2/07 Jřrn Justesen (Technical University of Denmark),
Cores in Random Graphs and Some Applications to Error-correcting Codes **

ABSTRACT:

A k-core of a given graph is a subgraph where all vertices have degree at least k .
It was proved by Pittel, Spencer, and Wormald that in a random graph, a core with k>=3
occurs with vanishing probability if the number of edges is below a certain threshold,
whereas when the number of edges exceeds the threshold, a very large k-core exists with
high probability. We extend the result to random bipartite graphs,
which are of interest both as descriptions of random graph codes and of error patterns
in graph codes. For products of Reed-Solomon codes the random graph bound gives
a useful estimate of the number of errors that can be corrected by repeated application
of the standard decoding algorithm for the component codes. We also discuss the implications
for other graph codes with RS components, for binary product codes, and for
estimates of the minimum distance of binary graph codes.

** 2/14 Arya Mazumdar (UMD), Thresholds for Codes on Bipartite Graph
**

ABSTRACT:

We derive the thresholds for iterative decoding of bipartite-graph codes on the BSC and BEC. The calculations for BEC will lead to the fact that there exist asymptotically good bipartite-graph codes.
(Joint work with Alexander Barg)

**2/28. Sirin Nitinawarat (UMD)**, Secret Key
Generation for a Pairwise Independent Network Model

ABSTRACT:

We investigate secret key generation for a ``pairwise independent network''
model in which every pair of

terminals observes correlated sources which are independent of sources observed
by all other pairs of terminals. The terminals are then allowed to communicate
interactively in multiple rounds over a public noiseless channel of unlimited
capacity, with all such communication being observed by all the terminals. The
objective is to generate a secret key shared by a given subset of terminals at

the largest rate possible. All the terminals cooperate in generating the secret
key, with secrecy being required from an eavesdropper which has access to the
public interterminal communication.

We provide a (single-letter) formula for the secrecy capacity. We then show a
natural connection between the problem of secret key generation for this model
and the combinatorial problem of maximal packing of Steiner trees in an
associated multigraph. In particular, we show that the maximum number of Steiner
trees packings in the multigraph is always a lower bound for the secrecy
capacity. The bound it tight for the case when all the terminals seek to share a
secret key. In the latter situation, the mentioned connection yields an

explicit capacity-achieving algorithm (which can be executed in polynomial time)
that extracts a group-wide secret key of the optimum rate from the collection of
optimum and mutually independent secret keys for pairs of terminals.

Joint work with {Professor Barg, Professor Narayan}(UMD), {Chunxuan Ye, Alex
Reznik}(InterDigital).

** 3/6. Anna Pantelidou (UMD) **, A Cross-layer Approach for Stable Throughput
Maximization under Channel State Uncertainty

ABSTRACT:

Obtaining the stable throughput region of a wireless network, and a policy that achieves this throughput, has attracted the interest of the research community in the past years. A major simplifying assumption in this line of research has been to assume that the network control policy has full access to the current channel conditions at every time a decision is made. However, in practice one may only estimate the actual conditions of the wireless channel process, and hence the network control policy can at most have access
to an estimate of the channel which can in fact be highly inaccurate.

In this work we determine a stationary joint link activation and routing policy based on a weighted version of the ``back-pressure'' algorithm that maximizes the stable throughput region of time-varying wireless networks with multiple commodities by having access to only a possibly inaccurate estimate of the true channel state. We further
show optimality of this policy within a broad class of stationary, non-stationary, and even anticipative policies under certain mild conditions. The only restriction is that policies in this class have no knowledge on the current true channel state, except what is available through its estimate.

Joint work with Professor Anthony Ephremides and Professor André Tits.

** 3/13. Arash Komaee (UMD) **, State Estimation with Point Process Observation

ABSTRACT:

Point processes are frequently used to model highly localized random events in time. A well known example of the point process is the "Poisson process", which has a constant and deterministic rate. Doubly stochastic Poisson process is a generalization of Poisson process in which the rate of the process is a random variable or a stochastic process, such that, conditioned on the rate, the process is an ordinary inhomogeneous Poisson process. When the rate of this process is modulated by the state of a dynamical system, the observation of the process can be used to estimate the state vector. This estimation problem forms the main theme of our talk.

In this talk, we will introduce some important cases of point process such as doubly stochastic Poisson process, self- exiting point process, and space-time point process. Then, we will consider the estimation problem with observation of a point process whose rate is modulated by a diffusion process. As the solution to this estimation problem, we will derive the equations describing the time evolution of the posterior density for both normalized and unnormalized cases. Also, we will briefly talk about the filtering problem associated with these equations.

** 3/27 N. Prasanth Anthapadmanabhan (UMD)**, Intersections of Random Graphs

ABSTRACT:

There are several well-known models for random graphs in the literature. For
instance, the Erdos-Renyi (ER) random graph, the geometric random graph etc. It
is of interest to analyze how graph properties such as existence of isolated
nodes and graph connectivity evolve by varying the parameters of these random
graphs (with growing number of nodes). These results are typically

given in terms of "zero-one laws". As communication theorists, we are interested
in utilizing these random graph models to analyze the performance of
communication networks. However, in many cases of interest, these models are
individually insufficient, and a combination of the models is required to model
the communication network. As an example, consider an ad hoc wireless network
with a simple fading model where the link between any two nodes may fail with
some specified probability. In this example, any two nodes are connected if (i)
they are within communication range and (ii) the link between them is active.
This leads to a joint random graph model which is the "intersection" of the
corresponding ER and geometric random graphs, i.e., has the edges that are
common to both graphs.

In this talk, we will focus on the issue of node isolation in ER-geometric joint
random graphs. We will present what we believe to be the zero-one law in this
case. We will demonstrate the method of first and second moments (a basic
technique in proving such results) and present a partial proof from our
work-in-progress.

Basic probability theory should be sufficient to understand the talk.

(Joint work with Armand Makowski)

**
4/3 Alexander Barg (UMD) **, Weight Distribution and Decoding of Codes on
Hypergraphs

ABSTRACT:

Codes on graphs have been shown to possess very good properties in terms of
their parameters and error correcting capability. In this talk we consider their
generalization to the case when the underlying graph is replaced by a regular
hypergraph.

We explain the following two groups of results:

(1) calculation of ensemble-average weight distributions and the minimum
distance for several ensembles of hypergraph codes;

(2) a decoding algorithm of such codes that corrects a constant fraction of
errors relative to code's length (the algorithms known previously were capable
of correcting only a vanishing proportion of errors).

Joint works with Arya Mazumdar and Gilles Zémor.

**
4/10 No Seminar,** ISR's 2008 Systems Symposium

**
4/17 P. S. Krishnaprasad (UMD)**,
Information Geometry and Dynamics on the Probability Simplex

ABSTRACT:

The Kullback-Leibler divergence is a measure of nearness of probability
measures. An associated Riemannian metric imposes a natural geometry on
the probability simplex. In this talk we will discuss Hamiltonian and
gradient dynamics connected with this geometry. The gradient dynamics is
of relevance to the solution of problems in noncooperative game theory.

(This talk will be self-contained.)

**4/24 R. Balan (UMD),** MDL based Estimation of the Number of Sources in
a Sparse Signals Mixture Model

ABSTRACT: In this talk we present an Information Theoretic Estimator for the
number of sources mutually disjoint in a linear mixing model. The approach
follows the Minimum Description Length prescription and is roughly equal to the
sum of negative normalized maximum log-likelihood and the logarithm of number of
sources. Preliminary numerical evidence supports this approach and compares
favorably to both the Akaike (AIC) and Bayesian (BIC) Information Criteria.

**
5/1 No Seminar,**

**
5/8 Osman Yagan (UMD) **,
A Zero-one Law for Connectivity in the Random Graphs Induced by a Random Key Predistribution Scheme

ABSTRACT:

Wireless sensor networks (WSN) are distributed collections of sensors with limited computation and communication capabilities. It is envisioned that such networks will be deployed in hostile environments where communications are monitored, and nodes are subject to capture and surreptitious use by an adversary. Thus, cryptographic protection is needed to ensure secure connectivity and the random key predistribution scheme proposed by Eschenauer and Gligor (EG scheme) is a widely accepted solution.

In this talk, we will model the WSN as a "random graph induced by the EG scheme", which we refer as the "random key graph", and show how proper parameter selection may lead to secure connectivity with very high probability. In other words, we will show the existence of a zero-one law for connectivity in the random key graphs and identify the corresponding critical thresholds.

(Joint work with Professor Armand Makowski)