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