Differences

This shows you the differences between two versions of the page.

--- en:group:seminars:20110413 [2011/04/14 10:58]
maatouk
+++ en:group:seminars:20110413 [2016/06/23 11:26] (current)
@@ Line 13: / Line 13: @@
 ==== abstract ====
-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,
+) 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.

Title

Sub-Title

Differences