Perfect sampling for hard spheres from strong spatial mixing

Konrad Anand, Andreas Göbel, Marcus Pappik, Will Perkins

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We provide a perfect sampling algorithm for the hard-sphere model on subsets of R^d with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials.
Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
EditorsNicole Megow, Adam Smith
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-18
Number of pages18
ISBN (Electronic)9783959772969
DOIs
Publication statusPublished - 4 Sept 2023
Event27th International Conference on Randomization and Computation and the 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems - Georgia Institute of Technology, Atlanta, United States
Duration: 11 Sept 202313 Sept 2023
https://randomconference.com/random-2023-home/

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik
ISSN (Electronic)1868-8969

Conference

Conference27th International Conference on Randomization and Computation and the 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems
Abbreviated titleAPPROX/RANDOM 2023
Country/TerritoryUnited States
CityAtlanta
Period11/09/2313/09/23
Internet address

Keywords / Materials (for Non-textual outputs)

  • perfect sampling
  • hard-sphere model
  • Gibbs point processes

Fingerprint

Dive into the research topics of 'Perfect sampling for hard spheres from strong spatial mixing'. Together they form a unique fingerprint.

Cite this