Information and Coding Theory Seminar
Abstracts of talks
Spring 2009
2/12 Alexander Barg (UMD), Polarization Codes
ABSTRACT: 2/19 Arya Mazumdar (UMD), Linear Balancing Sets
ABSTRACT: 3/5 Prasanth Anthapadmanabhan
(UMD), Two-level Fingerprinting Codes
ABSTRACT: 3/12 Gabriel Lipsa (UMD), Optimal Distributed State Estimation with Communication Cost: A Majorization Theory Approach
ABSTRACT: 3/25, S. Sandeep Pradhan (University of Michigan), Toward a New Approach to Distributed Source Coding:
Harnessing Group Structure
ABSTRACT: In this work, we consider a distributed source coding problem with a joint distortion criterion depending on the sources and the reconstruction. This includes as a special case the problem of computing a function of the sources to within some distortion and also
the classic Slepian-Wolf problem, Berger-Tung problem, Wyner-Ziv problem, Gelfand-Pinsker problem, Yeung-Berger problem and the Ahlswede-Korner-Wyner problem. While the prevalent trend in information theory has been to prove achievability results using Shannon's random coding arguments, using structured random codes offer
rate gains over unstructured random codes for many problems. Motivated by this, we present a new achievable rate-distortion region (an inner bound to the performance limit) for this problem for discrete memoryless sources based on ``good'' structured random nested codes built over abelian groups. We demonstrate rate gains for this problem
over traditional coding schemes using 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. As a corollary, we also prove that nested linear codes achieve the Shannon rate-distortion bound in the single-user setting. 4/2, Punarbasu Purkayastha (UMD), List Decoding Size and Weight distribution of Reed Muller Codes
ABSTRACT: A complete characterisation of
the list size as a function of the decoding
radius, and of the weight distribution as a function of the distance for
Reed Muller codes had been largely unknown till now. In "List Size vs
Decoding Radius for Reed Muller Codes", T. Kaufman and S. Lovett determine
the asymptotic behaviour of both these two quantities for all ranges of the
decoding radius and the distance, respectively. We will present the proof
of these two results.
4/9, Sirin Nitinawarat (UMD), Secrecy, Perfect Omniscience and Steiner Tree Packing
ABSTRACT: 4/23, Himanshu Tyagi (UMD), Strong Converse and Sphere Packing Bound for Channel with States
ABSTRACT: We consider a channel with states using Gelfand-Pinsker model of communication where the encoder knows the entire state sequence non-causally before sending the codeword. We derive bound on rate of a code for this channel which behaves "nicely" over large, message dependent subsets of state sequences. We then prove the strong converse by extracting these subsets of nice behavior from any "good" code. This approach is akin to the proof of strong converse of Shannon's channel coding theorem for a DMC, where a bound on rates of good constant composition codes is used to get a bound on rate of any good code. Finally, we use the aforementioned result to derive exponentially decaying lower bounds (exponential in code length) on the error probability of the optimal code for this channel. Such bounds are usually called sphere-packing bounds.
5/14, Grigory Kabatiansky, IITP RAS (Moscow,Russia), Reed-Muller Codes and Their List Decoding
ABSTRACT: We overview the known results on decoding of Reed-Muller codes
starting from the "Greene machine" (FFT) and the
seminal Goldreich-Levin algorithm for RM-1 codes.
We also present recent list decoding algorithms for RM codes
that correct errors up to the codes' minimum distance
(in the sense of list decoding).
E. Arikan has suggested an interesting idea for building code
families that achieve capacity of binary-input symmetric channels.
The purpose of this talk is to explain Arikan's code construction.
A subset B of n dimensional vector space over {0,1}
is called balancing set if a sphere of radius n/2 (in Hamming
metric) around any vector has a non-empty intersection with
B. A balancing set that is a linear subspace of dimension
O(log n) can be used to design `good' error correcting code with polynomial time encoding-decoding where all codewords
have hamming weight n/2. We show that most linear subspaces
of dimension slightly greater than 1.5log n are balancing
sets. We mention some related results as well. Work done at
HP Labs, Palo Alto, CA.
http://arxiv.org/abs/0901.3170
Fingerprinting and traceability codes are used for copyright
protection of licensed content. To prevent unauthorized
redistribution, each legal copy is supplied with an imperceptible
user-identifying signature (fingerprint) which is a codeword of a
fingerprinting (or traceability) code.
We introduce the notion of two-level fingerprinting and traceability
codes. In this setting, the users are organized in a hierarchical
manner by classifying them into various groups; for instance, by
dividing the distribution area of the content into several geographic
regions, and collecting users from the same region into one group. The
two-level codes we propose have the following property: If a coalition
of at most t users attempts to modify the fingerprints and create an
illegal copy, the decoder can identify at least one of the guilty
users. For coalitions of size greater than t, but smaller than some
value s, the decoder is capable of identifying a group that contains a member of the coalition.
In this talk, we provide constructions for two-level fingerprinting
codes and also obtain sufficient conditions for two-level traceability
codes. If time permits, we will briefly describe a concatenated
construction which permits decoding in polynomial time.
(Joint work with Alexander Barg)
Consider a first order, linear and time-invariant discrete time system driven by Gaussian and zero mean white process noise, a pre-processor that accepts causal measurements of the state of the system, and a state estimator. The pre-processor and the state estimator are not co-located, and, at every time-step, the pre-processor sends either a real number or an erasure symbol to the estimator. We seek the pre-processor and the estimator that jointly minimize a cost that combines two terms; the expected squared state estimation error and a communication cost. The communication cost is zero for erasure symbols and a pre-selected constant otherwise. We show that the optimal pre-processor follows a threshold policy, and that the optimal estimator is a Kalman-like filter that updates its estimate linearly in the presence of erasures. Existing work has adopted such a Kalman-like structure, but this paper is the first to prove its optimality.
We investigate perfect secret key generation for a
``pairwise independent network'' model in which every pair of
terminals observes correlated sources that 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. This communication is observed by all the terminals as well as by an eavesdropper. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible. All the terminals
cooperate in generating the secret key, with perfect secrecy being required from the eavesdropper. For this model, we introduce the concept of communication for perfect omniscience using which we first obtain a single-letter characterization of the perfect secret key capacity.
Moreover, this perfect secret key capacity is shown to be achieved by linear noninteractive communication, and coincides with the (standard) secret key capacity. Our second contribution, exploiting the notion of communication for perfect omniscience, is a new nonasymptotic and computable upper bound for the combinatorial problem of maximal Steiner tree packing in a multigraph. Thus,
our work establishes certain connections among perfect secrecy
generation and communication for perfect omniscience for the
pairwise independent network model, and Steiner tree packing.
Joint work with Prof. Barg, Prof. Narayan, Alex Reznik
and Chunxuan Ye.
This is joint work with my advisor Prof. Prakash Narayan.