mlsanityData to 14 Oct 2026

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)

arXiv 2411.10453 ↗First posted 31 Oct 2024cs.CC cs.AI cs.DMcited by 0

Not on the map. Why?

Abstract (arXiv)

Motivated by phase transitions in combinatorial optimization problems, we define two kinds of geometry-preserving reductions between constraint satisfaction problems and other NP-search problems. We give a couple of examples and counterexamples for these reductions.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 2 of its 50 references that are in the map. First posted on arXiv 31 Oct 2024.

Builds on

2 of 50 references.

References · 2

  1. 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
  2. 2023Local consistency as a reduction between constraint satisfaction problemscited by 1

Built on by

Not cited yet.