Bridging a Small Gap in the Gap Amplification of Assignment Testers

DOI10.1007/978-3-030-43662-9_2MaRDI QIDQ5098766zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Or Meir

Publication date 30 August 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-43662-9_2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Gap Amplification in PCPs Using Lazy Random Walks
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• The PCP theorem by gap amplification
• The PCP theorem by gap amplification
• New direct-product testers and 2-query PCPs

Cites work

• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• The PCP theorem by gap amplification

This page was built for publication: Bridging a Small Gap in the Gap Amplification of Assignment Testers

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