6 Search Results for "Bapst, Victor"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.39
Locality Sensitive Hashing in Hyperbolic Space

Authors: Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, and Cheng Xin

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
For a metric space (X, d), a family ℋ of locality sensitive hash functions is called (r, cr, p₁, p₂) sensitive if a randomly chosen function h ∈ ℋ has probability at least p₁ (at most p₂) to map any a, b ∈ X in the same hash bucket if d(a, b) ≤ r (or d(a, b) ≥ cr). Locality Sensitive Hashing (LSH) is one of the most popular techniques for approximate nearest-neighbor search in high-dimensional spaces, and has been studied extensively for Hamming, Euclidean, and spherical geometries. An (r, cr, p₁, p₂)-sensitive hash function enables approximate nearest neighbor search (i.e., returning a point within distance cr from a query q if there exists a point within distance r from q) with space O(n^{1+ρ}) and query time O(n^ρ) where ρ = (log 1/p₁)/(log 1/p₂). But LSH for hyperbolic spaces ℍ^d remains largely unexplored. In this work, we present the first LSH construction native to hyperbolic space. For the hyperbolic plane (d = 2), we show a construction achieving ρ ≤ 1/c, based on the hyperplane rounding scheme. For general hyperbolic spaces (d ≥ 3), we use dimension reduction from ℍ^d to ℍ² and the 2D hyperbolic LSH to get ρ ≤ 1.59/c. On the lower bound side, we show that the lower bound on ρ of Euclidean LSH extends to the hyperbolic setting via local isometry, therefore giving ρ ≥ 1/c².
Cite as

Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, and Cheng Xin. Locality Sensitive Hashing in Hyperbolic Space. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.SoCG.2026.39,
  author =	{Deng, Chengyuan and Gao, Jie and Lu, Kevin and Luo, Feng and Xin, Cheng},
  title =	{{Locality Sensitive Hashing in Hyperbolic Space}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.39},
  URN =		{urn:nbn:de:0030-drops-258454},
  doi =		{10.4230/LIPIcs.SoCG.2026.39},
  annote =	{Keywords: Locality Sensitive Hashing, Hyperbolic Geometry, Dimension Reduction, Approximate Nearest Neighbor Search}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.39
Planting and MCMC Sampling from the Potts Model

Authors: Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We consider the problem of sampling from the ferromagnetic q-state Potts model on the random d-regular graph with parameter β > 0. A key difficulty that arises in sampling from the model is the existence of a "metastability" window β ∈ (β_u,β_u'), where roughly the distribution has two competing modes, the so-called disordered and ordered phases. This causes classical Markov-chain algorithms to be slow mixing from worst-case initialisations. Nevertheless, Helmuth, Jenssen and Perkins (SODA '19) designed a sampling algorithm that works for all β, when d ≥ 5 and q = d^{Ω(d)}, using polymers and cluster expansion methods; more recently, their analysis technique has been adapted to show that a Markov chain (random-cluster dynamics) mixes fast when initialised appropriately, in the same regime of q,d,β. Despite these positive algorithmic results, a well-known bottleneck behind cluster-expansion arguments is that they inherently only work for large q, whereas it is widely conjectured that sampling on the random d-regular graph is possible for all q,d ≥ 3. The only result so far that applies to general q,d ≥ 3 is by Blanca and Gheissari who showed that the random-cluster dynamics mixes fast in the "uniqueness" regime β < β_u where roughly only the disordered mode exists. For β ≥ β_u however, a second subdominant mode emerges creating bottlenecks and giving rise to correlations which have been hard to handle, especially for small values of q and d. Our main contribution is to perform a delicate analysis of the Potts distribution and the random-cluster dynamics that goes beyond the threshold β_u. We use planting as the main tool, a technique used in the analysis of random CSPs to capture how the space of solutions is correlated with the structure of the random instance. While planting arguments provide only weak sampling guarantees generically, here we instead combine planting with the analysis of random-cluster dynamics to obtain significantly stronger guarantees. We are thus able to show that the random-cluster dynamics initialised from all-out mixes fast for all integers q,d ≥ 3 beyond the uniqueness threshold β_u, all the way to the optimal threshold β_c ∈ (β_u,β_u') where the dominant mode switches from disordered to ordered. A more involved analysis also applies to the ordered regime β > β_c where we obtain an algorithm for all d ≥ 3 and q ≥ (5d)⁵, improving significantly upon the previous range of q,d by Carlson, Davies, Fraiman, Kolla, Potukuchi, and Yap (FOCS'22).
Cite as

Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Planting and MCMC Sampling from the Potts Model. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.STACS.2026.39,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Smolarova, Paulina},
  title =	{{Planting and MCMC Sampling from the Potts Model}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.39},
  URN =		{urn:nbn:de:0030-drops-255280},
  doi =		{10.4230/LIPIcs.STACS.2026.39},
  annote =	{Keywords: approximate sampling, Glauber dynamics, Potts model, random cluster model}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.27
Understanding the Impact of Value Selection Heuristics in Scheduling Problems

Authors: Tim Luchterhand, Emmanuel Hebrard, and Sylvie Thiébaux

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
It has been observed that value selection heuristics have less impact than other heuristic choices when solving hard combinatorial optimization (CO) problems. It is often thought that this is because more time is spent on unsatisfiable sub-problems where the value ordering is irrelevant. In this paper we investigate this belief in the scheduling domain and come up with a more detailed explanation. We find that, even though there are less relevant choices to be made on hard instances, each mistake tends to have a bigger impact, to a point where the potential gain from a value heuristic predominates. Moreover, we observe two interesting and relatively surprising phenomena when solving scheduling problems. First, the accuracy of a given value selection heuristic decreases with the optimality gap. Second, the computational penalty of a mistake increases with the accuracy of the heuristic. For the first observation, we argue that on hard problems, constraint propagation removes a large portion of choices that align with the intuition behind the heuristic. This means that the heuristic faces mostly difficult choices. For the second observation, we argue that simple heuristics tend to make more mistakes on intuitive choice points, and the computational cost for refuting these mistakes is smaller than for those made by a more accurate heuristic.
Cite as

Tim Luchterhand, Emmanuel Hebrard, and Sylvie Thiébaux. Understanding the Impact of Value Selection Heuristics in Scheduling Problems. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 27:1-27:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{luchterhand_et_al:LIPIcs.CP.2025.27,
  author =	{Luchterhand, Tim and Hebrard, Emmanuel and Thi\'{e}baux, Sylvie},
  title =	{{Understanding the Impact of Value Selection Heuristics in Scheduling Problems}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{27:1--27:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.27},
  URN =		{urn:nbn:de:0030-drops-238885},
  doi =		{10.4230/LIPIcs.CP.2025.27},
  annote =	{Keywords: Scheduling, Branching Heuristics, Constraint Programming}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.22
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
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.467
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
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.449
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 Type
  • 6 Document/PDF
  • 3 Document/HTML

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

  • Refine by Author
  • 3 Bapst, Victor
  • 3 Coja-Oghlan, Amin
  • 1 Deng, Chengyuan
  • 1 Galanis, Andreas
  • 1 Gao, Jie
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 1 Computing methodologies → Discrete space search
  • 1 Computing methodologies → Heuristic function construction
  • 1 Computing methodologies → Neural networks
  • 1 Computing methodologies → Planning and scheduling
  • 1 Mathematics of computing → Gibbs sampling
  • Show More...

  • Refine by Keyword
  • 2 Belief Propagation
  • 2 phase transitions
  • 1 Approximate Nearest Neighbor Search
  • 1 Branching Heuristics
  • 1 Constraint Programming
  • 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