Monday, December 7, 2015 - 3:00pm
Location:Reddy Conference Room 4405 Gates & Hillman Centers
Speaker:AMEYA VELINGKER - Rescheduled, Ph.D. Student http://www.cs.cmu.edu/~avelingk/
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. More recently, error-correcting codes have been shown to have several exciting connections to areas in theoretical computer science.
This thesis proposal explores several new directions in modern coding theory. To this end, we:
1.) Show that polar codes over prime alphabets are the first explicit construction of efficient codes to provably achieve capacity for symmetric channels with a polynomial convergence. We introduce interesting new techniques involving entropy sumset inequalities, which are an entropic analogue of sumset inequalities studied in additive combinatorics.
2.) Consider the problem of coding over two-party interactive channels. Specifically, we bridge the gap between channel capacities for interactive communication and one-way communication. We also consider a model of one-way communication with partial feedback.
3.) 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.
4.) Study locally-testable codes and affine invariance. Specifically, we investigate the limitations posed by the local testability property.
Thesis Committee: Venkatesan Guruswami (Chair) Bernhard Haeupler Gary Miller Emmanuel Abbe (Princeton University)
Copy of Thesis Summary