Pith. sign in

REVIEW 5 minor 297 references

Optimal PSPACE-hardness of Approximating $q$-CSP Reconfiguration

T0 review · 0 major / 5 minor · reviewed 2026-07-31 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Approximating Maxmin q-CSP reconfiguration is PSPACE-hard above 1/2^{q-1} and lies in NP just below it.

desk verdict Closes the GKMRW open problem with a matching 1/2^{q-1} PSPACE threshold for every arity, via a new tolerant q-query product tester and clean gap amplification. read the letter →

arxiv 2607.28099 v1 pith:MBKKUPNG submitted 2026-07-30 cs.CC cs.DMcs.DS

Shuichi Hirahara , Naoto Ohsaka This is my paper · ORCID
classification cs.CCcs.DMcs.DS MSC 68Q1768Q2568W25
keywords Maxminq-CSPReconfigurationPSPACE-hardnessofapproximationdirectproducttestinggapamplificationthreshold
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper pins down the exact approximation threshold for Maxmin q-CSP Reconfiguration: given a satisfiable q-ary constraint system and two satisfying assignments, find a path that flips one variable at a time while keeping the worst intermediate assignment as good as possible. For every arity q at least 2, any factor strictly better than 1/2^{q-1} is PSPACE-hard, even on regular instances; any factor strictly worse is achievable by a short certificate and therefore lies in NP whenever a perfect path exists. The matching upper and lower bounds settle an open question for the q=2 case and reveal a surprising complexity split: for binary constraints the threshold separates P from PSPACE, while for arity four and higher it separates NP-completeness from PSPACE-completeness. A deterministic polynomial-time algorithm recovers the same factor on regular instances. The results show that reconfiguration approximability can sit in three distinct complexity regimes rather than the two that earlier work had assumed.

What carries the argument

A tolerant q-query direct-product tester on the Johnson graph. Its soundness converts acceptance probability p into approximate agreement with a genuine direct product at rate roughly p^{1/(q-1)}, which supplies the precise 1/2^{q-1} hardness factor when the tester is composed with a gap-amplifying reduction from 2-CSP reconfiguration.

What would settle it

Exhibit either a polynomial-time algorithm that beats factor 1/2^{q-1}+ε on regular q-CSP reconfiguration instances, or a proof that GAP_{1,1/2^{q-1}-ε} q-CSP reconfiguration is PSPACE-hard, for any fixed q≥2.

Watch

Extended reading notes

Core claim

For every integer q≥2 and every ε>0, Maxmin q-CSP Reconfiguration is PSPACE-hard to approximate within factor 1/2^{q-1}+ε (even when every variable appears equally often), while a (1/2^{q-1}-ε)-factor approximation is in NP in the perfect-completeness case; the two statements together are optimal under NP≠PSPACE.

Load-bearing premise

The argument starts from a known constant-gap PSPACE-hard instance of 2-CSP reconfiguration on regular graphs; if that seed hardness fails, the optimal factor for larger arities does not follow.

Editorial extensions

If this is right

  • For binary CSPs the approximation threshold 1/2 cleanly separates polynomial time from PSPACE-completeness.
  • For arity-four and higher CSPs the same threshold separates NP-completeness from PSPACE-completeness—the first reconfiguration problem known to exhibit this three-way split.
  • A deterministic poly-time algorithm already achieves the optimal factor on every regular instance.
  • Any future improvement of the hardness factor would require a stronger seed than the existing PCRP theorem supplies.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The open complexity of a (1/4-ε)-factor approximation for ternary CSPs is the natural next target; a poly-time algorithm would unify the q=2 and q=3 pictures, while NP-hardness would require highly irregular gadgets.
  • The same tolerant multi-query tester may yield tight thresholds for other reconfiguration problems whose natural encodings admit direct-product lifts.
  • The appearance of an NP-complete intermediate regime suggests that many PSPACE-complete reconfiguration problems may hide similar NP islands once approximation is allowed.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies the approximability of Maxmin q-CSP Reconfiguration. It proves that for every q≥2 and ε>0, approximating the problem within a factor of 1/2^{q-1}+ε is PSPACE-hard (even on regular instances), via a gap-amplifying reduction from the PCRP theorem that uses a new tolerant q-query direct-product tester. Complementarily, it shows that a (1/2^{q-1}-ε)-factor approximation lies in NP in the perfect-completeness case (by low/high-degree sparsification and random-order interpolation), and gives a deterministic polynomial-time algorithm achieving the same factor on regular instances. Together these establish an optimal PSPACE-hardness threshold under NP eq PSPACE, with a striking complexity dichotomy: for q=2 the threshold separates P from PSPACE-complete, while for q≥4 it separates NP-complete from PSPACE-complete.

Significance. The result closes the open problem of Guruswami et al. on the optimal PSPACE threshold for Maxmin 2-CSP Reconfiguration and substantially strengthens prior PSPACE-hardness factors of Gur–Minzer–Weissenberg–Zheng. The discovery that approximate reconfiguration can be NP-complete (rather than only P or PSPACE-complete) is conceptually new and forces a finer complexity landscape for the area. The technical contribution—a tolerant multi-query direct-product tester whose soundness yields the precise 1/2^{q-1} exponent via expander hitting on the Johnson graph—is of independent interest and is supplied with a complete analysis (including the long uniqueness/decoding argument of Appendix A). The matching algorithmic upper bounds (NP membership and a deterministic regular-case algorithm) make the threshold tight under standard assumptions.

minor comments (5)
  1. [Section 2.1.1] In the proof overview (Section 2.1.1) the informal Claims 2.4–2.6 are stated with asymptotic notation that is later made precise only in Section 6; a forward pointer to the exact statements (Claims 6.6–6.8) would help the reader.
  2. [Table 1] Table 1 footnote † asserts that sequential repetition yields the 0.81-factor for q=4 from the q=2 result of GMWZ26; a one-sentence justification or citation of the precise repetition lemma used would remove any ambiguity.
  3. [Section 5] The parameter regime ℓ=Θ(√k), m=Θ(√ℓ) is used throughout Sections 5–6; stating once that these choices simultaneously make ε_{k,ℓ,m}=k^{-Ω(1)} and keep the completeness error o(1) would tighten the exposition.
  4. [Lemma 7.2] In Lemma 7.2 the concrete constant 100 appearing in the degree cutoff Δ=ε^{2}m/(100q log n) is never justified beyond “sufficiently large”; a short calculation showing where the 100 arises from McDiarmid would improve reproducibility.
  5. [Theorems 6.1, 7.1] Several “O_q” and “Ω(1)” hide dependencies on the alphabet size σ that become relevant when σ grows with k (as it does after the reduction); making the dependence explicit in the final statements of Theorems 6.1 and 7.1 would be cleaner.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: optimal threshold is derived by a new gap-amplifying reduction and constructive path arguments, not by fitting or self-definition.

full rationale

The paper’s central claims are (i) PSPACE-hardness of GAP_{1, 1/2^{q-1}+ε} q-CSP Reconfiguration via a polynomial-time gap-amplifying reduction from constant-gap GAP_{1,s} 2-CSP Reconfiguration, and (ii) NP-membership of the complementary (1/2^{q-1}-ε) factor under perfect completeness by sparsifying a satisfying path and interpolating on low-degree variables. The seed hardness is the external PCRP theorem (GKMRW25, HO24b), used as a black-box many-one starting point in the proof of Theorem 6.1 / Lemma 6.2; that is ordinary reduction architecture, not a self-definitional loop or a uniqueness theorem that forces the present factor. The numerical threshold 1/2^{q-1} is obtained analytically: soundness of the new tolerant q-query direct-product tester (Theorem 5.1 / 5.6) yields agreement probability ~p^{1/(q-1)} via expander hitting on the Johnson graph, and the NP-side lower bound uses the elementary inequality θ^q+(1-θ)^q ≥ 2^{1-q} plus McDiarmid concentration (Lemma 7.2) and a deterministic 2q-wise bucket construction (Theorem 8.1). None of these steps renames a fitted parameter as a prediction, smuggles an ansatz that already encodes the target, or equates the claimed optimum with its inputs by construction. Self-citation of prior PCRP/gap work is present but not load-bearing in the circular sense: the new content is the reduction and the matching algorithmic upper bound. Score 0.

