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.)
 

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)