Combinatorics Seminar

When: Sunday, April 11, 10am Where: Schreiber 309 Speaker: Tali Kaufman, Weizmann Institute Title: Symmetric LDPC codes and local testing

Abstract:

Local computation tasks (as local testing, correcting, decoding) is possible in codes based on polynomials. This is related to the fact that such codes are highly symmetric, yet they are defined by short linear equations. Codes defined by short linear equations are called LDPC. In the heart of this work is the following question: Could we have high rate codes which are highly symmetric, yet are defined by short linear equations? In this work we construct codes with rate better than polynomial codes that are defined by short equations. Moreover we obtain bounds on the best rate of such symmetric codes.

Joint work with Avi Wigderson