Gap Amplification in PCPs Using Lazy Random Walks

DOI10.1007/11786986_10MaRDI QIDQ3613752zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(6)

• Gap amplification for small-set expansion via random walks
• Bravely, moderately: a common theme in four recent works
• Bridging a Small Gap in the Gap Amplification of Assignment Testers
• The PCP theorem by gap amplification
• The PCP theorem by gap amplification
• Gap preserving reductions between reconfiguration problems

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)