On 2-Query Codeword Testing with Near-Perfect Completeness

DOI10.1007/11940128_28MaRDI QIDQ5459122zbMATH OpenOpenAlexFDO

Authors Venkatesan Guruswami

Publication date 24 April 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11940128_28

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Bounds on \(2\)-query codeword testing
• New direct-product testers and 2-query PCPs
• A query efficient non-adaptive long code test with perfect completeness
• New direct-product testers and 2-query PCPs
• Bounds on 2-query locally testable codes with affine tests

Cited in

(6)

• Bounds on 2-query locally testable codes with affine tests
• A query efficient non-adaptive long code test with perfect completeness
• A query efficient non-adaptive long code test with perfect completeness
• Limitation on the Rate of Families of Locally Testable Codes
• Bounds on \(2\)-query codeword testing
• Towards lower bounds on locally testable codes via density arguments

This page was built for publication: On 2-Query Codeword Testing with Near-Perfect Completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5459122)