Abstracts for Venkat Anantharam

The EECS Research Summary for 2003


The Zero-Rate Error Exponent of the Exponential-Server Timing Channel

Aaron Wagner
(Professor Venkat Anantharam)
(DARPA) F30602-00-2-0538, (DARPA) N66001-00-C-8062, NSF Graduate Research Fellowship, (NSF) SBR-9873086, and (ONR) N00014-1-0637

The exponential-server timing channel (ESTC) is one in which the sender chooses times at which identical jobs are submitted to a single-server queue with an exponential service time distribution, while the receiver observes their departure times. Our interest in this channel is due to its canonical nature and the central role it plays in the study of covert timing channels, in which the sender sends messages containing irrelevant or misleading information, and actually communicates with the receiver using the timing of the messages, unknown to a casual observer.

Previous work has established the Shannon capacity of the channel [1], and the random-coding and sphere-packing bounds on its reliability function [2]. The bounds prove that the reliability function is at least as large as the reliability function of the well-known Poisson channel [3,4], and that the two reliability functions coincide at rates close to their common capacity. We have proved that at sufficiently low rates, the reliability function of the ESTC lies strictly above the Poisson channel's, answering in the negative the open question of whether the two reliability functions coincide at all rates [2]. Our results reveal a distance metric between codewords for the ESTC that parallels Hamming distance for the binary symmetric channel and Euclidean distance for the Gaussian channel. We are currently attempting to determine the zero-rate error exponent of the ESTC exactly.

[1]
V. Anantharam and S. Verdú, "Bits through Queues," IEEE Trans. Information Theory, Vol. 42, No. 1, January 1996.
[2]
E. Arikan, "On the Reliability Exponent of the Exponential Timing Channel," IEEE Trans. Information Theory, Vol. 48, No. 6, June 2002.
[3]
A. D. Wyner, "Capacity and Error Exponent for the Direct Detection Photon Channel Part I," IEEE Trans. Information Theory, Vol. 34, No. 6, November 1988.
[4]
A. D. Wyner, "Capacity and Error Exponent for the Direct Detection Photon Channel Part II," IEEE Trans. Information Theory, Vol. 34, No. 6, November 1988.

Send mail to the author : (awagner@eecs.berkeley.edu)

Eliminating the Identification Problem in the Presence of the Varying Sampling Rate

Lara Dolecek
(Professor Venkat Anantharam)
California MICRO, Marvell Inc., (NSF) SBR-9873086, (ONR) MURI N00014-1-0637, ST Microelectronics, and Texas Instruments

When the sampling rate at the output of a channel carrying coded information varies, the performance of the decoder can be significantly degraded. For example, for simple linear codes, even as the SNR goes to infinity, one cannot successfully decode the input sequence because two or more distinct input sequences can potentially give rise to the same output sequence.

To address this issue, we adopt the following model. An input sequence is first encoded by a linear block code. The output is then passed through a set of linear transformations, which model the uncertainty of the sampling rate. The transformations include, for the simplest case, a family of identity matrices with one column repeated, or more generally, a symbolic dynamics (d,k) pattern.

Our goal is to identify which conditions impose on the linear block code, and in which properties of the family of the transformations no two input sequences result in the non-zero overlapping set of outputs. We also want to determine the most efficient precoding technique which will eliminate the identification problem while keeping the rate of the code as high as possible.


Send mail to the author : (dolecek@eecs.berkeley.edu)

Estimation and Marginalization Using Free Energy Based Methods

Payam Pakzad
(Professor Venkat Anantharam)
California MICRO, (DARPA) F30602-00-2-0538, (NSF) SBR-9873086, and (ONR/MURI) N00014-1-0637

It was shown recently in [1] that the well known belief propagation algorithms for posterior probability evaluation can be viewed as algorithms that aim to minimize certain approximations to the variational free energy in a statistical physics context. Specifically, the fixed points of belief propagation algorithms are shown to coincide with the stationary points of Bethe's approximate free energy subject to certain consistency constraints. Bethe's approximation is known to be a special case of a more general class of approximations called Kikuchi free energy approximations. A more general class of belief propagation algorithms was thus introduced which corresponds to algorithms that aim to minimize a general Kikuchi approximate free energy.

In this reseach we develop and extend this general method of approximation. Specifically, given an arbitrary collection of regions, i.e., proper subsets of a set of state variables, and a collection of functions of the configuration of state variables over these regions, we define a general constrained minimization problem corresponding to the general Kikuchi approximation whose stationary points approximate marginals over these regions of the product function, and we specify a general class of local message-passing algorithms along the edges of a graphical representation of the collection of Kikuchi regions, which attempt to solve that problem (see [2]). We have also developed a suitable minimal graphical representation of the collection of regions (see [3]). Iterative message-passing algorithms on the graph we construct involve fewest message updates at each iteration. We have proven that exactness of Kikuchi approximation of marginals depends directly on this graph being cycle-free, and we have conditions for convexity of the Kikuchi function based on the properties of the minimal graph of regions.

[1]
J. S. Yedidia, W. T. Freeman, and Y. Weiss, Bethe Free Energy, Kikuchi Approximations, and Belief Propagation Algorithms, Mitsubishi Electric Research Laboratories Technical Report No. MERL TR2001-16, May 2001.
[2]
P. Pakzad and V. Anantharam, "Belief Propagation and Statistical Physics," Proc. CISS Conf., Princeton University, March 2002.
[3]
P. Pakzad and V. Anantharam, "Minimal Graphical Representation of Kikuchi Regions," Proc. Allerton Conf., Monticello, IL, October 2002.

Send mail to the author : (payamp@eecs.berkeley.edu)