Alphabet reduction for reconfiguration problems
From MaRDI portal
Cites work
- A Parallel Repetition Theorem
- Alphabet reduction for reconfiguration problems
- Analysis of Boolean Functions
- Approximability of the subset sum reconfiguration problem
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Computational Complexity
- Explicit expanders of every degree and size
- Explicit Near-Ramanujan Graphs of Every Degree
- Gap amplification for reconfiguration problems
- Gap preserving reductions between reconfiguration problems
- scientific article; zbMATH DE number 7272506 (Why is no real title available?)
- Introduction to reconfiguration
- Limits of local algorithms over sparse random graphs
- On Dinur’s proof of the PCP theorem
- On the complexity of reconfiguration problems
- On the power of multi-prover interactive protocols
- On the solution-space geometry of random constraint satisfaction problems
- Optimal low-degree hardness of maximum independent set
- Optimization, approximation, and complexity classes
- Rigid matrices from rectangular PCPs or: hard claims have complex proofs
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Some optimal inapproximability results
- The complexity of change
- The PCP theorem by gap amplification
Cited in
(2)
This page was built for publication: Alphabet reduction for reconfiguration problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875076)
