Yet another simple proof of the PCRP theorem

DOI10.4230/LIPICS.ICALP.2025.122MaRDI QIDQ7397579zbMATH OpenFDO

Authors Naoto Ohsaka

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.122

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A note on succinct representations of graphs
• A survey on the parameterized complexity of reconfiguration problems
• Alphabet reduction for reconfiguration problems
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Asymptotically optimal inapproximability of maxmin k-cut reconfiguration
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complexity of independent set reconfigurability problems
• Computational Complexity
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Games, puzzles, and computation
• Gap amplification for reconfiguration problems
• Gap preserving reductions between reconfiguration problems
• scientific article; zbMATH DE number 7272506 (Why is no real title available?)
• scientific article; zbMATH DE number 7803587 (Why is no real title available?)
• Introduction to reconfiguration
• On approximate reconfigurability of label cover
• On the complexity of reconfiguration problems
• On the parameterized complexity of reconfiguration problems
• Optimal PSPACE-hardness of approximating set cover reconfiguration
• Parameterized problems complete for nondeterministic FPT time and logarithmic space
• Polynomial Codes Over Certain Finite Fields
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration in bounded bandwidth and tree-depth
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Some optimal inapproximability results
• Succinct representations of graphs
• The complexity of change
• The complexity of dominating set reconfiguration
• The complexity of independent set reconfiguration on bipartite graphs
• The complexity of rerouting shortest paths
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The PCP theorem by gap amplification

This page was built for publication: Yet another simple proof of the PCRP theorem

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