This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
en:group:seminars:20110413 [2011/04/14 10:57] maatouk created |
en:group:seminars:20110413 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | page | + | ---- dataentry seminar ---- |
| + | date_dt : 2011-04-13 | ||
| + | title : Symmetric LDPC codes are not necessarily locally testable | ||
| + | speaker : Ghid Maatouk | ||
| + | affiliation : ALGO - EPFL | ||
| + | time : 16h15 | ||
| + | room : BC129 | ||
| + | table : seminars | ||
| + | =================== | ||
| + | template:datatemplates:seminar | ||
| + | ----------------------- | ||
| + | |||
| + | |||
| + | ==== abstract ==== | ||
| + | Locally testable codes, i.e., codes where membership in the code is | ||
| + | testable with a constant number of queries, have played a central role | ||
| + | in complexity theory. It is well known that a code must be a | ||
| + | "low-density parity check" (LDPC) code for it to be locally testable, | ||
| + | but few LDPC codes are known to the locally testable, and even fewer | ||
| + | classes of LDPC codes are known not to be locally testable. Indeed, most | ||
| + | previous examples of codes that are not locally testable were also not | ||
| + | LDPC. The only exception was in the work of Ben-Sasson et al. (SICOMP, | ||
| + | 2005) who showed that random LDPC codes are not locally testable. Random | ||
| + | codes lack "structure" and in particular "symmetries" motivating the | ||
| + | possibility that "symmetric LDPC" codes are locally testable, a question | ||
| + | raised in the work of Alon et al. (IEEE IT, 2005). If true such a result | ||
| + | would capture many of the basic ingredients of known locally testable | ||
| + | codes. | ||
| + | |||
| + | In this work we rule out such a possibility by giving a highly symmetric | ||
| + | ("2-transitive") family of LDPC codes that are not testable with a | ||
| + | constant number of queries. We do so by continuing the exploration of | ||
| + | "affine-invariant codes" --- codes where the coordinates of the words | ||
| + | are associated with a finite field, and the code is invariant under | ||
| + | affine transformations of the field. New to our study is the use of | ||
| + | fields that have many subfields, and showing that such a setting allows | ||
| + | sufficient richness to provide new obstacles to local testability, even | ||
| + | in the presence of structure and symmetry. | ||
| + | |||
| + | This is joint work with Eli Ben-Sasson, Amir Shpilka and Madhu Sudan. | ||