Expanders, Property Testing and the PCP theorem

Student Presentation #8

Posted in presentations by atri on January 13, 2009

(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  2-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 C\subseteq F^n be a (2, c, s)-locally testable linear code with minimal relative distance \delta>0, for c> s, we have |C| \le |F|^{3/\delta}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: