Computer Science Thesis Oral

Thursday, June 23, 2016 - 10:30am to 12:00pm


8102 Gates & Hillman Centers



Error-correcting codes were originally developed in the context of reliable delivery of data over a noisy communication channel and continue to be widely used in communication and storage systems.  Over time, error-correcting codes have also been shown to have several exciting connections to  areas in theoretical computer science. Recently, there have been several advances including new constructions of efficient codes as well as coding for different settings. This thesis proposal exploresseveral new directions in modern coding theory. To this end, we: Provide a theoretical analysis of polar codes, which were a breakthrough made by Arikan in 2008.  We show that polar codes over prime alphabets are the first explicit construction of efficient codes to provably achieve Shannon capacity for symmetric channels with polynomially fast convergence. We  introduce interesting new techniques involving entropy sumset inequalities, which are an entropic analogue of sumset inequalities studied in additive combinatorics.  Consider the recent problem of coding for two-party interactive communication, in which two parties wish to execute a protocol over a noisy interactive channel. Specifically, we provide an explicit  interactive coding scheme for oblivious adversarial errors and bridge the gap between channel capacities for interactive communication and one-way communication. We also consider a related question involving one-way communication with partial feedback. Study the problem of list decodability for codes. We resolve an open question about the list  decodability of random linear codes and show surprising connections to the field of compressed sensing, in which we provide improved bounds on the number of frequency samples needed for exact reconstruction of sparse signals (improving upon work of Cand├Ęs-Tao and Rudelson-Vershynin).  Study locally-testable codes and affine invariance in codes. Specifically, we investigate the  limitations posed by local testability, which has served as an important notion in the study of probabilistically checkable proofs (PCPs) and hardness of approximation. Thesis Committee:Venkatesan Guruswami (Chair)Bernhard HaeuplerGary MillerEmmanuel Abbe (Princeton University)

For More Information, Contact:


Thesis Oral