Faculty Recruiting Support CICS

Coding Theory for Data Summarization and Reconstruction

20 Mar
Wednesday, 03/20/2019 12:15pm to 1:15pm
Computer Science Building Room 140
Theory Seminar
Speaker: Arya Mazumdar

Error-correcting codes are classically used to fulfill Shannon's promise of achieving the optimal rate of information transfer through noisy media. For the past seventy years, there have been intermittent breakthroughs in the theory of codes, and many codes of algebraic and combinatorial varieties have been proposed, namely the BCH codes, Reed-Solomon and Reed-Muller codes, Algebraic Geometric codes, Low-Density Parity Check matrix (LDPC) codes, and the Polar codes. Methods of algebraic combinatorics were also developed to characterize the fundamental limits of codes. Over the years, it has also been observed that the symmetry properties of many of the aforementioned families of codes can be useful for the purpose of derandomization, and codes can be used in sampling, hashing and other data summarization procedures that constitute a major area within Data Science. In this talk, we survey some of the most fundamental of such directions, emphasizing my recent works:

 1. The role of coding theory in sparse data processing, such as compressed sensing and combinatorial group testing. This includes both the constructions of sparse recovery schemes as well as methods for the efficient recovery of sparse data.

2. Applications of coding theory to dimensionality reduction, including Johnson Lindenstrauss transforms, and low-rank approximations.