Optimal PSPACE-hardness of approximating set cover reconfiguration
From MaRDI portal
Cites work
- A threshold of ln n for approximating set cover
- Analytical approach to parallel repetition
- Approximability of the subset sum reconfiguration problem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Derandomized graph products
- Expander graphs and their applications
- Explicit expanders of every degree and size
- Explicit Near-Ramanujan Graphs of Every Degree
- Finding paths between 3-colorings
- Games, puzzles, and computation
- Gap amplification for reconfiguration problems
- Gap preserving reductions between reconfiguration problems
- Improved approximation algorithms for label cover problems
- Interactive proofs and the hardness of approximating cliques
- Introduction to reconfiguration
- On the complexity of reconfiguration problems
- On the hardness of approximating minimization problems
- Optimal PSPACE-hardness of approximating set cover reconfiguration
- 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
- Shortest paths between shortest paths
- Shortest Reconfiguration of Colorings Under Kempe Changes
- Shortest reconfiguration of perfect matchings via alternating cycles
- Shortest reconfiguration paths in the solution space of Boolean formulas
- Smooth and strong PCPs
- Some optimal inapproximability results
- The complexity of change
- The complexity of rerouting shortest paths
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The PCP theorem by gap amplification
Cited in
(6)- Gap preserving reductions between reconfiguration problems
- Optimal PSPACE-hardness of approximating set cover reconfiguration
- On approximate reconfigurability of label cover
- Tight inapproximability of target set reconfiguration
- Asymptotically optimal inapproximability of maxmin k-cut reconfiguration
- Yet another simple proof of the PCRP theorem
This page was built for publication: Optimal PSPACE-hardness of approximating set cover reconfiguration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875111)
