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.

ABSTRACT

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 questions.

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 and challenges.

Based on joint work with Alex Dimakis, Emin Martinian and Elitza Maneva.