Student Presentation #8

(Guest post by Swapnoneel Roy)

I presented the paper titled Bounds on 2-Query Codeword Testing by Eli Ben-Sasson, Oded Goldreich, and Madhu Sudan. In the paper, the authors study  -query codeword testers. The main results in the paper are the upper bounds on the size of linear (respectively binary) codes that admit such testers (respectively testers of perfect completeness).

In other words, it was showed, if be a -locally testable linear code with minimal relative distance , for , we have .