Information and Coding Theory Seminar  

Abstracts of talks

Spring 2009

2/12 Alexander Barg (UMD), Polarization Codes

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.

2/19 Arya Mazumdar (UMD), Linear Balancing Sets

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.

3/5 Prasanth Anthapadmanabhan (UMD), Two-level Fingerprinting Codes

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)

3/12 Gabriel Lipsa (UMD), Optimal Distributed State Estimation with Communication Cost: A Majorization Theory Approach

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.

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

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.

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.

This is joint work with my advisor Prof. Prakash Narayan.

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