Search Results

Documents authored by Chatterjee, Arnab

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.47
Belief Propagation Guided Decimation on Random k-XORSAT

Authors: Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien, and Gregory B. Sorkin

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We analyse the performance of Belief Propagation Guided Decimation, a physics-inspired message passing algorithm, on the random k-XORSAT problem. Specifically, we derive an explicit threshold up to which the algorithm succeeds with a strictly positive probability Ω(1) that we compute explicitly, but beyond which the algorithm with high probability fails to find a satisfying assignment. In addition, we analyse a thought experiment called the decimation process for which we identify a (non-) reconstruction and a condensation phase transition. The main results of the present work confirm physics predictions from [Ricci-Tersenghi and Semerjian: J. Stat. Mech. 2009] that link the phase transitions of the decimation process with the performance of the algorithm, and improve over partial results from a recent article [Yung: Proc. ICALP 2024].
Cite as

Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien, and Gregory B. Sorkin. Belief Propagation Guided Decimation on Random k-XORSAT. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 47:1-47:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.ICALP.2025.47,
  author =	{Chatterjee, Arnab and Coja-Oghlan, Amin and Kang, Mihyun and Krieg, Lena and Rolvien, Maurice and Sorkin, Gregory B.},
  title =	{{Belief Propagation Guided Decimation on Random k-XORSAT}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{47:1--47:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.47},
  URN =		{urn:nbn:de:0030-drops-234248},
  doi =		{10.4230/LIPIcs.ICALP.2025.47},
  annote =	{Keywords: random k-XORSAT, belief propagation, decimation process, random matrices}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.39
The Number of Random 2-SAT Solutions Is Asymptotically Log-Normal

Authors: Arnab Chatterjee, Amin Coja-Oghlan, Noela Müller, Connor Riddlesden, Maurice Rolvien, Pavel Zakharov, and Haodong Zhu

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
We prove that throughout the satisfiable phase, the logarithm of the number of satisfying assignments of a random 2-SAT formula satisfies a central limit theorem. This implies that the log of the number of satisfying assignments exhibits fluctuations of order √n, with n the number of variables. The formula for the variance can be evaluated effectively. By contrast, for numerous other random constraint satisfaction problems the typical fluctuations of the logarithm of the number of solutions are bounded throughout all or most of the satisfiable regime.
Cite as

Arnab Chatterjee, Amin Coja-Oghlan, Noela Müller, Connor Riddlesden, Maurice Rolvien, Pavel Zakharov, and Haodong Zhu. The Number of Random 2-SAT Solutions Is Asymptotically Log-Normal. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.APPROX/RANDOM.2024.39,
  author =	{Chatterjee, Arnab and Coja-Oghlan, Amin and M\"{u}ller, Noela and Riddlesden, Connor and Rolvien, Maurice and Zakharov, Pavel and Zhu, Haodong},
  title =	{{The Number of Random 2-SAT Solutions Is Asymptotically Log-Normal}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.39},
  URN =		{urn:nbn:de:0030-drops-210329},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.39},
  annote =	{Keywords: satisfiability problem, 2-SAT, random satisfiability, central limit theorem}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact