Gap Amplification in PCPs Using Lazy Random Walks

DOI10.1007/11786986_10zbMATH Open1223.68049OpenAlexW1530525467MaRDI QIDQ3613752FDOQ3613752

Authors: Jaikumar Radhakrishnan 

Publication date: 12 March 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11786986_10

Recommendations

• Gap amplification for small-set expansion via random walks
• The PCP theorem by gap amplification
• The PCP theorem by gap amplification
• Amplification and Derandomization without Slowdown
• Approximability in the GPAC
• The parameterized complexity of probability amplification
• On lazy randomized incremental construction
• On lazy randomized incremental construction
• Pseudo-gaps for random hopping models
• Performances of pure random walk algorithms on constraint satisfaction problems with growing domains

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (4)

• The PCP theorem by gap amplification
• Gap amplification for small-set expansion via random walks
• The PCP theorem by gap amplification
• Bravely, moderately: a common theme in four recent works

This page was built for publication: Gap Amplification in PCPs Using Lazy Random Walks

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