Good Locally Testable Codes with Small Alphabet and Small Query Size

Uriya First, Stav Lazarovici

Ben-Sasson, Goldreich and Sudan showed that a binary error correcting code admitting a $2$-query tester cannot be good, i.e., it cannot have both linear distance and constant rate.…