Assumptions & free parameters 4 free parameters · 5 assumptions · 1 invented entities

The result rests on standard probabilistic method and expander tools, the external PCRP/PSPACE-hardness seed for 2-CSP reconfiguration, and asymptotic parameter choices (large k, intersection/tolerance scales) that are not data-fitted. No physical or ad-hoc ontological entities are introduced; the ‘tolerant q-query tester’ is a defined algorithm with proved guarantees.

free parameters (4)
  • direct-product block size k = poly(1/ε,1/s,q) large enough
    Chosen sufficiently large depending on s,ε,q so that decoding distance δ(k,ε)≤(1-s)/4 and exponential error terms vanish; asymptotic, not fitted to empirical data.
  • intersection ℓ and tolerance m = ℓ=Θ(√k), m=ℓ^{1-Θ(1)}
    Set ℓ=Θ(√k), m=ℓ^{1-Θ(1)} (e.g. m=1 in the edge-tuple tester) to make ε_{k,ℓ,m}=k^{-Ω(1)}; design parameters of the tester.
  • degree cutoff Δ in NP-membership = ε² m /(100 q log n)
    Δ=Θ(ε² m /(q log n)) splits low/high degree vertices so |H|=O_{q,ε}(log n); analytic choice for McDiarmid concentration.
  • bucket count L in regular algorithm = smallest power of two ≥4q/ε
    L=Θ(q/ε) power of two so checkpoint and bucket Chebyshev bounds beat 1; design parameter.
assumptions (5)
  • domain assumption PCRP theorem: GAP_{1,s} 2-CSP_σ Reconfiguration is PSPACE-complete for some s∈(0,1) and constant σ (on regular instances after gap-preserving reductions).
    Seed hardness for Lemma 6.2 / Theorem 6.1; cited from GKMRW25 and HO24b.
  • standard math Johnson graph J(n,k,ℓ) is an O(ℓ/k)-expander; expander hitting property for length-q walks.
    Used in Proposition 5.2 and Lemmas 5.4–5.5 (DG08, AFWZ95, AKS87).
  • standard math Hoeffding, Chernoff, and McDiarmid concentration inequalities; exact k-wise independent hash families of size M^k.
    Used throughout §§5,7,8 and Lemma 8.2 (Vad12/Joffe).
  • domain assumption NP ≠ PSPACE is required only for the informal optimality slogan; hardness and NP-membership statements are unconditional relative to the PCRP seed.
    Stated in abstract and Corollary 1.3 framing.
  • ad hoc to paper Soundness analysis of 2-query direct product testing in the low-acceptance regime extends to the tolerant multi-query setting as claimed in Theorem 5.6 / Appendix A.
    Core new analytic work; built by extending IKW12/DG08 but is paper-specific and load-bearing for the 1/2^{q-1} exponent.
invented entities (1)
  • Tolerant q-query direct product tester T_q / W_q independent evidence
    purpose: Amplify weak reconfiguration gaps to the optimal 1/2^{q-1} soundness while preserving perfect completeness for approximate product encodings.
    Defined algorithm with completeness/soundness theorems; not an unfalsifiable postulate. Independent mathematical content is the proof, not an external physical handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal PSPACE-hardness of Approximating $q$-CSP Reconfiguration." pith.science (2026). https://pith.science/paper/MBKKUPNG

@misc{pith2026260728099,
  author       = {Pith},
  title        = {Pith review of: Optimal PSPACE-hardness of Approximating $q$-CSP Reconfiguration},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MBKKUPNG}},
  note         = {Machine review of arXiv:2607.28099}
}
abstract

In the Maxmin $q$-CSP Reconfiguration problem, given a satisfiable $q$-CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the other by repeatedly changing the value assigned to a single variable. The objective is to find such a transformation that maximizes the minimum fraction of satisfied constraints along the transformation. In this paper, we prove that for any $q \geq 2$ and $\varepsilon > 0$, Maxmin $q$-CSP Reconfiguration is $\mathsf{PSPACE}$-hard to approximate within a factor of $\frac{1}{2^{q-1}}+\varepsilon$. To complement this hardness result, we prove that a $\bigl(\frac{1}{2^{q-1}}-\varepsilon\bigr)$-factor approximation for Maxmin $q$-CSP Reconfiguration is in $\mathsf{NP}$ in the perfect completeness case. These results establish the optimal $\mathsf{PSPACE}$-hardness of approximating Maxmin $q$-CSP Reconfiguration for every $q \geq 2$ under $\mathsf{NP} \neq \mathsf{PSPACE}$.

Figures

Figures reproduced from arXiv: 2607.28099 by the authors.

