6 Search Results for "Müller, Noela"

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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.70
Tiling Random Regular Graphs Efficiently

Authors: Sahar Diskin, Ilay Hoshen, and Maksim Zhukovskii

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

Abstract
We show that for every ε > 0 there exists a sufficiently large d₀ ∈ ℕ such that for every d ≥ d₀, whp the random d-regular graph G(n,d) contains a T-factor for every tree T on at most (1-ε)d/log d vertices. This is best possible since, for large enough integer d, whp G(n,d) does not contain a ((1+ε)d)/(log d)-star-factor. Our method gives a randomised algorithm which whp finds said T-factor and whose expected running time is O(n^{1+o(1)}), as well as an efficient deterministic counterpart.
Cite as

Sahar Diskin, Ilay Hoshen, and Maksim Zhukovskii. Tiling Random Regular Graphs Efficiently. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 70:1-70:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{diskin_et_al:LIPIcs.ICALP.2025.70,
  author =	{Diskin, Sahar and Hoshen, Ilay and Zhukovskii, Maksim},
  title =	{{Tiling Random Regular Graphs Efficiently}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{70:1--70:17},
  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.70},
  URN =		{urn:nbn:de:0030-drops-234477},
  doi =		{10.4230/LIPIcs.ICALP.2025.70},
  annote =	{Keywords: Random regular graphs, Tree tilings}
}
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}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.54
The Full Rank Condition for Sparse Random Matrices

Authors: Amin Coja-Oghlan, Jane Gao, Max Hahn-Klimroth, Joon Lee, Noela Müller, and Maurice Rolvien

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

Abstract
We derive a sufficient condition for a sparse random matrix with given numbers of non-zero entries in the rows and columns having full row rank. Inspired by low-density parity check codes, the family of random matrices that we investigate is very general and encompasses both matrices over finite fields and {0,1}-matrices over the rationals. The proof combines statistical physics-inspired coupling techniques with local limit arguments.
Cite as

Amin Coja-Oghlan, Jane Gao, Max Hahn-Klimroth, Joon Lee, Noela Müller, and Maurice Rolvien. The Full Rank Condition for Sparse Random Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX/RANDOM.2023.54,
  author =	{Coja-Oghlan, Amin and Gao, Jane and Hahn-Klimroth, Max and Lee, Joon and M\"{u}ller, Noela and Rolvien, Maurice},
  title =	{{The Full Rank Condition for Sparse Random Matrices}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.54},
  URN =		{urn:nbn:de:0030-drops-188792},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.54},
  annote =	{Keywords: random matrices, rank, finite fields, rationals}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.24
Inference and Mutual Information on Random Factor Graphs

Authors: Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick, Noela Müller, Konstantinos Panagiotou, and Matija Pasch

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
Random factor graphs provide a powerful framework for the study of inference problems such as decoding problems or the stochastic block model. Information-theoretically the key quantity of interest is the mutual information between the observed factor graph and the underlying ground truth around which the factor graph was created; in the stochastic block model, this would be the planted partition. The mutual information gauges whether and how well the ground truth can be inferred from the observable data. For a very general model of random factor graphs we verify a formula for the mutual information predicted by physics techniques. As an application we prove a conjecture about low-density generator matrix codes from [Montanari: IEEE Transactions on Information Theory 2005]. Further applications include phase transitions of the stochastic block model and the mixed k-spin model from physics.
Cite as

Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick, Noela Müller, Konstantinos Panagiotou, and Matija Pasch. Inference and Mutual Information on Random Factor Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cojaoghlan_et_al:LIPIcs.STACS.2021.24,
  author =	{Coja-Oghlan, Amin and Hahn-Klimroth, Max and Loick, Philipp and M\"{u}ller, Noela and Panagiotou, Konstantinos and Pasch, Matija},
  title =	{{Inference and Mutual Information on Random Factor Graphs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.24},
  URN =		{urn:nbn:de:0030-drops-136692},
  doi =		{10.4230/LIPIcs.STACS.2021.24},
  annote =	{Keywords: Information theory, random factor graphs, inference problems, phase transitions}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.23
Refined Asymptotics for the Number of Leaves of Random Point Quadtrees

Authors: Michael Fuchs, Noela S. Müller, and Henning Sulzbach

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
In the early 2000s, several phase change results from distributional convergence to distributional non-convergence have been obtained for shape parameters of random discrete structures. Recently, for those random structures which admit a natural martingale process, these results have been considerably improved by obtaining refined asymptotics for the limit behavior. In this work, we propose a new approach which is also applicable to random discrete structures which do not admit a natural martingale process. As an example, we obtain refined asymptotics for the number of leaves in random point quadtrees. More applications, for example to shape parameters in generalized m-ary search trees and random gridtrees, will be discussed in the journal version of this extended abstract.
Cite as

Michael Fuchs, Noela S. Müller, and Henning Sulzbach. Refined Asymptotics for the Number of Leaves of Random Point Quadtrees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fuchs_et_al:LIPIcs.AofA.2018.23,
  author =	{Fuchs, Michael and M\"{u}ller, Noela S. and Sulzbach, Henning},
  title =	{{Refined Asymptotics for the Number of Leaves of Random Point Quadtrees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.23},
  URN =		{urn:nbn:de:0030-drops-89165},
  doi =		{10.4230/LIPIcs.AofA.2018.23},
  annote =	{Keywords: Quadtree, number of leaves, phase change, stochastic fixed-point equation, central limit theorem, positivity of variance, contraction method}
}
  • Refine by Type
  • 6 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2024
  • 1 2023
  • 1 2021
  • 1 2018

  • Refine by Author
  • 4 Coja-Oghlan, Amin
  • 3 Müller, Noela
  • 3 Rolvien, Maurice
  • 2 Chatterjee, Arnab
  • 2 Hahn-Klimroth, Max
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Probabilistic inference problems
  • Show More...

  • Refine by Keyword
  • 2 central limit theorem
  • 2 random matrices
  • 1 2-SAT
  • 1 Information theory
  • 1 Quadtree
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact