Information and Coding Theory Seminar  

Abstracts of talks

Spring 2010

02/18, 02/25 Sirin Nitinawarat (UMD) , On the Deterministic Code Capacity Region of an Arbitrarily Varying Multiple-Access Channel Under List Decoding

ABSTRACT: we study the capacity region $C_L$ of an arbitrarily varying multiple-access channel (AVMAC) for deterministic codes with decoding into a list of size $L$ and for the average error probability criterion. First, we introduce the notion of symmetrizability, denoted by an integer $U \geq 0$, of the AVMAC by generalizing from a similar notion earlier defined for a point-to-point arbitrarily varying channel. It is then shown that for every $L \leq U$, $C_L$ has an empty interior, and for a fixed function $f:\{0, 1, \ldots \} \rightarrow \{0, 1, \ldots \}$ and for every $L \geq f(U)$, $C_L$ equals the capacity region of the AVMAC for random codes with a known single-letter characterization. In particular, $f(u) \leq (u+1)^2(u+2) - 1$, for every $u \geq 0,$ and, hence, the latter holds for every $L \geq (U+1)^2(U+2) - 1$.

I plan to start with some overview on the theory of the (single-input-single-output) arbitrarily varying channel and its extension to the multiple access channel before addressing the main results. If time permitted, relevant open problems will also be discussed.

03/11 Arya Mazumdar (UMD) , Coding for High-Density Magnetic Recording

ABSTRACT: We study a model of errors in binary data that arises in terabit-density magnetic recording. Under this model, several bits of the data are replaced by the values of their neighbors on the medium. We consider a simple one-dimensional version of this model, and derive several properties of codes that correct this type of error.

Joint work with Navin Kashyap and Alexander Barg.

03/25 Alexander Barg (UMD) , Codes with a strong parent-identifying property

ABSTRACT:
In the area of digital fingerprinting, one setting calls for unconditional identifying of one of the members of the "pirate coalition," while the other permits a small failure probability of the system designer. These two settings are distinguished by different types of pirate attacks. An interesting question arises if one considers an intermediate setting. It is answered by the concept of strongly IPP codes, introduced in the present work. We will prove that such codes exist, and find some exact answers for the case of size-2 pirate coalitions.

Joint work with G. Kabatiansky

04/01 Ravi Tandon (UMD) ,

ABSTRACT: We consider a secure lossless source coding problem with a rate- limited helper. In particular, Alice observes an i.i.d. source $X^{n}$ and wishes to transmit this source losslessly to Bob. A helper, say Helen, observes a correlated source $Y^{n}$ and transmits at a rate $R_{y}$ to Bob. A passive eavesdropper can observe the coded output of Alice. The equivocation $\Delta$ is measured by the conditional entropy $H(X^{n}|J_{x})/n$, where $J_{x}$ is the output of Alice. We first completely characterize the rate-equivocation region for this secure source coding model, where we show that Slepian-Wolf binning is optimal.

We next study two generalizations of this model and provide single-letter characterizations for the respective rate-equivocation regions. In particular, we first consider the case of a two- sided helper where Alice also has access to the coded output of Helen. We show that for this case, Slepian-Wolf binning is suboptimal and one can further decrease the information leakage to the eavesdropper by utilizing the side information at Alice. We finally generalize this result to the case when there are both secure and insecure rate-limited links from Helen and additional uncoded side informations $W^{n}$ and $Z^{n}$ are available at Bob and Eve, respectively. For this model, we provide a complete characterization of the rate-equivocation region when $Y^{n}\rightarrow X^{n} \rightarrow (W^{n},Z^{n})$ forms a Markov chain.

(Joint work with Sennur Ulukus and Kannan Ramchandran.)

04/08 Sirin Nitinawarat (UMD) , Maximal Error Capacity Regions Are Smaller than Average Error Capacity Regions for Multi-user Channels

ABSTRACT: The coding theorem for a discrete memoryless channel was originally proved by Shannon for the average error concept. However, a simple expurgation argument shows that the capacities for both the average and maximal error concepts are the same.

We present the results in the paper by G. Dueck (see below). In the paper, examples are given, for two-way channels and for multiple access channels, to show that the capacity regions depend on the error concept used. The author also proved that the same assertion holds with perfect feedback available to all the transmitters.

G. Dueck, ``Maximal Error Capacity Regions Are Smaller than Average Error Capacity Regions for Multi-user Channels,'' Problems of Control and Information Theory, Vol 7. (1), pp.11-19 (1978).

04/22 Avinash Varna (UMD) , TTT

ABSTRACT: Applications such as detection of copyright infringement and metadata services have spurred the development of efficient techniques for automated multimedia identification. Compact representations of robust and distinct multimedia features, called "fingerprints" or "robust hashes", are used for efficient multimedia identification. In this talk, we briefly review the concept of content fingerprints and present our work on modeling and analysis of multimedia content identification using binary fingerprints.

We first examine content identification using i.i.d. binary fingerprints under a detection-theoretic framework and derive a relation between the length of the fingerprint and the identification accuracy. We then model the interaction between the detector and an attacker seeking to evade detection as a two player game and obtain optimal strategies for both parties. To capture correlations among fingerprint bits, we introduce a Markov Random Field model for the fingerprint bits and noise. Under this model, we use a statistical physics inspired technique to first estimate the density of states and then utilize this estimate of the density of states to compute the probabilities of detection and false alarm.
(Joint work with Dr. Min Wu and Dr. Ashwin Swaminathan.)

05/13 Dr. S. Sandeep Pradhan (University of Michigan) , Toward a new approach to distributed information processing: Harnessing group structure

ABSTRACT: The prevalent trend in information theory has been to obtain performance limits of communication using Shannon's random coding arguments and its multi-terminal extensions, and in coding theory, the goal has been to achieve these limits using algebraic-structured codes with fast encoding and decoding algorithms.

It turns out that algebraic structure can also be used to weed out bad codes from an ensemble. In this work, we build on this observation, and look at the distributed source coding problem. We present a new approach to this problem and an achievable rate-distortion region (an inner bound to the performance limit) based on “good” structured random nested codes built over abelian groups. We demonstrate rate gains for this problem over traditional coding schemes that use random unstructured codes. For certain sources and distortion functions, the new rate region is strictly bigger than the Berger-Tung rate region, which has been the best known achievable rate region for this problem till now. Further, there is no known unstructured random coding scheme that achieves these rate gains. Achievable performance limits for single-user source coding using abelian group codes are also obtained as parts of the proof of the main coding theorem. We also show that nested linear codes achieve the Shannon rate-distortion bound in the single-user setting.