Figure 1
Figure 1. Illustration of the query sequence of the [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

297 extracted references · 5 canonical work pages

  1. [1]

    Exponential Bounds for

    Achlioptas, Dimitris and Beame, Paul and Molloy, Michael , Booktitle =. Exponential Bounds for. 2004 , Pages =

    2004

  2. [2]

    Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

    Algorithmic Barriers from Phase Transitions , Author =. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

  3. [3]

    Random Structures & Algorithms , Year =

    On the Solution-Space Geometry of Random Constraint Satisfaction Problems , Author =. Random Structures & Algorithms , Year =

  4. [4]

    On Approximation Algorithms for Hierarchical

    Agarwal, Sameet and Condon, Anne , Journal =. On Approximation Algorithms for Hierarchical. 1998 , Number =

    1998

  5. [5]

    Algorithmica , Year =

    Flip Distances Between Graph Orientations , Author =. Algorithmica , Year =

  6. [6]

    Proceedings of the European Symposium on Algorithms (ESA) , Year =

    Hardness of Token Swapping on Trees , Author =. Proceedings of the European Symposium on Algorithms (ESA) , Year =

  7. [7]

    Deterministic Simulation in

    Ajtai, Mikl\'. Deterministic Simulation in. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  8. [8]

    Combinatorica , Year =

    Explicit Expanders of Every Degree and Size , Author =. Combinatorica , Year =

Show all 297 references
  1. [9]

    Discrete Mathematics , Year =

    Explicit construction of linear sized tolerant networks , Author =. Discrete Mathematics , Year =

  2. [10]

    Computational Complexity , Year =

    Derandomized graph products , Author =. Computational Complexity , Year =

  3. [11]

    2016 , Series =

    The Probabilistic Method , Author =. 2016 , Series =

    2016

  4. [12]

    Proceedings of the Conference on Computational Complexity (CCC) , Year =

    Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs , Author =. Proceedings of the Conference on Computational Complexity (CCC) , Year =

  5. [13]

    Journal of Computer and System Sciences , Year =

    The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations , Author =. Journal of Computer and System Sciences , Year =

  6. [14]

    2009 , Doi =

    Computational Complexity: A Modern Approach , Author =. 2009 , Doi =

    2009

  7. [15]

    Journal of the ACM , Year =

    Proof Verification and the Hardness of Approximation Problems , Author =. Journal of the ACM , Year =

  8. [16]

    Probabilistic Checking of Proofs: A New Characterization of

    Arora, Sanjeev and Safra, Shmuel , Journal =. Probabilistic Checking of Proofs: A New Characterization of. 1998 , Number =

    1998

  9. [17]

    Combinatorica , Year =

    Improved Low-Degree Testing and its Applications , Author =. Combinatorica , Year =

  10. [18]

    Balanced

    Austrin, Per , Booktitle =. Balanced. 2007 , Pages =

    2007

  11. [19]

    Theory of Computing , Year =

    Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs , Author =. Theory of Computing , Year =

  12. [20]

    Austrin, Per and O'Donnell, Ryan and Tan, Li. New. ACM Transactions on Computation Theory , Year =

  13. [21]

    Computational Complexity , Year =

    Non-Deterministic Exponential Time has Two-Prover Interactive Protocols , Author =. Computational Complexity , Year =

  14. [22]

    Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

    Constant Degree Direct Product Testers with Small Soundness , Author =. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

  15. [23]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    Characterizing Direct Product Testing via Coboundary Expansion , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  16. [24]

    Quasi-Linear Size

    Bafna, Mitali and Minzer, Dor and Vyas, Nikhil and Yun, Zhiwei , Booktitle =. Quasi-Linear Size. 2025 , Pages =

    2025

  17. [25]

    Journal of Computer and System Sciences , Year =

    Galactic Token Sliding , Author =. Journal of Computer and System Sciences , Year =

  18. [26]

    IEEE Transactions on Information Theory , Year =

    Linearity testing in characteristic two , Author =. IEEE Transactions on Information Theory , Year =

  19. [27]

    Free Bits,

    Bellare, Mihir and Goldreich, Oded and Sudan, Madhu , Journal =. Free Bits,. 1998 , Number =

    1998

  20. [28]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    Improved non-approximability results , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  21. [29]

    Theory of Computing Systems , Year =

    Token Sliding on Split Graphs , Author =. Theory of Computing Systems , Year =

  22. [30]

    Ben. Robust. SIAM Journal on Computing , Year =

  23. [31]

    Randomness-efficient low degree tests and short

    Ben. Randomness-efficient low degree tests and short. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  24. [32]

    SIAM Journal on Computing , Year =

    Time/Space Trade-Offs for Reversible Computation , Author =. SIAM Journal on Computing , Year =

  25. [33]

    Stochastic Processes and their Applications , Year =

    Percolation and the hard-core lattice gas model , Author =. Stochastic Processes and their Applications , Year =

  26. [34]

    Discrete Applied Mathematics , Year =

    Independent-set reconfiguration thresholds of hereditary graph classes , Author =. Discrete Applied Mathematics , Year =

  27. [35]

    Rigid Matrices From Rectangular

    Bhangale, Amey and Harsha, Prahladh and Paradise, Orr and Tal, Avishay , Booktitle =. Rigid Matrices From Rectangular. 2020 , Pages =

    2020

  28. [36]

    2022 , Number =

    Bhangale, Amey and Khot, Subhash , Journal =. 2022 , Number =

    2022

  29. [37]

    Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA) , Year =

    Decremental optimization of dominating sets under the reconfiguration framework , Author =. Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA) , Year =

  30. [38]

    Journal of Computer and System Sciences , Year =

    Self-testing/correcting with applications to numerical problems , Author =. Journal of Computer and System Sciences , Year =

  31. [39]

    and Groenland, Carla and Nederlof, Jesper and Swennenhuis, C\'

    Bodlaender, Hans L. and Groenland, Carla and Nederlof, Jesper and Swennenhuis, C\'. Parameterized Problems Complete for Nondeterministic. Information and Computation , Year =. doi:10.1016/j.ic.2024.105195 , Eid =

    2024

  32. [40]

    Algorithmica , Year =

    Parameterized Complexities of Dominating and Independent Set Reconfiguration , Author =. Algorithmica , Year =. doi:10.1007/S00453-026-01381-9 , Eid =

    doi

  33. [41]

    Electronic Colloquium on Computational Complexity , Year =

    Gap Amplification Fails Below 1/2 , Author =. Electronic Colloquium on Computational Complexity , Year =

  34. [42]

    Computing Research Repository , Year =

    Reconfiguring independent sets in cographs , Author =. Computing Research Repository , Year =. 1406.1433 , Eprinttype =

    arXiv

  35. [43]

    Electronic Notes in Discrete Mathematics , Year =

    Recoloring bounded treewidth graphs , Author =. Electronic Notes in Discrete Mathematics , Year =

  36. [44]

    Shortest Reconfiguration of Colorings Under

    Bonamy, Marthe and Heinrich, Marc and Ito, Takehiro and Kobayashi, Yusuke and Mizuta, Haruka and M\". Shortest Reconfiguration of Colorings Under. Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS) , Year =

  37. [45]

    Journal of Combinatorial Optimization , Year =

    Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs , Author =. Journal of Combinatorial Optimization , Year =

  38. [46]

    Electronic Notes in Discrete Mathematics , Year =

    On the diameter of reconfiguration graphs for vertex colourings , Author =. Electronic Notes in Discrete Mathematics , Year =

  39. [47]

    Algorithmica , Year =

    Complexity of Token Swapping and Its Variants , Author =. Algorithmica , Year =

  40. [48]

    Journal of Graph Theory , Year =

    Independent Set Reconfiguration in Cographs and Their Generalizations , Author =. Journal of Graph Theory , Year =

  41. [49]

    Theoretical Computer Science , Year =

    The Complexity of Rerouting Shortest Paths , Author =. Theoretical Computer Science , Year =

  42. [50]

    Finding paths between graph colourings:

    Bonsma, Paul and Cereceda, Luis , Journal =. Finding paths between graph colourings:. 2009 , Number =

    2009

  43. [51]

    Proceedings of the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) , Year =

    Reconfiguring Independent Sets in Claw-Free Graphs , Author =. Proceedings of the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) , Year =

  44. [52]

    and Nishimura, Naomi and Raman, Venkatesh , Booktitle =

    Bonsma, Paul and Mouawad, Amer E. and Nishimura, Naomi and Raman, Venkatesh , Booktitle =. The Complexity of Bounded Length Graph Recoloring and. 2014 , Pages =

    2014

  45. [53]

    Computing Research Repository , Year =

    A Note on the Complexity of Graph Recoloring , Author =. Computing Research Repository , Year =. 2401.03011 , Eprinttype =

    arXiv

  46. [54]

    Proceedings of the European Symposium on Algorithms (ESA) , Year =

    Linear Transformations Between Colorings in Chordal Graphs , Author =. Proceedings of the European Symposium on Algorithms (ESA) , Year =

  47. [55]

    The Electronic Journal of Combinatorics , Year =

    Extremal Independent Set Reconfiguration , Author =. The Electronic Journal of Combinatorics , Year =

  48. [56]

    Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG) , Year =

    Shortest Reconfiguration of Matchings , Author =. Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG) , Year =

  49. [57]

    Algorithmica , Year =

    Reconfiguration of Spanning Trees with Degree Constraints or Diameter Constraints , Author =. Algorithmica , Year =

  50. [58]

    Proceedings of the European Symposium on Algorithms (ESA) , Year =

    Reconfiguration of Spanning Trees with Many or Few Leaves , Author =. Proceedings of the European Symposium on Algorithms (ESA) , Year =

  51. [59]

    Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) , Year =

    Approximating Shortest Connected Graph Transformation for Trees , Author =. Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) , Year =

  52. [60]

    Proceedings of the International Workshop on Approximation and Online Algorithms (WAOA) , Year =

    Reconfiguration of Graphs with Connectivity Constraints , Author =. Proceedings of the International Workshop on Approximation and Online Algorithms (WAOA) , Year =

  53. [61]

    Computer Science Review , Year =

    A survey on the parameterized complexity of reconfiguration problems , Author =. Computer Science Review , Year =. doi:10.1016/j.cosrev.2024.100663 , Eid =

    2024

  54. [62]

    Tight approximability of

    Brakensiek, Joshua and Huang, Neng and Zwick, Uri , Booktitle =. Tight approximability of. 2024 , Pages =

    2024

  55. [63]

    Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , Year =

    New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling , Author =. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , Year =

  56. [64]

    Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS) , Year =

    Reconfiguring Independent Sets on Interval Graphs , Author =. Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS) , Year =

  57. [65]

    Theoretical Computer Science , Year =

    Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect , Author =. Theoretical Computer Science , Year =

  58. [66]

    Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS) , Year =

    Distributed Vertex Cover Reconfiguration , Author =. Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS) , Year =

  59. [67]

    2007 , Url =

    Mixing Graph Colourings , Author =. 2007 , Url =

    2007

  60. [68]

    Journal of Graph Theory , Year =

    Finding paths between 3-colorings , Author =. Journal of Graph Theory , Year =

  61. [69]

    European Journal of Combinatorics , Year =

    Mixing 3-colourings in bipartite graphs , Author =. European Journal of Combinatorics , Year =

  62. [70]

    Discrete Mathematics , Year =

    Connectedness of the graph of vertex-colourings , Author =. Discrete Mathematics , Year =

  63. [71]

    Hardness of Approximation in

    Chan, Siu Man and Lauria, Massimo and Nordstr\". Hardness of Approximation in. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

  64. [72]

    Journal of the ACM , Year =

    Approximation Resistance from Pairwise-Independent Subgroups , Author =. Journal of the ACM , Year =

  65. [73]

    Algorithmica , Year =

    Improved Approximation Algorithms for Label Cover Problems , Author =. Algorithmica , Year =

  66. [74]

    SIAM Journal on Discrete Mathematics , Year =

    Fast Sampling of Satisfying Assignments from Random k -SAT with Applications to Connectivity , Author =. SIAM Journal on Discrete Mathematics , Year =

  67. [75]

    From Algorithms to Connectivity and Back: Finding a Giant Component in Random

    Chen, Zongchen and Mani, Nitya and Moitra, Ankur , Booktitle =. From Algorithms to Connectivity and Back: Finding a Giant Component in Random. 2023 , Pages =

    2023

  68. [76]

    The Annals of Mathematical Statistics , Year =

    A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations , Author =. The Annals of Mathematical Statistics , Year =

  69. [77]

    On Parallel Repetition of

    Chiesa, Alessandro and Guan, Ziyi and Y. On Parallel Repetition of. Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS) , Year =

  70. [78]

    Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , Year =

    Approximation Algorithms for Label Cover and The Log-Density Threshold , Author =. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , Year =

  71. [79]

    Mathematics of Operations Research , Year =

    A Greedy Heuristic for the Set-Covering Problem , Author =. Mathematics of Operations Research , Year =

  72. [80]

    , Booktitle =

    Cohen, Michael B. , Booktitle =. 2016 , Pages =

    2016

  73. [81]

    Advances in Mathematics , Year =

    The asymptotic k -SAT threshold , Author =. Advances in Mathematics , Year =

  74. [82]

    Approximate Solutions to Problems in

    Condon, Anne , Journal =. Approximate Solutions to Problems in. 1995 , Number =

    1995

  75. [83]

    SIAM Journal on Computing , Year =

    Random Debaters and the Hardness of Approximating Stochastic Functions , Author =. SIAM Journal on Computing , Year =

  76. [84]

    , Journal =

    Condon, Anne and Feigenbaum, Joan and Lund, Carsten and Shor, Peter W. , Journal =. Probabilistically Checkable Debate Systems and Nonapproximability of. 1995 , Volume =

    1995

  77. [85]

    Proceedings of the IEEE Conference on Computational Complexity (CCC) , Year =

    A Short Guide to Approximation Preserving Reductions , Author =. Proceedings of the IEEE Conference on Computational Complexity (CCC) , Year =

  78. [86]

    Theory of Computing Systems , Year =

    On Approximation Scheme Preserving Reducibility and Its Applications , Author =. Theory of Computing Systems , Year =

  79. [87]

    2015 , Doi =

    Parameterized Algorithms , Author =. 2015 , Doi =

    2015

  80. [88]

    SIAM Journal on Computing , Year =

    Direct Sum Testing , Author =. SIAM Journal on Computing , Year =

  81. [89]

    Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , Year =

    Adaptivity and Approximation for Stochastic Packing Problems , Author =. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , Year =

  82. [90]

    Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

    Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity , Author =. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

  83. [91]

    DeHaan, Ian and Pashkovich, Kanstantsin , Booktitle =. Matroid. 2024 , Pages =

    2024

  84. [92]

    Theoretical Computer Science , Year =

    Linear-Time Algorithm for Sliding Tokens on Trees , Author =. Theoretical Computer Science , Year =

  85. [93]

    Proceedings of the International Symposium on Algorithms and Data Structures (WADS) , Year =

    Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs , Author =. Proceedings of the International Symposium on Algorithms and Data Structures (WADS) , Year =

  86. [94]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  87. [95]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    Swap Cosystolic Expansion , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  88. [96]

    Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

    Agreement Testing Theorems on Layered Set Systems , Author =. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

  89. [97]

    Low Acceptance Agreement Tests via Bounded-Degree Symplectic

    Dikstein, Yotam and Dinur, Irit and Lubotzky, Alexander , Booktitle =. Low Acceptance Agreement Tests via Bounded-Degree Symplectic. 2024 , Pages =

    2024

  90. [98]

    Annals of Mathematics , Year =

    Proof of the satisfiability conjecture for large k , Author =. Annals of Mathematics , Year =

  91. [99]

    Dinur, Irit , Journal =. The. 2007 , Number =. doi:10.1145/1236457.1236459 , Eid =

    2007

  92. [100]

    Proceedings of the Annual IEEE Symposium on Foundations of Computer Science , Year =

    Locally Testing Direct Product in the Low Error Range , Author =. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science , Year =

  93. [101]

    Direct Sum Testing: The General Case , Author =. Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the International Workshop on Randomization and Computation (RANDOM) , Year =

  94. [102]

    Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

    High Dimensional Expanders Imply Agreement Expanders , Author =. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , Year =

  95. [103]

    Exponentially Small Soundness for the Direct Product

    Dinur, Irit and Livni Navon, Inbal , Journal =. Exponentially Small Soundness for the Direct Product. 2023 , Number =

    2023

  96. [104]

    Derandomized Parallel Repetition via Structured

    Dinur, Irit and Meir, Or , Journal =. Derandomized Parallel Repetition via Structured. 2011 , Number =

    2011

  97. [105]

    Assignment Testers: Towards a Combinatorial Proof of the

    Dinur, Irit and Reingold, Omer , Journal =. Assignment Testers: Towards a Combinatorial Proof of the. 2006 , Number =

    2006

  98. [106]

    Annals of Mathematics , Year =

    On the hardness of approximating vertex cover , Author =. Annals of Mathematics , Year =

  99. [107]

    Information Processing Letters , Year =

    On the hardness of approximating label-cover , Author =. Information Processing Letters , Year =

  100. [108]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    Analytical Approach to Parallel Repetition , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  101. [109]

    Proceedings of the IEEE Conference on Computational Complexity (CCC) , Year =

    Direct Product Testing , Author =. Proceedings of the IEEE Conference on Computational Complexity (CCC) , Year =

  102. [110]

    The problem of uniqueness of a

    Dobrushin, Roland L'vovich , Journal =. The problem of uniqueness of a. 1968 , Number =

    1968

  103. [111]

    Proceedings of the International Conference and Workshops on Algorithms and Computation (WALCOM) , Year =

    The Shortest Path Reconfiguration Problem Based on Relaxation of Reconfiguration Rules , Author =. Proceedings of the International Conference and Workshops on Algorithms and Computation (WALCOM) , Year =

  104. [112]

    2013 , Doi =

    Fundamentals of Parameterized Complexity , Author =. 2013 , Doi =

    2013

  105. [113]

    Random Structures & Algorithms , Year =

    Randomly coloring sparse random graphs with fewer colors than the maximum degree , Author =. Random Structures & Algorithms , Year =

  106. [114]

    Theory of Computing Systems , Year =

    The Hardness of Approximating Spanner Problems , Author =. Theory of Computing Systems , Year =

  107. [115]

    The Quarterly Journal of Mathematics , Year =

    Intersection theorems for systems of finite sets , Author =. The Quarterly Journal of Mathematics , Year =

  108. [116]

    SIAM Journal on Discrete Mathematics , Year =

    Approximating Maximum Clique by Removing Subgraphs , Author =. SIAM Journal on Discrete Mathematics , Year =

  109. [117]

    Journal of the ACM , Year =

    A Threshold of n for Approximating Set Cover , Author =. Journal of the ACM , Year =

  110. [118]

    Journal of the ACM , Year =

    Interactive Proofs and the Hardness of Approximating Cliques , Author =. Journal of the ACM , Year =

  111. [119]

    Journal of Computer and System Sciences , Year =

    Zero Knowledge and the Chromatic Number , Author =. Journal of Computer and System Sciences , Year =

  112. [120]

    SIAM Journal on Computing , Year =

    Maximizing Non-monotone Submodular Functions , Author =. SIAM Journal on Computing , Year =

  113. [121]

    2006 , Doi =

    Parameterized Complexity Theory , Author =. 2006 , Doi =

    2006

  114. [122]

    1965 , Url =

    Concatenated Codes , Author =. 1965 , Url =

    1965

  115. [123]

    Theoretical Computer Science , Year =

    On the Power of Multi-Prover Interactive Protocols , Author =. Theoretical Computer Science , Year =

  116. [124]

    and Jerrum, Mark , Journal =

    Frieze, Alan M. and Jerrum, Mark , Journal =. Improved Approximation Algorithms for. 1997 , Number =

    1997

  117. [125]

    Proceedings of the International Symposium on Algorithms and Computation (ISAAC) , Year =

    Algorithms for Coloring Reconfiguration Under Recolorability Digraphs , Author =. Proceedings of the International Symposium on Algorithms and Computation (ISAAC) , Year =

  118. [126]

    Journal of Computer and System Sciences , Year =

    Explicit Constructions of Linear-Sized Superconcentrators , Author =. Journal of Computer and System Sciences , Year =

  119. [127]

    Algorithmica , Year =

    Reconfiguring Shortest Paths in Graphs , Author =. Algorithmica , Year =

  120. [128]

    Information and Control , Year =

    Succinct Representations of Graphs , Author =. Information and Control , Year =

  121. [129]

    Proceedings of the National Academy of Sciences of the United States of America , Year =

    The Overlap Gap Property: A Topological Barrier to Optimizing over Random Structures , Author =. Proceedings of the National Academy of Sciences of the United States of America , Year =. doi:10.1073/pnas.2108492118 , Eid =

    doi

  122. [130]

    Finding a Large Submatrix of a

    Gamarnik, David and Li, Quan , Journal =. Finding a Large Submatrix of a. 2018 , Number =

    2018

  123. [131]

    Annals of Probability , Year =

    Limits of local algorithms over sparse random graphs , Author =. Annals of Probability , Year =

  124. [132]

    Garey, Michael. R. and Johnson, David S. and Stockmeyer, Larry J. , Journal =. Some Simplified. 1976 , Number =

    1976

  125. [133]

    Random Structures & Algorithms , Year =

    A tail bound for read- k families of functions , Author =. Random Structures & Algorithms , Year =

  126. [134]

    Algorithmica , Year =

    Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited , Author =. Algorithmica , Year =

  127. [135]

    Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs , Author =. Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the International Workshop on Randomization and Computation...

  128. [136]

    Journal of the ACM , Year =

    Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming , Author =. Journal of the ACM , Year =

  129. [137]

    A Combinatorial Consistency Lemma with Application to Proving the

    Goldreich, Oded and Safra, Shmuel , Journal =. A Combinatorial Consistency Lemma with Application to Proving the. 2000 , Number =

    2000

  130. [138]

    Locally testable codes and

    Goldreich, Oded and Sudan, Madhu , Journal =. Locally testable codes and. 2006 , Number =

    2006

  131. [139]

    and Maneva, Elitza and Papadimitriou, Christos H

    Gopalan, Parikshit and Kolaitis, Phokion G. and Maneva, Elitza and Papadimitriou, Christos H. , Journal =. The Connectivity of. 2009 , Number =

    2009

  132. [140]

    Course notes of 15-854(

    Gupta, Anupam and O'Donnell, Ryan , Year =. Course notes of 15-854(

  133. [141]

    Gur, Tom and Minzer, Dor and Weissenberg, Guy and Zheng, Kai Zhe , Booktitle =. 3-Query. 2026 , Pages =

    2026

  134. [142]

    2001 , Month =

    List Decoding of Error-Correcting Codes , Author =. 2001 , Month =

    2001

  135. [143]

    Computational Complexity , Year =

    Hardness Amplification via Space-Efficient Direct Products , Author =. Computational Complexity , Year =

  136. [144]

    On Inapproximability of Reconfiguration Problems:

    Guruswami, Venkatesan and. On Inapproximability of Reconfiguration Problems:. Computing Research Repository , Year =. 2312.17140v3 , Eprinttype =

  137. [145]

    Course notes of

    Guruswami, Venkatesan and O'Donnell, Ryan , Year =. Course notes of

  138. [146]

    2025 , Volume =

    Guruswami, Venkatesan and Ren, Xuandi and Wu, Kewen , Journal =. 2025 , Volume =. 2507.01192 , Eprinttype =

    2025 arXiv

  139. [147]

    2019 , Note =

    Essential Coding Theory , Author =. 2019 , Note =

    2019

  140. [148]

    Theory of Computing , Year =

    Improved Inapproximability Results for Maximum k -Colorable Subgraph , Author =. Theory of Computing , Year =

  141. [149]

    Reasoning in

    H. Reasoning in. Proceedings of the Conference on Learning Theory (COLT) , Year =

  142. [150]

    Journal of the ACM , Year =

    Some Optimal Inapproximability Results , Author =. Journal of the ACM , Year =

  143. [151]

    Clique is hard to approximate within n^

    H. Clique is hard to approximate within n^. Acta Mathematica , Year =

  144. [152]

    Theoretical Computer Science , Year =

    The Complexity of Dominating Set Reconfiguration , Author =. Theoretical Computer Science , Year =

  145. [153]

    Linear Algebra and its Applications , Year =

    Interlacing Eigenvalues and Graphs , Author =. Linear Algebra and its Applications , Year =

  146. [154]

    1979 , Doi =

    Eigenvalue techniques in design and graph theory , Author =. 1979 , Doi =

    1979

  147. [155]

    IEICE Transactions on Information and Systems , Year =

    The Coloring Reconfiguration Problem on Specific Graph Classes , Author =. IEICE Transactions on Information and Systems , Year =

  148. [156]

    Computing Research Repository , Year =

    Complexity of Reconfiguration Problems for Constraint Satisfaction , Author =. Computing Research Repository , Year =. 1812.10629 , Eprinttype =

    arXiv

  149. [157]

    Games, Puzzles, and Computation , Author =

  150. [158]

    and Demaine, Erik D

    Hearn, Robert A. and Demaine, Erik D. , Journal =. 2005 , Number =

    2005

  151. [159]

    Journal of Computational Biology , Year =

    Sorting by short swaps , Author =. Journal of Computational Biology , Year =

  152. [160]

    Surveys in Combinatorics 2013 , Publisher =

    The Complexity of Change , Author =. Surveys in Combinatorics 2013 , Publisher =. 2013 , Pages =

    2013

  153. [161]

    The Computer Journal , Year =

    Incomplete Distinguishing Sequences for Finite State Machines , Author =. The Computer Journal , Year =

  154. [162]

    Hirahara, Shuichi and Ohsaka, Naoto , Note =. Optimal

  155. [163]

    Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , Year =

    Asymptotically Optimal Inapproximability of Maxmin k -Cut Reconfiguration , Author =. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , Year =

  156. [164]

    Asymptotically Optimal Inapproximability of

    Hirahara, Shuichi and Ohsaka, Naoto , Booktitle =. Asymptotically Optimal Inapproximability of. 2025 , Pages =

    2025

  157. [165]

    Hirahara, Shuichi and Ohsaka, Naoto , Booktitle =. Optimal. 2024 , Pages =

    2024

  158. [166]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  159. [167]

    Proceedings of the International Symposium on Algorithms and Computation (ISAAC) , Year =

    Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules , Author =. Proceedings of the International Symposium on Algorithms and Computation (ISAAC) , Year =

  160. [168]

    , Year =

    Hoang, Duc A. , Year =

  161. [169]

    Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , Year =

    On (In)approximability of MaxMin Independent Set Reconfiguration , Author =. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , Year =

  162. [170]

    Journal of the American Statistical Association , Year =

    Probability Inequalities for Sums of Bounded Random Variables , Author =. Journal of the American Statistical Association , Year =

  163. [171]

    Bulletin of the American Mathematical Society , Year =

    Expander graphs and their applications , Author =. Bulletin of the American Mathematical Society , Year =

  164. [172]

    and Schwartz, Jacob Theodore and Sharir, Micha , Journal =

    Hopcroft, John E. and Schwartz, Jacob Theodore and Sharir, Micha , Journal =. On the Complexity of Motion Planning for Multiple Independent Objects. 1984 , Number =

    1984

  165. [173]

    Theory of Computing , Year =

    Approximation Resistance on Satisfiable Instances for Sparse Predicates , Author =. Theory of Computing , Year =

  166. [174]

    and Marathe, Madhav V

    Hunt, III, Harry B. and Marathe, Madhav V. and Radhakrishnan, Venkatesh and Ravi, S. S. and Rosenkrantz, Daniel J. and Stearns, Richard E. , Journal =. 1998 , Number =

    1998

  167. [175]

    and Marathe, Madhav V

    Hunt, III, Harry B. and Marathe, Madhav V. and Stearns, Richard E. , Booktitle =. On the Efficient Approximability of ``. 2000 , Editor =

    2000

  168. [176]

    Electronic Notes in Discrete Mathematics , Year =

    Complexity and Approximability of Quantified and Stochastic Constraint Satisfaction Problems , Author =. Electronic Notes in Discrete Mathematics , Year =

  169. [177]

    New Direct-Product Testers and 2-Query

    Impagliazzo, Russell and Kabanets, Valentine and Wigderson, Avi , Journal =. New Direct-Product Testers and 2-Query. 2012 , Number =

    2012

  170. [178]

    Journal of Computer and System Sciences , Year =

    Randomness vs Time: Derandomization under a Uniform Assumption , Author =. Journal of Computer and System Sciences , Year =

  171. [179]

    Journal of Combinatorial Optimization , Year =

    Approximability of the subset sum reconfiguration problem , Author =. Journal of Combinatorial Optimization , Year =

  172. [180]

    Theoretical Computer Science , Year =

    On the Complexity of Reconfiguration Problems , Author =. Theoretical Computer Science , Year =

  173. [181]

    Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS) , Year =

    Independent Set Reconfiguration on Directed Graphs , Author =. Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS) , Year =

  174. [182]

    SIAM Journal on Discrete Mathematics , Year =

    Shortest Reconfiguration of Perfect Matchings via Alternating Cycles , Author =. SIAM Journal on Discrete Mathematics , Year =

  175. [183]

    Discrete Applied Mathematics , Year =

    Reconfiguration of list edge-colorings in a graph , Author =. Discrete Applied Mathematics , Year =

  176. [184]

    Journal of Combinatorial Optimization , Year =

    Incremental optimization of independent sets under the reconfiguration framework , Author =. Journal of Combinatorial Optimization , Year =

  177. [185]

    IEICE Transactions on Information and Systems , Year =

    Reconfiguration of Vertex Covers in a Graph , Author =. IEICE Transactions on Information and Systems , Year =

  178. [186]

    Theoretical Computer Science , Year =

    Reconfiguration of Colorable Sets in Classes of Perfect Graphs , Author =. Theoretical Computer Science , Year =

  179. [187]

    Proceedings of the International Workshop on Modelling and Reformulating Constraint Satisfaction Problems , Year =

    A Compact Reformulation of Propositional Satisfiability as Binary Constraint Satisfaction , Author =. Proceedings of the International Workshop on Modelling and Reformulating Constraint Satisfaction Problems , Year =

  180. [188]

    Random Structures & Algorithms , Year =

    A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph , Author =. Random Structures & Algorithms , Year =

  181. [189]

    The Annals of Probability , Year =

    On a Set of Almost Deterministic k -Independent Random Variables , Author =. The Annals of Probability , Year =

  182. [190]

    Journal of Computer and System Sciences , Year =

    Approximation algorithms for combinatorial problems , Author =. Journal of Computer and System Sciences , Year =

  183. [191]

    Algorithmica , Year =

    Finding Shortest Paths Between Graph Colourings , Author =. Algorithmica , Year =

  184. [192]

    Discrete Mathematics , Year =

    Upper bounds for constant weight error correcting codes , Author =. Discrete Mathematics , Year =

  185. [193]

    IRE Transactions on Information Theory , Year =

    A new upper bound for error-correcting codes , Author =. IRE Transactions on Information Theory , Year =

  186. [194]

    American Journal of Mathematics , Year =

    Notes on the ``15'' puzzle , Author =. American Journal of Mathematics , Year =

  187. [195]

    Strong bounds on the approximability of two

    Jonsson, Peter , Journal =. Strong bounds on the approximability of two. 1999 , Number =

    1999

  188. [196]

    Information processing letters , Year =

    A Nonapproximability Result for Finite Function Generation , Author =. Information processing letters , Year =

  189. [197]

    Journal of Combinatorial Theory, Series B , Year =

    Partitions of graphs with high minimum degree or connectivity , Author =. Journal of Combinatorial Theory, Series B , Year =

  190. [198]

    Proceedings of the International Conference and Workshops on Algorithms and Computation (WALCOM) , Year =

    Reconfiguration Using Generalized Token Jumping , Author =. Proceedings of the International Conference and Workshops on Algorithms and Computation (WALCOM) , Year =

  191. [199]

    Theoretical Computer Science , Year =

    Complexity of Independent Set Reconfigurability Problems , Author =. Theoretical Computer Science , Year =

  192. [200]

    Theoretical Computer Science , Year =

    Shortest Paths Between Shortest Paths , Author =. Theoretical Computer Science , Year =

  193. [201]

    On the Hardness of Approximating

    Kann, Viggo and Khanna, Sanjeev and Lagergren, Jens and Panconesi, Alessandro , Journal =. On the Hardness of Approximating. 1997 , Volume =

    1997

  194. [202]

    Complexity of Computer Computations , Year =

    Reducibility Among Combinatorial Problems , Author =. Complexity of Computer Computations , Year =

  195. [203]

    Electronic Colloquium on Computational Complexity , Year =

    On Inapproximability of Reconfiguration Problems:. Electronic Colloquium on Computational Complexity , Year =

  196. [204]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    Coboundary Expansion of Coset Complexes , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  197. [205]

    Combinatorica , Year =

    On the hardness of approximating the chromatic number , Author =. Combinatorica , Year =

  198. [206]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    On the Power of Unique 2-Prover 1-Round Games , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  199. [207]

    Optimal Inapproximability Results for

    Khot, Subhash and Kindler, Guy and Mossel, Elchanan and O'Donnell, Ryan , Journal =. Optimal Inapproximability Results for. 2007 , Number =

    2007

  200. [208]

    Theoretical Computer Science , Year =

    Trichotomy for the reconfiguration problem of integer linear systems , Author =. Theoretical Computer Science , Year =

  201. [209]

    Algorithmica , Year =

    On the Hardness of Approximating Spanners , Author =. Algorithmica , Year =

  202. [210]

    Improved Rounding Techniques for the

    Lewin, Michael and Livnat, Dror and Zwick, Uri , Booktitle =. Improved Rounding Techniques for the. 2002 , Pages =

    2002

  203. [211]

    Theoretical Computer Science , Year =

    Optimization Complexity of Linear Logic Proof Games , Author =. Theoretical Computer Science , Year =

  204. [212]

    Bulletin of Symbolic Logic , Year =

    Linear logic proof games and optimization , Author =. Bulletin of Symbolic Logic , Year =

  205. [213]

    ACM Transactions on Algorithms , Year =

    The Complexity of Independent Set Reconfiguration on Bipartite Graphs , Author =. ACM Transactions on Algorithms , Year =

  206. [214]

    Discrete Mathematics , Year =

    On the ratio of optimal integral and fractional covers , Author =. Discrete Mathematics , Year =

  207. [215]

    Proceedings of the Southeastern Conference on Combinatorics, Graph Theory, and Computing , Year =

    Coverings and coloring of hypergraphs , Author =. Proceedings of the Southeastern Conference on Combinatorics, Graph Theory, and Computing , Year =

  208. [216]

    1988 , Number =

    Lubotzky, Alexander and Phillips, Ralph and Sarnak, Peter , Journal =. 1988 , Number =

    1988

  209. [217]

    Journal of the ACM , Year =

    Algebraic Methods for Interactive Proof Systems , Author =. Journal of the ACM , Year =

  210. [218]

    Journal of the ACM , Year =

    On the Hardness of Approximating Minimization Problems , Author =. Journal of the ACM , Year =

  211. [219]

    Physical Review Letters , Year =

    Clustering of Solutions in the Random Satisfiability Problem , Author =. Physical Review Letters , Year =. doi:10.1103/PhysRevLett.94.197205 , Eid =

    doi

  212. [220]

    Science , Year =

    Analytic and Algorithmic Solution of Random Satisfiability Problems , Author =. Science , Year =

  213. [221]

    An Exact Algorithm for The

    Makino, Kazuhisa and Tamaki, Suguru and Yamamoto, Masaki , Journal =. An Exact Algorithm for The. 2011 , Number =

    2011

  214. [222]

    Makino, Kazuhisa and Tamaki, Suguru and Yamamoto, Masaki , Journal =. On the. 2010 , Number =

    2010

  215. [223]

    Algorithmica , Year =

    Improved Approximation Algorithms for Projection Games , Author =. Algorithmica , Year =

  216. [224]

    and Hunt, III, Harry B

    Marathe, Madhav V. and Hunt, III, Harry B. and Ravi, S. S. , Journal =. The Complexity of Approximating. 1994 , Number =

    1994

  217. [225]

    and Hunt, III, Harry B

    Marathe, Madhav V. and Hunt, III, Harry B. and Stearns, Richard E. and Radhakrishnan, Venkatesh , Journal =. Approximation Algorithms for. 1998 , Number =

    1998

  218. [226]

    and Spielman, Daniel A

    Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil , Journal =. Interlacing families. 2018 , Number =

    2018

  219. [227]

    and Spielman, Daniel A

    Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil , Journal =. Interlacing families. 2015 , Pages =

    2015

  220. [228]

    Journal of Computer and System Sciences , Year =

    Completely inapproximable monotone and antimonotone parameterized problems , Author =. Journal of Computer and System Sciences , Year =

  221. [229]

    Surveys in Combinatorics, 1989 , Publisher =

    On the method of bounded differences , Author =. Surveys in Combinatorics, 1989 , Publisher =. 1989 , Pages =

    1989

  222. [230]

    2013 , Number =

    Meir, Or , Journal =. 2013 , Number =

    2013

  223. [231]

    Proceedings of the European Symposium on Algorithms (ESA) , Year =

    Approximation and Hardness of Token Swapping , Author =. Proceedings of the European Symposium on Algorithms (ESA) , Year =

  224. [232]

    Computing Research Repository , Year =

    Near Optimal Hardness of Approximating k -CSP , Author =. Computing Research Repository , Year =. 2510.23991 , Eprinttype =

  225. [233]

    Near Optimal Alphabet-Soundness Tradeoff

    Minzer, Dor and Zheng, Kai Zhe , Booktitle =. Near Optimal Alphabet-Soundness Tradeoff. 2024 , Pages =

    2024

  226. [234]

    Explicit Near-

    Mohanty, Sidhanth and O'Donnell, Ryan and Paredes, Pedro , Journal =. Explicit Near-. 2021 , Number =

    2021

  227. [235]

    Journal of Combinatorial Theory, Series B , Year =

    Face Covers and the Genus Problem for Apex Graphs , Author =. Journal of Combinatorial Theory, Series B , Year =

  228. [236]

    Molloy, Michael , Journal =. The. 2004 , Number =

    2004

  229. [237]

    Annals of Mathematics , Year =

    Noise stability of functions with low influences: Invariance and optimality , Author =. Annals of Mathematics , Year =

  230. [238]

    2015 , Url =

    On Reconfiguration Problems: Structure and Tractability , Author =. 2015 , Url =

    2015

  231. [239]

    and Nishimura, Naomi and Pathak, Vinayak and Raman, Venkatesh , Journal =

    Mouawad, Amer E. and Nishimura, Naomi and Pathak, Vinayak and Raman, Venkatesh , Journal =. Shortest Reconfiguration Paths in the Solution Space of. 2017 , Number =

    2017

  232. [240]

    Algorithms , Year =

    Vertex Cover Reconfiguration and Beyond , Author =. Algorithms , Year =. doi:10.3390/a11020020 , Eid =

    doi

  233. [241]

    Algorithmica , Year =

    On the Parameterized Complexity of Reconfiguration Problems , Author =. Algorithmica , Year =

  234. [242]

    Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC) , Year =

    Reconfiguration over Tree Decompositions , Author =. Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC) , Year =

  235. [243]

    , Journal =

    Muller, David E. , Journal =. Application of. 1954 , Number =

    1954

  236. [244]

    50 years of Combinatorics, Graph Theory, and Computing , Publisher =

    Reconfiguration of Colourings and Dominating Sets in Graphs , Author =. 50 years of Combinatorics, Graph Theory, and Computing , Publisher =. 2019 , Chapter =

    2019

  237. [245]

    Algorithms , Year =

    Introduction to Reconfiguration , Author =. Algorithms , Year =. doi:10.3390/a11040052 , Eid =

    doi

  238. [246]

    Logical Methods in Computer Science , Year =

    Pebble Games, Proof Complexity, and Time-Space Trade-offs , Author =. Logical Methods in Computer Science , Year =

  239. [247]

    Information Processing Letters , Year =

    On Approximate Reconfigurability of Label Cover , Author =. Information Processing Letters , Year =. doi:10.1016/j.ipl.2024.106556 , Eid =

    2024

  240. [248]

    Yet Another Simple Proof of the

    Ohsaka, Naoto , Booktitle =. Yet Another Simple Proof of the. 2025 , Pages =

    2025

  241. [249]

    Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , Year =

    Alphabet Reduction for Reconfiguration Problems , Author =. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , Year =

  242. [250]

    Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , Year =

    Gap Amplification for Reconfiguration Problems , Author =. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , Year =

  243. [251]

    Computing Research Repository , Year =

    Tight Inapproximability of Target Set Reconfiguration , Author =. Computing Research Repository , Year =. 2402.15076 , Eprinttype =

    arXiv

  244. [252]

    Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS) , Year =

    Gap Preserving Reductions Between Reconfiguration Problems , Author =. Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS) , Year =

  245. [253]

    Proceedings of the ACM International Conference on Web Search and Data Mining (WSDM) , Year =

    Reconfiguration Problems on Submodular Functions , Author =. Proceedings of the ACM International Conference on Web Search and Data Mining (WSDM) , Year =

  246. [254]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    The Complexity of Dynamic Languages and Dynamic Optimization Problems , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  247. [255]

    Journal of Computer and System Sciences , Year =

    On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence , Author =. Journal of Computer and System Sciences , Year =

  248. [256]

    Journal of Computer and System Sciences , Year =

    Games Against Nature , Author =. Journal of Computer and System Sciences , Year =

  249. [257]

    Mathematics of Operations Research , Year =

    Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities , Author =. Mathematics of Operations Research , Year =

  250. [258]

    Journal of Computer and System Sciences , Year =

    Optimization, Approximation, and Complexity Classes , Author =. Journal of Computer and System Sciences , Year =

  251. [259]

    Information and Control , Year =

    A Note on Succinct Representations of Graphs , Author =. Information and Control , Year =

  252. [260]

    Smooth and Strong

    Paradise, Orr , Journal =. Smooth and Strong. 2021 , Number =. doi:10.1007/s00037-020-00199-3 , Eid =

    2021 doi

  253. [261]

    Record of the Project MAC Conference on Concurrent Systems and Parallel Computation , Year =

    Comparative Schematology , Author =. Record of the Project MAC Conference on Concurrent Systems and Parallel Computation , Year =

  254. [262]

    Theoretical Computer Science , Year =

    Non Deterministic Polynomial Optimization Problems and Their Approximations , Author =. Theoretical Computer Science , Year =

  255. [263]

    Approximation algorithms for the Label-Cover

    Peleg, David , Journal =. Approximation algorithms for the Label-Cover. 2007 , Number =

    2007

  256. [264]

    Computational Complexity , Year =

    The Hardness of Approximation: Gap Location , Author =. Computational Complexity , Year =

  257. [265]

    IRE Transactions on Information Theory , Year =

    Binary codes with specified minimum distance , Author =. IRE Transactions on Information Theory , Year =

  258. [266]

    Gap Amplification in

    Radhakrishnan, Jaikumar , Booktitle =. Gap Amplification in. 2006 , Pages =

    2006

  259. [267]

    Radhakrishnan, Jaikumar and Sudan, Madhu , Journal =. On. 2007 , Number =

    2007

  260. [268]

    Gap Amplification for Small-Set Expansion via Random Walks , Author =. Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the International Workshop on Randomization and Computation (RANDOM) , Year =

  261. [269]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    Graph Expansion and the Unique Games Conjecture , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  262. [270]

    SIAM Journal on Computing , Year =

    A Parallel Repetition Theorem , Author =. SIAM Journal on Computing , Year =

  263. [271]

    A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability

    Raz, Ran and Safra, Shmuel , Booktitle =. A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability. 1997 , Pages =

    1997

  264. [272]

    Transactions of the IRE Professional Group on Information Theory , Year =

    A class of multiple-error-correcting codes and the decoding scheme , Author =. Transactions of the IRE Professional Group on Information Theory , Year =

  265. [273]

    Journal of the Society for Industrial and Applied Mathematics , Year =

    Polynomial Codes Over Certain Finite Fields , Author =. Journal of the Society for Industrial and Applied Mathematics , Year =

  266. [274]

    Annals of Mathematics , Year =

    Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders , Author =. Annals of Mathematics , Year =

  267. [275]

    Journal of Computer and System Sciences , Year =

    Relationships between nondeterministic and deterministic tape complexities , Author =. Journal of Computer and System Sciences , Year =

  268. [276]

    Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

    The complexity of satisfiability problems , Author =. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Year =

  269. [277]

    , Journal =

    Schwerdtfeger, Konrad W. , Journal =. A Computational Trichotomy for Connectivity of. 2012 , Number =

    2012

  270. [278]

    1992 , Number =

    Shamir, Adi , Journal =. 1992 , Number =

    1992

  271. [279]

    2012 , Edition =

    Introduction to the Theory of Computation , Author =. 2012 , Edition =

    2012

  272. [280]

    Information and Computation , Year =

    The Problem of Space Invariance for Sequential Machines , Author =. Information and Computation , Year =

  273. [281]

    Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS) , Year =

    A Generalized Matching Reconfiguration Problem , Author =. Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS) , Year =

  274. [282]

    On regularity of

    Stankovi\'. On regularity of. Information Processing Letters , Year =. doi:10.1016/j.ipl.2022.106244 , Eid =

    2022

  275. [283]

    Proceedings of the Symposium on Switching Circuit Theory and Logical Design (SWCT) , Year =

    Hierarchies of memory limited computations , Author =. Proceedings of the Symposium on Switching Circuit Theory and Logical Design (SWCT) , Year =

  276. [284]

    ACM SIGACT News , Year =

    Planar 3-colorability is polynomial complete , Author =. ACM SIGACT News , Year =

  277. [285]

    Proceedings of the International Conference and Workshops on Algorithms and Computation (WALCOM) , Year =

    Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules , Author =. Proceedings of the International Conference and Workshops on Algorithms and Computation (WALCOM) , Year =

  278. [286]

    Journal of Combinatorial Optimization , Year =

    Reconfiguration of dominating sets , Author =. Journal of Combinatorial Optimization , Year =

  279. [287]

    Algorithms , Year =

    Complexity of Hamiltonian Cycle Reconfiguration , Author =. Algorithms , Year =. doi:10.3390/a11090140 , Eid =

    doi

  280. [288]

    Computational Complexity , Year =

    Pseudorandomness and Average-Case Complexity via Uniform Reductions , Author =. Computational Complexity , Year =

  281. [289]

    Foundations and Trends in Theoretical Computer Science , Year =

    Pseudorandomness , Author =. Foundations and Trends in Theoretical Computer Science , Year =

  282. [290]

    Parameterized Inapproximability for

    W. Parameterized Inapproximability for. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , Year =

  283. [291]

    Mathematical Statistics and Learning , Year =

    Optimal low-degree hardness of maximum independent set , Author =. Mathematical Statistics and Learning , Year =

  284. [292]

    Journal of Computer and System Sciences , Year =

    Reconfiguration in Bounded Bandwidth and Tree-depth , Author =. Journal of Computer and System Sciences , Year =

  285. [293]

    Theoretical Computer Science , Year =

    Swapping labeled tokens on graphs , Author =. Theoretical Computer Science , Year =

  286. [294]

    International Journal of Computer Mathematics: Computer Systems Theory , Year =

    Decremental optimization of vertex-colouring under the reconfiguration framework , Author =. International Journal of Computer Mathematics: Computer Systems Theory , Year =

  287. [295]

    Proceedings of the Symposium on Foundations of Computer Science (SFCS) , Year =

    Theory and Applications of Trapdoor Functions (Extended Abstract) , Author =. Proceedings of the Symposium on Foundations of Computer Science (SFCS) , Year =

  288. [296]

    Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , Year =

    A Parallel Repetition Theorem for All Entangled Games , Author =. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , Year =

  289. [297]

    Theory of Computing , Year =

    Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number , Author =. Theory of Computing , Year =

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.