Abstract
We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom–Rowlinson model in a region of \(d \)-dimensional Euclidean space \( \mathbb {V} \subset \mathbb {R} ^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function.
Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom–Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu \left( \mathbb {V} \right) \) if the fugacity is below a certain threshold. For the \(d \)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\textrm{e}/2^d \). As the number of dimensions \(d \) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom–Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anari, N., Jain, V., Koehler, F., Pham, H.T., Vuong, T.D.: Entropic independence II: optimal sampling and concentration via restricted modified log-Sobolev inequalities. CoRR abs/2111.03247 (2021). https://arxiv.org/abs/2111.03247
Anari, N., Liu, K., Gharan, S.O.: Spectral independence in high-dimensional expanders and applications to the hardcore model. CoRR abs/2001.00303 (2020). http://arxiv.org/abs/2001.00303
Boublik, T., Nezbeda, I., Hlavaty, K.: Statistical thermodynamics of simple liquids and their mixtures. Fundam. Stud. Eng. Elsevier (1980)
Chen, X., Feng, W., Yin, Y., Zhang, X.: Rapid mixing of Glauber dynamics via spectral independence for all degrees. CoRR abs/2105.15005 (2021). http://arxiv.org/abs/2105.15005
Chen, Z., Liu, K., Vigoda, E.: Rapid mixing of Glauber dynamics up to uniqueness via contraction. CoRR abs/2004.09083 (2020). http://arxiv.org/abs/2004.09083
Chen, Z., Liu, K., Vigoda, E.: Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. In: STOC, pp. 1537–1550. ACM (2021). https://doi.org/10.1145/3406325.3451035
Friedrich, T., Göbel, A., Katzmann, M., Krejca, M., Pappik, M.: Using random graphs to sample repulsive gibbs point processes with arbitrary-range potentials. CoRR abs/2204.01793 (2022). http://arxiv.org/abs/2204.01793
Friedrich, T., Göbel, A., Krejca, M., Pappik, M.: A spectral independence view on hard spheres via block dynamics. In: Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), vol. 198, pp. 66:1–66:15 (2021). https://doi.org/10.4230/LIPIcs.ICALP.2021.66
Galanis, A., Ge, Q., Stefankovic, D., Vigoda, E., Yang, L.: Improved inapproximability results for counting independent sets in the hard-core model. Random Struct. Algorithms 45(1), 78–110 (2014). https://doi.org/10.1002/rsa.20479
Guo, H., Jerrum, M.: Perfect simulation of the hard disks model by partial rejection sampling. CoRR abs/1801.07342 (2018). https://arxiv.org/abs/1801.07342v2
Hansen, J.P., McDonald, I.R.: Theory of Simple Liquids. Academic Press, 4th edn. (2013). https://doi.org/10.1016/B978-0-12-387032-2.00013-1
Helmuth, T., Perkins, W., Regts, G.: Algorithmic Pirogov-Sinai theory. In: Proceedings of the 51st Annual ACM Symposium on the Theory of Computing (STOC), pp. 1009–1020 (2019). https://doi.org/10.1145/3313276.3316305
Jenssen, M., Joos, F., Perkins, W.: On the hard sphere model and sphere packings in high dimensions. Forum Math. Sigma 7, e1 (2019). https://doi.org/10.1017/fms.2018.25
Jerrum, M., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169–188 (1986). https://doi.org/10.1016/0304-3975(86)90174-X
Kendall, W.S.: Perfect simulation for the area-interaction point process. In: Accardi, L., Heyde, C.C. (eds.) Probability Towards 2000. Lecture Notes in Statistics, vol. 128, pp. 218–234. Springer, Cham (1998). https://doi.org/10.1007/978-1-4612-2224-8_13
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087–1092 (1953). https://doi.org/10.1063/1.1699114
Michelen, M., Perkins, W.: Strong spatial mixing for repulsive point processes. CoRR abs/2202.08753 (2022). https://arxiv.org/abs/2202.08753
Patel, V., Regts, G.: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46(6), 1893–1919 (2017). https://doi.org/10.1137/16M1101003
Penrose, M.D.: Self-avoiding walks and trees in spread-out lattices. J. Stat. Phys. 77(1–2), 3–15 (1994). https://doi.org/10.1007/BF02186829
Sinclair, A., Srivastava, P., Štefankovič, D., Yin, Y.: Spatial mixing and the connective constant: optimal bounds. Probab. Theory Relat. Fields 168, 153–197 (2017). https://doi.org/10.1007/s00440-016-0708-2
Sly, A.: Computational transition at the uniqueness threshold. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287–296 (2010). https://doi.org/10.1109/FOCS.2010.34
Štefankovič, D., Vempala, S., Vigoda, E.: Adaptive simulated annealing: a near-optimal connection between sampling and counting. J. ACM 56(3), 1–36 (2009). https://doi.org/10.1145/1516512.1516520
Stoyan, D., Kendall, W.S., Chiu, S.N., Mecke, J.: Stochastic Geometry and its Applications. Wiley, Hoboken (2013). https://doi.org/10.1002/9781118658222
Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the 38th Annual ACM Symposium on the Theory of Computing (STOC), pp. 140–149 (2006). https://doi.org/10.1145/1132516.1132538
Widom, B., Rowlinson, J.S.: New model for the study of liquid-vapor phase transitions. J. Chem. Phys. 52(4), 1670–1684 (1970). https://doi.org/10.1063/1.1673203
Acknowledgments
Andreas Göbel was funded by the project PAGES (project No. 467516565) of the German Research Foundation (DFG). This project has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No. 945298-ParisRegionFP and was partially funded by the HPI Research School on Data Science and Engineering.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Friedrich, T., Göbel, A., Katzmann, M., Krejca, M.S., Pappik, M. (2022). Algorithms for Hard-Constraint Point Processes via Discretization. In: Zhang, Y., Miao, D., Möhring, R. (eds) Computing and Combinatorics. COCOON 2022. Lecture Notes in Computer Science, vol 13595. Springer, Cham. https://doi.org/10.1007/978-3-031-22105-7_22
Download citation
DOI: https://doi.org/10.1007/978-3-031-22105-7_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22104-0
Online ISBN: 978-3-031-22105-7
eBook Packages: Computer ScienceComputer Science (R0)