Speaker: Sanjeev Arora Princeton University
Time: 2009-03-02 16:00-2009-03-02 17:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance (coming close to that of iterative decoding algorithms) and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel.
 
 
Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding which allows us to prove that LP decoding corrects a 0.05-fraction of errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and significantly higher than the best previously noted correctable bit error rates. Unlike other techniques, our analysis is primal-only and works by exploiting an explicit connection between LP decoding, local-versus-global properties, and message passing algorithms.
 
(Joint work with Costis Daskalakis and David Steurer; to appear at ACM STOC 2009)

 

Short Bio:

Sanjeev Arora (born January 1968) is a computer scientist who is best known for his seminal work on probabilistically checkable proofs and, in particular, on the PCP theorem. He is also known for his work on designing new approximation algorithms for Geometric Traveling Salesman problem and graph partitioning problems. His PhD thesis on probabilistically checkable proofs received the ACM Doctoral Dissertation Award in 1995. He was awarded the G?del Prize for his work on the PCP theorem in 2001, and in 2009 he was inducted as a Fellow of the Association for Computing Machinery.

His research area is theoretical computer science, specifically in computational complexity theory, uses of randomness in computation, probabilistically checkable proofs, computing approximate solutions to NP-hard problems, and geometric embeddings of metric spaces.