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

Link to this comparison view

Both sides previous revision Previous revision
en:group:seminars:20110413 [2011/04/14 10:58]
en:group:seminars:20110413 [2011/04/14 11:04]
Line 13: Line 13:
 ==== abstract ==== ==== 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, 
 +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 
 +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.