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

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

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

(4)

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

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)