4 Search Results for "Bapst, Victor"


Document
The Condensation Phase Transition in the Regular k-SAT Model

Authors: Victor Bapst and Amin Coja-Oghlan

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


Abstract
Much of the recent work on phase transitions in discrete structures has been inspired by ingenious but non-rigorous approaches from physics. The physics predictions typically come in the form of distributional fixed point problems that mimic Belief Propagation, a message passing algorithm. In this paper we show how the Belief Propagation calculation can be turned into a rigorous proof of such a prediction, namely the existence and location of a condensation phase transition in the regular k-SAT model.

Cite as

Victor Bapst and Amin Coja-Oghlan. The Condensation Phase Transition in the Regular k-SAT Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 22:1-22:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bapst_et_al:LIPIcs.APPROX-RANDOM.2016.22,
  author =	{Bapst, Victor and Coja-Oghlan, Amin},
  title =	{{The Condensation Phase Transition in the Regular k-SAT Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.22},
  URN =		{urn:nbn:de:0030-drops-66452},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.22},
  annote =	{Keywords: random k-SAT, phase transitions, Belief Propagation, condensation}
}
Document
Harnessing the Bethe Free Energy

Authors: Victor Bapst and Amin Coja-Oghlan

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


Abstract
Gibbs measures induced by random factor graphs play a prominent role in computer science, combinatorics and physics. A key problem is to calculate the typical value of the partition function. According to the "replica symmetric cavity method", a heuristic that rests on non-rigorous considerations from statistical mechanics, in many cases this problem can be tackled by way of maximising a functional called the "Bethe free energy". In this paper we prove that the Bethe free energy upper-bounds the partition function in a broad class of models. Additionally, we provide a sufficient condition for this upper bound to be tight.

Cite as

Victor Bapst and Amin Coja-Oghlan. Harnessing the Bethe Free Energy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 467-480, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bapst_et_al:LIPIcs.APPROX-RANDOM.2015.467,
  author =	{Bapst, Victor and Coja-Oghlan, Amin},
  title =	{{Harnessing the Bethe Free Energy}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{467--480},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.467},
  URN =		{urn:nbn:de:0030-drops-53180},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.467},
  annote =	{Keywords: Belief Propagation, free energy, Gibbs measure, partition function}
}
Document
Local Convergence of Random Graph Colorings

Authors: Amin Coja-Oghlan, Charilaos Efthymiou, and Nor Jaafari

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


Abstract
Let G=G(n,m) be a random graph whose average degree d=2m/n is below the k-colorability threshold. If we sample a k-coloring Sigma of G uniformly at random, what can we say about the correlations between the colors assigned to vertices that are far apart? According to a prediction from statistical physics, for average degrees below the so-called condensation threshold d_c, the colors assigned to far away vertices are asymptotically independent [Krzakala et al: PNAS 2007]. We prove this conjecture for k exceeding a certain constant k_0. More generally, we determine the joint distribution of the k-colorings that Sigma induces locally on the bounded-depth neighborhoods of a fixed number of vertices.

Cite as

Amin Coja-Oghlan, Charilaos Efthymiou, and Nor Jaafari. Local Convergence of Random Graph Colorings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 726-737, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX-RANDOM.2015.726,
  author =	{Coja-Oghlan, Amin and Efthymiou, Charilaos and Jaafari, Nor},
  title =	{{Local Convergence of Random Graph Colorings}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{726--737},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.726},
  URN =		{urn:nbn:de:0030-drops-53321},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.726},
  annote =	{Keywords: Random graph, Galton-Watson tree, phase transitions, graph coloring, Gibbs distribution, convergence}
}
Document
The Condensation Phase Transition in Random Graph Coloring

Authors: Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, and Dan Vilenchik

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


Abstract
Based on a non-rigorous formalism called the "cavity method", physicists have put forward intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random k-SAT or random graph k-coloring, very shortly before the threshold for the existence of solutions there occurs another phase transition called condensation [Krzakala et al., PNAS 2007]. The existence of this phase transition appears to be intimately related to the difficulty of proving precise results on, e.g., the k-colorability threshold as well as to the performance of message passing algorithms. In random graph k-coloring, there is a precise conjecture as to the location of the condensation phase transition in terms of a distributional fixed point problem. In this paper we prove this conjecture for k exceeding a certain constant k0.

Cite as

Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, and Dan Vilenchik. The Condensation Phase Transition in Random Graph Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 449-464, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{bapst_et_al:LIPIcs.APPROX-RANDOM.2014.449,
  author =	{Bapst, Victor and Coja-Oghlan, Amin and Hetterich, Samuel and Ra{\ss}mann, Felicia and Vilenchik, Dan},
  title =	{{The Condensation Phase Transition in Random Graph Coloring}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{449--464},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.449},
  URN =		{urn:nbn:de:0030-drops-47168},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.449},
  annote =	{Keywords: random graphs, graph coloring, phase transitions, message-passing algorithm}
}
  • Refine by Author
  • 4 Coja-Oghlan, Amin
  • 3 Bapst, Victor
  • 1 Efthymiou, Charilaos
  • 1 Hetterich, Samuel
  • 1 Jaafari, Nor
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 phase transitions
  • 2 Belief Propagation
  • 2 graph coloring
  • 1 Galton-Watson tree
  • 1 Gibbs distribution
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2015
  • 1 2014
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail