Addendum 2: Poisson Cloning Model for Random 3‑SAT

Indexed indatacite

Abstract

We provide a rigorous definition of the Poisson cloning model for random 3-SAT at clause density α = 4.2, following the construction of Kim (2008). We prove that the cloned model is mutually contiguous with the original Erdős–Rényi model, so that any property holding with high probability in one model also holds in the other. This result is the first technical brick required to extend the Nam–Sly–Sohn 1RSB proof from random regular NAE-SAT to canonical 3-SAT.

Citation impact

28
total citations
FWCI
Percentile
References
2
Too recent for citation history.

Authors

1

Topics & keywords

Keywords
  • Poisson distribution
  • Property (philosophy)
  • Addendum
  • Random variable
  • Cloning (programming)
  • Probability density function
No related works found for this paper.