In random K-SAT formulas, the entropy density of a solution community, worked out with belief propagation, differs between communities in the same solution cluster.

The paper

The paper's details are OpenAlex's; the citation count is OpenAlex's, 20 Oct 2026. The line on the paper is machine-written, as noted under Why it matters.

Why it matters

Written by Claude (claude-sonnet-5-5) on 20 Oct 2026 from the paper's abstract (as arXiv publishes it) and its OpenAlex record. Machine-written context to help a reader: it is not evidence, it moves no number, and it may be wrong. The quoted sentence is the claim; where it stands is computed from the record. If it misreads the paper, tell the stewards.

The story so far

1. 1

   What the authors did

   The authors explored single solution clusters of random 3- and 4-SAT formulas using unbiased and biased random walks and the replica-symmetric cavity method from statistical physics. They also looked at clusters reached by stochastic search algorithms.

   Machine-written from the paper's abstract, as noted under Why it matters.

2. 2

   What they found

   • The giant connected component of the solution space already splits into many communities when the constraint density is below the clustering transition point.
   • Solutions in the same community are more similar to each other and more densely connected than to other solutions.
   • Beyond the clustering transition point, the same community behaviour is seen in clusters reached by several stochastic search algorithms.

   Machine-written from the paper's abstract, as noted under Why it matters.

3. 3

   What has been checked on Ecdysis

   Exuvia registered the claim on 20 October 2026, with a test written from the paper. No check has been filed yet.

What would check it

How far it has been checked

1. 1
   Same data, same methodverification · not yet

   Not yet: re-run the paper's analysis on its own data, where the authors have published it.

2. 2
   New data, same methodreproduction · not yet

   Not yet: the same method on new data covering the claim's population and period. Established needs one.

3. 3
   The designrobustness tests and arguments · not yet

   Nothing yet: change the method or the data and see whether it holds (a robustness test), or argue that the method does not test what the claim says.

How sure is the record?

Share this finding

Ready-made posts, written from the record. You post them yourself, from your own account; nothing is ever posted for anyone.

Click a post's text to select all of it. Both posts give the claim's standing on the record, and the longer one says what the checks show and what they do not; the wording changes when the record does. The longer post quotes the paper first, then gives the machine-written headline, marked as such; edit it as you like. To cite the claim, see Cite this claim.

What would prove it wrong

Refuted if an independent analysis of a random K‑SAT instance shows that the estimated entropy densities for all communities identified within any single solution cluster differ by less than 0.01 bits per variable (or lie within a 95% confidence interval of width ≤0.02) across at least two distinct communities.

The test as Exuvia registered it on 20 Oct 2026, written from the paper's words.

The wider literature

Other claims from the same paper

• uncheckedIn random 3- and 4-SAT, the connected set of solutions splits into many communities before the constraint density reaches the clustering transition point.“We find that the giant connected component of the solution space has already formed many different communities when the constraint density of the formula is still lower than the solution space cluste…”
• uncheckedSolutions of the same community are more similar with each other and more densely connected with each other than with the other solutions.

Headlines are machine-written from the paper's abstract, or from the quote and the paper's title where no abstract is open; each claim's own words are quoted beneath its headline.