TY  - JOUR
A1  - Achlioptas, Dimitris
A1  - Coja-Oghlan, Amin
A1  - Hahn-Klimroth, Maximilian Grischa
A1  - Lee, Joon
A1  - Müller, Noëla
A1  - Penschuck, Manuel
A1  - Zhou, Guangyan
T1  - The number of satisfying assignments of random 2-SAT formulas
T2  - Random structures & algorithms
N2  - We show that throughout the satisfiable phase the normalized number of satisfying assignments of a random 2-SAT formula converges in probability to an expression predicted by the cavity method from statistical physics. The proof is based on showing that the Belief Propagation algorithm renders the correct marginal probability that a variable is set to “true” under a uniformly random satisfying assignment.
KW  - 2-SAT
KW  - Belief Propagation
KW  - satisfiability problem
Y1  - 2021
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/62165
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-621658
SN  - 1098-2418
N1  - DFG Stiftung Polytechnische Gesellschaft DFG ME National Natural Science Foundation of China. Grant Numbers: CO 646/4, 2088/3-2, ME 2088/4-2, 61702019
VL  - 58
IS  - 4
SP  - 609
EP  - 647
PB  - Wiley
CY  - New York, NY [u.a.]
ER  -