Given an code , a codeword tester for is a randomized algorithm (call it ) with the following properties (below is the received word and and are some fixed real and integer respectively):

- If then accepts with probability .
- If then rejects with probability at least .
- queries at most positions in .

Let us try to get a sense of the parameters. If , then of course can get a tester — the problem just reduces to error detection. However, the catch is that the number of *queries* needs to be at least *sub-linear* and ideally, a **constant** independent of . It is not too hard to convince yourself that in such a case one cannot have a deterministic algorithm (which is why in the definition is allowed to be a randomized algorithm). Further, one cannot hope to be able to decide if for *every* whether . Thus, in property 2. above, we only need to reject received words that have a large Hamming distance for every codeword (for received words in the “middle” is allowed to have arbitrary behavior). Codes with sub-linear query complexity tester are called *Locally Testable Codes* (or **LTCs**).

Let us now pause for a bit and think why we would like to study such a notion. Here are two reasons: the first one is “practical” and is motivated by coding theory considerations while the second is not practical at all and is motivated by complexity theory (though the motivation is pretty darn strong):

- Such testers as above can be used as a filter. They can serve as light weight procedures (recall that the ideal tester only probes constant many places and hence, the running time will be constant) that can detect received words that have more errors than (some) decoding algorithm for can tolerate. The advantage is that we save on running our “expensive” decoding algorithms on received words that it cannot recover from.
- Perhaps the most striking use of codeword testing is in the proof of the
__PCP theorem__. (The theorem was first proven in__two____papers__by Arora, Lund, Motwani, Sudan, Szegedy and Arora, Safra.) Without going into the details, the PCP theorem has been one of the most influential results in complexity theory and has lead to, among other things, a much better understating of the__approximability__of NP-complete problems. Unfortunately, describing this connection takes a major part of a semester long course (and is out of scope of this puny blog post).

Now the most fundamental question regarding codeword testing is the following:

- Does there exist a family of codes with constant rate and constant relative distance that can be tested with constant number of queries?

For ease of reference I’ll refer to codes that answer the question above in the affirmative as *ideal LTCs*. Remarkably, it is **not known** if ideal LTCs exits or not.

Your task in this project will be to study the literature related to tackling the above question (either from the perspective of proving upper bounds *or* lower bounds). Here are some papers that should help you start out.

**Upper bounds**- The paper by Kaufman and Ron titled
__Testing Polynomials over General Fields__(FOCS04) looks at designing testers for a particular family of codes called__Reed-Muller__codes (which we will see later in the course). Codeword testers for Reed-Muller codes were crucial in the early proofs of the PCP theorem (the__recent proof__of the PCP theorem by Dinur does not use Reed-Muller codes. Dinur’s paper also holds the record for the LTC with the best known rate for constant query complexity). The paper by Kaufman and Ron essentially resolves the question for getting testers for Reed-Muller codes with optimal query complexity. - Recently, there has been an interesting interplay between PCPs and LTCs: LTCs have been constructed using (variants of) PCPs. A good place to start studying these connections is Goldreich‘s
__survey__. - Kaufman and Litsyn in their paper titled
__Almost Orthogonal Linear Codes are Locally Testable__(FOCS05) looks at the codeword testing problem for certain classes of codes. The proof techniques are different from the ones used in the sequence of work leading up to the paper of Kaufman and Ron. - You can also look at this
__chapter__in my__thesis__(based on joint work with Guruswami) that looks at a slightly different version of codeword testing (motivated by the “practical” angle mentioned a few paragraphs back). It also has a survey of some of the results in the usual codeword testing setting.

- The paper by Kaufman and Ron titled
**Lower bounds**(Unfortunately not much is known for lower bounds but here are some results)- The paper by Ben-Sasson, Harsha and Raskhodnikova titled
__Some 3CNF properties are hard to test__(STOC03) shows that most LDPC codes are not ideal testers. - Babai, Shpilka and Stefankovic in their paper titled
__Locally testable cyclic codes__(FOCS03) prove that cyclic codes are not ideal LTCs - Ben-Sasson, Goldreich and Sudan in their paper
__Bounds on 2-Query Codeword Testing__(RANDOM06) prove that there are no ideal LTCs that can be tested with two queries.

- The paper by Ben-Sasson, Harsha and Raskhodnikova titled

In short [:-)], codeword testing is a very interesting area where lots of research still needs to be done (especially in the obtaining lower bounds).

Thanks for sharing boundary value analysis

By:

piyush sinhaon October 7, 2009at 12:01 pm