Information and Coding Theory Seminar
Abstracts of talks
Fall 2009
09/10 Alexander Barg (UMD) ,
Bounds On the Size of Sets with Few Distances ABSTRACT:
Consider a binary code C=(x1,x2,...,xM) of length n such that for all i,j the distance d(xi,xj) is either a or b or c (or 0) for some fixed numbers a,b,c. How large can M be?
This is an instance of a large group of problems in combinatorics and geometry that include the Frankl-Wilson bound on families of finite sets with restricted intersections, the Erdos-Ko-Rado theorem, the Delsarte-Goethals-Seidel bound for spherical codes, and so on. 09/17,09/24 Professor Navin Kashyap (Queen's University at Kingston) , Complexity of Graphical Realizations of Linear Codes 10/01 Hiroshi Nozaki (U. Texas, Brownsville and Tohoku University) , Geometrical approach for strongly regular graphs 10/08 Arya Mazumdar (UMD), Rank Permutation Codes 10/15 Punarbasu Purkayastha (UMD), Near-MDS ordered codes and distributions 10/22 Prof. Alexander Barg (UMD), On the number of errors correctable with codes on graphs 10/29 Himanshu Tyagi (UMD), Secure Computation 11/05 Sirin Nitinawarat (UMD), Perfect Secrecy, Perfect Omniscience and Steiner Tree Packing
We will introduce some of these problems and show the two main
methods of proving the results. New results that were
obtained in a joint work with Oleg Musin (arxiv:0905.2423) include an improvement of the RayChaudhuri-Wilson bound on the size of uniform s-intersecting families and similar theorems. For small n we also find the exact size of maximal codes with 2,3, and 4 distances.
ABSTRACT: A graphical realization of a linear code C consists of an assignment of the coordinates of C to the vertices of a graph, along with a specification of linear state spaces and linear "local constraint'' codes to be associated with the edges and vertices, respectively, of the graph. Special cases of such realizations are trellises, Tanner graphs, and indeed any factor graph. A graphical realization of C specifies an associated sum-product decoding algorithm for C. The computational complexity of the associated sum-product algorithm is largely determined by the dimensions of the local constraint codes in the realization. Thus, the complexity of a graphical realization may be defined in terms of the dimensions of the local constraint codes. In this talk, we will give an overview of graphical realizations, and what is known about the complexity of graphical realizations of a linear code.
ABSTRACT: A simple graph G=(V,E) is called a strongly regular
graph with parameters (v,k,lambda,mu) if the cardinality of
V is v, G is k regular, any two adjacent vertices are adjacent
to lambda common vertices, and any two nonadjacent vertices are adjacent to mu common vertices. We have a certain Euclidean spherical embedding from a strongly regular
graph. By the geometrical theory of the Euclidean sphere, we construct new examples of strongly regular graphs with parameters (276,140,58,84). For these parameters, only one graph was known by Goethals-Seidel (1975) .
The survey paper by Brouwer and Lint (1984) asked whether this graph is unique or not.
ABSTRACT: The inversion distance between two permutations is
defined as the minimum number of adjacent transpositions
required to convert one permutation to the other. Codes in the permutation space with inversion distance, also called rank permutation codes, have been recently proposed as a means for protecting flash memory devices from errors.
We show the existence of a family of rank permutation
codes that correct a constant number of errors and have size
within a constant factor of the sphere packing upper bound.
The construction relies on the well-known Bose-Chowla Theorem
in additive number theory. We also discuss several possible
ways to bound the size of a rank permutation code of a given
minimum distance. It is interesting that unlike many other
asymptotic coding problems, the space of permutations with
inversion distance affords an exact answer for the growth rate of the size of optimal codes. The proof of the bounds relies on weight-preserving embeddings of permutation space into other metric spaces.
Joint work with Prof. Alexander Barg.
ABSTRACT: Codes in the ordered Hamming space are closely related to the study of
distributions of points in the unit cube, used for numerical integration
of functions. Maximum Distance Separable codes, whose minimum distance
meets the Singleton upper bound, have been well studied in the Hamming and
the ordered Hamming space. We generalize the concept of linear near-
Maximum Distance Separable codes (whose minimum distance is just one unit
away from the Singleton bound) to the ordered Hamming space. We show an
equivalent characterization of these codes in the context of distributions
of points in the unit cube, and we determine the weight distribution of
these codes. In studying the properties of these codes, we analyze the
code simultaneously as a linear code and as a linear orthogonal array.
Joint work with Prof. Alexander Barg.
ABSTRACT: We study ensembles of codes on graphs (generalized LDPC codes) and their extension to codes on hypergraphs constructed from random graphs and fixed local constraint codes. It is known that the minimum distance of codes in these ensembles grows linearly with the code length. We show that these codes correct a linearly growing number
of errors under simple iterative decoding algorithms. In particular, we show that this property extends to codes constructed by parallel concatenation of Hamming codes and other codes with small minimum
distance.
Joint work with Arya Mazumdar.
ABSTRACT: Two terminals observe i.i.d. repetitions of the random variables X and Y, respectively, with
a known joint distribution. Their objective is to compute a function g of X and Y
reliably and securely. Both the terminals must compute the values of the
function using interactive communication F in such a way that the probability of a block
error in computation decays to zero with blocklength, and the function values are asymptotically
independent of the communication F. We address the case of single-sided communication as well
as general versions of this problem, and give a complete characterization of functions for which
the mentioned objective can be met. An interesting result is that all functions with
entropy less than the secret key capacity of the correlated sources X and Y can be computed securely.
This is joint work with Dr. Piyush Gupta (Bell Labs) and Prof. Prakash Narayan (UMD).
ABSTRACT: We investigate perfect secret key (SK) 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 SK shared by
a given set of terminals at the largest rate possible. All the
terminals cooperate in generating the SK, 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 SK capacity in terms of the minimum rate of
communication for perfect omniscience.
We further explore the connection among the information theoretic
problems of perfect SK generation, minimum communication for
perfect omniscience and the combinatorial problem of maximal
Steiner tree packing. Specifically, we propose an efficient
algorithm, derived from maximal Steiner tree packing in the
multigraph, for the terminals to generate a perfect SK. This
algorithm employs linear noninteractive communication which leads
simultaneously to perfect omniscience and also to the generation
of a perfect SK of size equal to the maximum size of the Steiner
tree packing. The algorithm is shown to achieve perfect SK
capacity when all terminals seek a perfect SK. In a general case,
when only a subset of the terminals seek secrecy, we show that the
algorithm always achieves at least half of the perfect SK
capacity.
Focusing on the case with only one helper terminal, a necessary
and sufficient condition for the mentioned algorithm to achieve
the perfect SK capacity is given. A simpler (and stronger)
sufficient condition, stated in terms of the communication rate of
the helper terminal, will also be discussed.
Joint work with Prof. Narayan and Prof. Barg.
11/19 Yury Polyanskiy (Princeton), Achievability bounds in the regime of fixed
probability of error
ABSTRACT: Recently, we demonstrated that studying the asymptotics at fixed probability of error results in closed form approximation of the fundamental limits, which is surprisingly tight even for blocklengths as small as 200. This motivates the study of the achievability bounds
>in this regime as opposed to a more traditional regime of fixed rate (error-exponents). Gallager bound is better in one regime and Feinstein-Shannon is better in the other. This implies that neither is the best and motivates the search for better ones. I will present some new bounds and show which new results can be proved by using them. If time permits I will also rigorously derive the normal approximation expansion for the AWGN and discuss some further
applications.
Joint work with Sergio Verdu and Vincent Poor.