Harvard Theory of Computation Seminar
Analysis of MAX-XORSAT and its Generalizations, with Applications to Distributed Compression and "Dirty Paper" Coding
Martin Wainwright, UC Berkeley
Place and Time: Monday, April 2, Maxwell Dworkin 221. Refreshments at 2:30pm, talk at 2:45pm.
For a range of error-correction problems, the past two decades have
witnessed dramatic advances in both theory and practice, particularly in the
area of sparse graph codes and efficient message-passing algorithms.
However, many other problems involve delicate combinations of both
error-correction and data compression. The range of possible applications
is broad, including digital watermarking, distributed data compression,
coding for memory with defects, and MIMO communication. However, in this
realm of joint source/channel coding, there remain a variety of open
It is well known how to achieve the Shannon limits for these problems using
unstructured random codes. The focus of this talk is codes based on very
sparse graphs, which are easily stored and amenable to efficient algorithms.
We begin by analyzing the performance of bounded degree MAX-XORSAT
constructions using both combinatorial and information-theoretic methods.
This analysis leads naturally to considering generalized MAX-XORSAT
ensembles, constructed by compounding low-density parity check (LDPC) with
low-density generator matrix (LDGM) codes. We prove that suitably designed
codes of this type, even though all degrees remain bounded, can nonetheless
achieve the Shannon limits. We conclude with some discussion of open issues
Based on joint work with Alex Dimakis, Emin Martinian and Elitza Maneva.