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.

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.

09/17,09/24 Professor Navin Kashyap (Queen's University at Kingston) , Complexity of Graphical Realizations of Linear Codes

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.

10/01 Hiroshi Nozaki (U. Texas, Brownsville and Tohoku University) , Geometrical approach for strongly regular graphs

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.

10/08 Arya Mazumdar (UMD), Rank Permutation Codes

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.

10/15 Punarbasu Purkayastha (UMD), Near-MDS ordered codes and distributions

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.

10/22 Prof. Alexander Barg (UMD), On the number of errors correctable with codes on graphs

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.

10/29 Himanshu Tyagi (UMD), Secure Computation

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

11/05 Sirin Nitinawarat (UMD), Perfect Secrecy, Perfect Omniscience and Steiner Tree Packing

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.