Marié Hattingh

Machdel Matthee

Hanlie Smuts

Ilias Pappas

Yogesh K Dwivedi

Matti Mäntymäki

Preface

This book presents the proceedings of the 19th International Federation of Information Processing (IFIP) Conference on e-Business, e-Services, and e-Society (I3E 2020), which was held in Skukuza, Kruger National Park, South Africa, during April 6-8, 2020. The annual I3E conference is a core part of Working Group 6.11, which aims to organize and promote the exchange of information and co-operation related to all aspects of e-Business, e-Services, and e-Society (the three Es). The I3E conference series is truly interdisciplinary and welcomed contributions from both academics and practitioners alike.

The main theme of the 2020 conference was "Responsible design, implementation and use of information and communication technology." In line with the inclusive nature of the I3E series, all papers related to e-Business, e-Services, and e-Society were welcomed.

The age of digital transformation opens up exciting new avenues for design and application of ICTs. Yet, with the ubiquitous connectedness of a digitally transformed world, come unintended, unpredictable, and often adverse consequences for individuals, societies, and organizationsin developed and developing contexts. Security, privacy, trustworthiness, exploitation, and well-being are some of the pressing concerns resulting from new digital realities.

There is need for responsible design, implementation, and use of information systems (IS) based on critical awareness and ethical practices. As rightly put by Schultze (2017:65): "As IS researchers we need to examine our own practicesincluding the questions we ask, the methods we deploy and theories we adoptto understand and critically review our world-making."

The IFIP I3E 2020 was held during April 6-8, 2020, and brought together contributions from a variety of perspectives, disciplines, and communities for the advancement of knowledge regarding responsible design, implementation, and use of information and communications technology. This was evident by our variety of keynote speakers and topics for the panel discussions. We were delighted to welcome three distinguished keynote speakers:

-Mr. James van der Westhuizen who is the founder and managing partner of KnowHouse, founded 20 years ago out of a passion to work differently with the challenge of learning and change in organizations. The conference held two panels to facilitate discussions on important topics. The first panel on "Blockchainhope or hype? Blockchain as a disruptive force" was chaired by Dr. Matti Mäntymäki. Blockchain is surrounded by considerable optimism and enthusiasm among businesses and academia. This enthusiasm is evidenced by the numerous calls for papers in journals and dedicated blockchain tracks in conferences. The purpose of the panel was to make sense of the actual significance of the blockchain phenomenon and provoke discussion and exchange of ideas among the I3E community. To this end, the panel paid homage to the heterogenous nature of the I3E community and invited a diverse of group of expert panellists to share their distinctive perspectives on blockchain.

The second panel, made up of a panel of editors, was chaired by Dr. Shirish C. Srivastava. The panel consisted of six journal editors from international and local (South African) publications. Each editor gave an explanation on the requirements for authors when submitting to their journal.

The Call for Papers solicited submissions in two main categories: full research papers and short research-in-progress papers. Each submission was reviewed by at least two knowledgeable academics in the field, in a double-blind process. The 2020 conference received 191 submissions. Out of the 191 papers, 91 papers were selected to be presented at the conference. Four of the accepted papers were not included in the final proceedings because the authors decided to withdraw it. Thus, the acceptance rate was 45.5%.

Following the conference, two special issues were organized for selected best papers of the I3E 2020. The two special issues are in the International Journal of Information Management (IJIM) and the International Journal of Electronic Government Research (IJEGR).

The final set of 87 full and short papers submitted to I3E 2020 that appear in these proceedings were clustered into 14 groups, each of which are outlined below.

Part I: addressing the area of Blockchain. Three papers were grouped under this theme. One of the papers proposed a framework for the adoption of blockchain whilst another reported on the application of blockchain technology in Healthcare. The third paper examined the potential disruptive impact of cryptocurrencies.

Part II of the book addressed papers on the Fourth Industrial Revolution. Nine papers were grouped under this theme. Paper details range from a systematic literature review on the incompatibility of Smart manufacturing for SMMEs to the development of models and frameworks through the application of Smart technologies. One paper included a bibliographic coupling and co-occurrence on the topic of Smart City and Economy, whilst another reported on robotic automation and the consequences for knowledge workers. The final paper reported on the co-creation for digitalization in Norwegian business clusters.

Part III of the book addressed e-Business. 12 papers were grouped under this theme. The papers presented works on online banking quality, a conceptual framework for digital entrepreneurship, mobile applications, online switching behavior, and how games are used in business. Three papers reported on systematic review of literature on eWOM, mobile shopping acceptance predictors and social commerce adoption predictors. The final paper presented a review of papers published from 2001 to 2019 by I3E.

Part IV of the book addressed Business Processes. 10 papers were grouped under this theme. The papers presented works on governance achieved through business process management, how IT is being used in Fintech Innovation, a meta model for maturity models, and a strategic model for the safeguarding the preservation of business value. In addition to these themes, papers were presented on using the story-card method for business process re-engineering, using Zachman's framework as an IS theory and a review of the Task-Technology Fit Theory.

Part V of the book addressed Big Data and Machine Learning. Seven papers were grouped under this theme. The papers presented work on using machine learning in the field of healthcare, data governance, using a deep learning neural network model to predict information diffusion on Twitter, and big data visualization tools.

Part VI of the book addresses ICT and Education. Seven papers were grouped under this theme. The papers presented work on mobile learning, new considerations for flipped classroom approach, and eModeration system considerations.

Part VII of the book addressed eGovernment. Six papers were grouped under this theme. The papers presented work on the use of social media in eParticipation, enterprise architectures in eGovernments, and eGovernment implementation framework. Other themes included were digital innovation in public organizations, implementation challenges in eProcurement, and a case from Ghana on the effects on National Health Insurance digital platform development and use.

Part VIII of the book addressed eHealth. Six papers were grouped under this theme. Papers presented work on the use of technology for diabetic patients, factors influencing community health workers, wearable devices, and a Twitter social network analysis of the South African Health Insurance Bill.

Part IX of the book addressed Security. Four papers were grouped under this theme. Papers presented work on cyber-harassment among LGBTQIA+ youth, online identity theft, cybersecurity readiness of e-tail organizations, and the ethics of using publicly available data.

Part X of the book addressed Social Media. Six papers were grouped under this theme. Papers presented works on a conceptual framework for media use behavior, metaphors of social media, credibility of online information (fake news), and problematic media and technology use.

Part XI of the book addressed Knowledge and Knowledge Management. Three papers were grouped under this theme. Papers presented work on knowledge transfer science education, a knowledge asset management implementation framework, and a conceptual knowledge visualization framework for knowledge transfer.

Part XII of the book addressed ICT for Gender Equality and Development. Nine papers were grouped under this theme. Papers presented work on the rural vs urban digital divide, socio-economic factors in Internet usage in Nigeria, and enablers and barriers of mobile commerce and banking services among elderly individuals. A methodology for addressing the second-level digital divide, gender equality in the ICT context, digital competence requirements, and the influence of culture on women's IT career choices were also presented.

Part XIII of the book addressed Information Systems for Governance. Four papers were grouped under this theme. Papers presented work on the use of machine learning on financial inclusion data for governance in Eswatini, ordinance-tweet mining to disseminate urban policy knowledge for smart governance, open technology innovation in healthcare services, and multi-stakeholder-centric data analytics governance framework.

Part XIV of the book addressed User Experience and Usability. Three papers were grouped under this theme. Papers presented work on the use of machine learning and eye tracking to predict users' ratings on the aesthetics of websites, a systematic review on designing for positive emotional responses in users of interactive digital technologies, and a methodology to compare the usability of information systems.

The success of the 19th IFIP I3E Conference (I3E 2020) was a result of the enormous efforts of numerous people and organizations. Firstly, this conference was only made possible by the continued support of WG 6.11 for this conference series and for selecting South Africa to host it in 2020, for which we are extremely grateful. We received many good-quality submissions from authors across the globe and we would like to thank them for choosing I3E 2020 as the outlet to present and publish their current research. We are indebted to the Program Committee, who generously gave up their time to provide constructive reviews and facilitate the improvement of the submitted manuscripts. We would like to thank the Department of Informatics of the University of Pretoria for their support in enabling us to host this conference. Thank you to AfricaMassive that assisted us with all the logistical arrangements with hosting the conference in Skukuza located in the Kruger National Park. Finally, we extend our sincere gratitude to everyone involved in organizing the conference, to our esteemed keynote speakers, and to Springer LNCS as the publisher of these proceedings, which we hope will be of use for the continued development of research related to the three Es 1 .

February 2020 Marié Hattingh Machdel Matthee

Hanlie Smuts Ilias Pappas Yogesh K. Dwivedi Matti Mäntymäki

1 Due to the global COVID-19 pandemic and the consequential worldwide imposed travel restrictions and lock down, the I3E 2020 conference event scheduled to take place in Skukuza, South Africa, was unfortunately cancelled.

viii Preface

vi Preface

Preface vii

Contents -Part I xvii

Elena Parmiggiani Norwegian University of Science and Technology, Norway Douglas Parry Stellenbosch University, South Africa Marcel Pikhart University of Hradec Kralove, Czech Republic Colin Pilkington UNISA, South Africa Komla Pillay University of Pretoria, South Africa Henk Pretorius University of Pretoria, South Africa Tania Prinsloo University of Pretoria, South Africa Maciel Queiroz Paulista University, Brazil Van Raj UNISA, South Africa Nripendra Rana Swansea University, UK Anthony Renner-Micah University of Ghana, Ghana Suzanne Sackstein WITS University, South Africa Brenda Scholtz Nelson Mandela University, South Africa Lisa Seymour University of Cape Town, South Africa Anuragini Shirish University of Paris-Saclay, France Djofack Sidonie University of Yaounde II, Cameroon Ivana Simonova University of Jan Evangelista Purkyne, Czech Republic Konstantina Spanaki Loughborough University, UK Ruan Spies Stellenbosch University, South Africa Riana Steyn University of Pretoria, South Africa Ilse Struweg University of Johannesburg, South Africa Zhaohao Sun Federation University Australia, Australia Reima Vesa Suomi University of Turku, Finland Libuse Svobodova University of Hradec Kralove, Czechia Kuttimani Tamilmani Swansea University, UK Maureen Tanner University of Cape Town, South Africa Ali Tarhini Sultan Qaboos University, Oman Temitope Oluwaseyi Tokosi Nelson Mandela University, South Africa Cathrine Tømte University of Adger, Noway Juan Carlos Torrado Vidal Autonomous University of Madrid, Spain Pieter Toussaint Norwegian University of Science and Technology, Norway Rakhi Tripathi FORE School of Management, India Valentyna Tsap Tallinn University of Technology, Estonia Pitso Tsibolane Stellenbosch University, South Africa Marita Turpin University of Pretoria, South Africa Parijat Upadhyay IMT Nagpur, India Jean-Paul Van Belle University of Cape Town, South Africa Judy van Biljon UNISA, South Africa Rogier Van de Wetering Open University, The Netherlands Thomas van der Merwe UNISA, South Africa Alta Van der Merwe University of Pretoria, South Africa J. P. van Deventer University of Pretoria, South Africa


Tobias Friedrich

Andreas Göbel

Martin S Krejca

Marcus Pappik

A spectral independence view on hard spheres via block dynamics

Keywords: 2012 ACM Subject Classification Theory of computation → Random walks and Markov chains Hard-sphere Model, Markov Chain, Partition Function, Gibbs Distribution, Approximate Counting, Spectral Independence Digital Object Identifier 10.4230/LIPIcs.ICALP.2021.61 Category Track A: Algorithms, Complexity and Games

The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in d dimensions. Up to a fugacity of λ < e/2 d , the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure.

Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization.

To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.

Introduction

Statistical physics models particle systems as probability distributions. One of the most fundamental and mathematically challenging models in this area is the hard-sphere model, which plays a central role in understanding the thermodynamic properties of monoatomic gases and liquids [START_REF] Boublik | Statistical thermodynamics of simple liquids and their mixtures[END_REF][START_REF] Hansen | Theory of Simple Liquids[END_REF]. It is a continuous model that studies the distribution and macroscopic behavior of indistinguishable spherical particles, assuming only hard-core interactions, i.e., no two particles can occupy the same space.

We focus on computational properties of the grand-canonical ensemble of the hard-sphere model in a finite d-dimensional cubic region V = [0, ℓ) d in the Euclidean space. In the 61:2

A spectral independence view on hard spheres via block dynamics grand-canonical ensemble, the system can exchange particles with its surrounding based on a fugacity parameter λ, which is inverse to the temperature of the system. For the rest of the paper, we make the common assumption that the system is normalized such that the particles have unit volume. That means we fix their radii to r = (1/v d ) 1/d , where v d is the volume of a unit sphere in d dimensions.

A simple probabilistic interpretation of the distribution of particles in the grand-canonical ensemble is that centers of points that are drawn from a Poisson point process on V with intensity λ, conditioned on the event that no two particles overlap (i.e., every pair of centers has distance at least 2r). The resulting distribution over particle configurations in V is called the Gibbs distribution of the model. An important quantity in such models is the so called partition function Z(V, λ), which can be seen as the normalizing constant of the Gibbs distribution. Formally, it is defined as (1) , . . . , x (k) dν d×k , where D x (1) , . . . , x (k) = 1 if d x (i) , x (j) ≥ 2r for all i, j ∈ [k] with i ̸ = j 0 otherwise and ν d×k is the Lebesgue measure on R d×k . Commonly, two computational task are associated with the grand-canonical hard-sphere model: [START_REF] Levi | Improved analysis of higher order random walks and applications[END_REF] approximating its partition function Z(V, λ), and (2) approximately sampling from the Gibbs distribution.

Z(V, λ) = 1 + k∈N>0 λ k k! V k D x
Studying computational aspects of the hard-sphere model carries a historical weight, as in the seminal work of Metropolis [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF], the Monte Carlo method was introduced to investigate a two-dimensional hard-sphere model. Approximate-sampling Markov chain approaches have been mainly focused on the canonical ensemble of the model, that is, the system does not exchange particles with its surrounding and thus, the distribution is defined over a fixed number of spheres [START_REF] Hayes | Lower bounds on the critical density in the hard disk model via optimized metrics[END_REF][START_REF] Kannan | Rapid mixing of several Markov chains for a hard-core model[END_REF][START_REF] Jenssen | On the hard sphere model and sphere packings in high dimensions[END_REF]. Considering the grand canonical ensemble, exact sampling algorithms have appeared in the literature for the two-dimensional model without asymptotic runtime guarantees [START_REF] Kendall | Perfect simulation for the area-interaction point process[END_REF][START_REF] Kendall | Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes[END_REF][START_REF] Babu Moka | Analysis of perfect sampling methods for hard-sphere models[END_REF]. A result that is more aligned with theoretical computer science was given in [START_REF] Guo | Perfect simulation of the hard disks model by partial rejection sampling[END_REF], where the authors introduced an exact sampling algorithm for the grand-canonical hard-sphere model in d-dimensions. Their algorithm is based on partial rejection sampling with a runtime linear in the volume of the system |V| when assuming a continuous computational model and access to a sampler from a continuous Poisson point process. Their approach is guaranteed to apply for λ < 2 -(d+1/2) .

Besides such sampling results, there is an ongoing effort to improve the known fugacity regime where the Gibbs measure is unique and correlations decay exponentially fast [START_REF] Fernández | The analyticity region of the hard sphere gas. Improved bounds[END_REF][START_REF] Christoph | Disagreement percolation for the hard-sphere model[END_REF][START_REF] Helmuth | Correlation decay for hard spheres via Markov chains[END_REF][START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF]. Note that for many discrete spin systems, such as the hard-core model, correlation decay is closely related to the applicability of different methods for efficient approximation of the partition function [START_REF] Sly | Computational transition at the uniqueness threshold[END_REF][START_REF] Galanis | Improved inapproximability results for counting independent sets in the hard-core model[END_REF][START_REF] Weitz | Counting independent sets up to the tree threshold[END_REF]. Recently, the correlation decay bounds for the hard-sphere model were improved in [START_REF] Helmuth | Correlation decay for hard spheres via Markov chains[END_REF] to λ < 2/2 d , using probabilistic arguments, and in [START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF] to λ < e/2 d , based on an analytic approach. A common feature of [START_REF] Helmuth | Correlation decay for hard spheres via Markov chains[END_REF] and [START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF] is that they translated tools originally developed in theoretical computer science for investigating the discrete hard-core model to the continuous domain.

Our work is in line with the computational view on the hard-sphere model but more algorithmic in nature. We investigate the range of the fugacity λ for which an approximation of Z(V, λ) can be obtained efficiently in terms of the volume of the system |V|, assuming a

V = [0, ℓ) d . If there is a δ ∈ (0, 1] such that λ ≤ (1 -δ) e 2 d , then for each ε ∈ (0, 1] there is a randomized ε-approximation of Z(V, λ) computable in time polynomial in |V| 1/δ 2 and 1 ε .
Note that this bound on λ precisely coincides with the best known bound for the uniqueness of the Gibbs measure in the thermodynamic limit, recently established in [START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF]. For many discrete spin systems, such as the hard-core model or general anti-ferromagnetic 2-state spin systems, the region of efficient approximation of the partition function is closely related to uniqueness of the Gibbs measure. More precisely, it can be shown that the partition function of every graph of maximum degree ∆ can be approximated efficiently if the corresponding Gibbs distribution on an infinite ∆ regular tree is unique [START_REF] Li | Correlation decay up to uniqueness in spin systems[END_REF][START_REF] Weitz | Combinatorial criteria for uniqueness of Gibbs measures[END_REF]. A detailed discussion for the discrete hard-core model can be found in the next subsection. In a sense, Theorem 1 can be seen as the algorithmic counterpart of the recent uniqueness result for the continuous hard-sphere model. This answers an open question, asked in [START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF].

The way we prove our result is quite contrary to [START_REF] Helmuth | Correlation decay for hard spheres via Markov chains[END_REF] and [START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF]. Instead of translating discrete tools from computer science into the continuous domain, we rather discretize the hard-sphere model. By this, existing algorithmic and probabilistic techniques for discrete models become available, and we avoid continuous analysis.

Our applied discretization scheme is fairly intuitive and results in an instance of the discrete hard-core model. This model has been extensively studied in the computer science community. However, as this hard-core instance is exponential in the size of the continuous [START_REF] Anari | Spectral independence in high-dimensional expanders and applications to the hardcore model[END_REF]. Together with a known self-reducibility scheme for clique dynamics, this results in the desired approximation algorithm.

Note that we aim for a rigorous algorithmic result for approximating the partition function of the continuous hard-sphere model. To be in line with commonly used discrete computational models, our Markov chain Monte Carlo algorithm does not assume access to a continuous sampler but instead samples approximately from a discretized version of the Gibbs distribution. Note that sampling from the continuous hard-sphere partition function cannot be done using a discrete computation model as this would involve infinite float pointer precision. For practical matters, our discretization of the Gibbs distribution can be seen as an approximation of the original continuous Gibbs measure. However, a rigorous comparison between both distributions based on total variation distance is not applicable, due to the fact that one is discrete whereas the other is continuous in nature.

I C A L P 2 0 2 1 61:4

A spectral independence view on hard spheres via block dynamics

Assuming access to a continuous sampler, we believe that our approach can be used to obtain an approximation of the Gibbs distribution of the continuous model within the same fugacity regime, by adding small perturbations to the drawn sphere centers. This would be in line with the relation between the mixing time of continuous heat-bath dynamics and strong spatial mixing, pointed out in [START_REF] Helmuth | Correlation decay for hard spheres via Markov chains[END_REF], combined with the uniqueness bound from [START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF].

In Sections 1.1-1.3 we discuss our contributions in more detail and explain how they relate to the existing literature. Finally in Section 1.4 we discuss possible extensions and future work. All technical details, statements and proofs are presented the full version of the paper.

Discretization and hard-core model

Our discretization scheme expresses the hard-sphere partition function as the partition function of an instance of the (univariate) hard-core model. An instance of the hard-core model is a tuple (G, λ) where G = (V, E) is an undirected graph and λ ∈ R >0 . Its partition function is defined as

Z(G, λ) := I∈I(G) λ |I| ,
where I(G) denotes the independent sets of G. A common way to obtain an approximation for the partition function is by applying a Markov chain Monte Carlo algorithm. This involves sampling from the Gibbs distribution µ (G,λ) of (G, λ), which is a probability distribution on I(G) that assigns each independent set I ∈ I(G) the probability

µ (G,λ) (I) = λ |I| Z(G, λ) .
Conditions for efficient approximation of the hard-core partition function have been studied extensively in the theoretical computer science community. Due to hardness results in [START_REF] Sly | Computational transition at the uniqueness threshold[END_REF] and [START_REF] Galanis | Improved inapproximability results for counting independent sets in the hard-core model[END_REF], it is known that for general graphs of maximum degree ∆ ∈ {3} ∪ N >5 there is a critical parameter value λ c (∆) = (∆ -1) ∆-1 /(∆ -2) ∆ , such that there is no FPRAS for the partition function of (G, λ) for λ > λ c (∆), unless RP = NP. On the other hand, in [START_REF] Weitz | Counting independent sets up to the tree threshold[END_REF] it was proven that there is a deterministic algorithm for approximating the partition function of (G, λ) for λ < λ c (∆) that runs in time |V | O(∆) . The critical value λ c (∆) is especially interesting, as it precisely coincides with the upper bound on λ for which the hard-core model on an infinite ∆-regular tree exhibits strong spatial mixing and a unique Gibbs distribution [START_REF] Weitz | Counting independent sets up to the tree threshold[END_REF]. For this reason, it is also referred to as the tree threshold.

This relation between computational hardness and phase transition in statistical physics is one of the most celebrated results in the area. Both, the hardness results [START_REF] Galanis | Inapproximability of the independent set polynomial below the Shearer threshold[END_REF][START_REF] Bezáková | Inapproximability of the independent set polynomial in the complex plane[END_REF] and the approximation algorithms [START_REF] Patel | Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials[END_REF][START_REF] Nicholas | Computing the independence polynomial: From the tree threshold down to the roots[END_REF] were later generalized for complex λ.

Note that the computational hardness above the tree threshold λ c (∆) for general graphs of maximum degree ∆ applies to both, randomized and deterministic algorithms. However, to the Gibbs distribution, meaning that it eventually converges to µ (G,λ) . A sequence of results has shown that for all ∆ ≥ 3 there is a family of graphs with maximum degree ∆, such that the Glauber dynamics are torpidly mixing for λ > λ c (∆), even without additional complexity-theoretical assumptions [START_REF] Dyer | On counting independent sets in sparse graphs[END_REF]27,[START_REF] Mossel | On the hardness of sampling independent sets beyond the tree threshold[END_REF]. Whether the Glauber dynamics are rapidly mixing for the entire regime λ < λ c (∆) remained a long-standing open problem, until recently the picture was completed [START_REF] Anari | Spectral independence in high-dimensional expanders and applications to the hardcore model[END_REF]. By relating spectral expansion properties of certain random walks on simplicial complexes to the Glauber dynamics, it was shown that the mixing time is polynomial in |V | below the tree threshold. The mixing time was recently further improved in [START_REF] Chen | Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion[END_REF] for a broader class of spin systems by combining simplicial complexes with entropy factorization and using the modified log-Sobolev inequality.

in
By mapping the hard-sphere model to an instance of the hard-core model we can make use of the existing results about approximation and sampling below the tree threshold. Roughly, our discretization scheme restricts the positions of sphere centers to an integer grid, while scaling the radii of spheres and the fugacity appropriately. For a hard-sphere instance (V, λ)

with V = [0, ℓ) d the hard-core representation for resolution ρ ∈ R ≥1 is a hard-core instance (G ρ , λ ρ ) with G ρ = (V ρ , E ρ ). Each vertex v ∈ V ρ represents a
λ ρ = λ/ρ d .
We provide the following result on the rate of convergence of Z(G ρ , λ ρ ) to the hard-sphere partition function Z(V, λ) in terms of ρ.

▶ Lemma 2. Let (V, λ) be an instance of the continuous hard-sphere model in d dimensions.

For each resolution ρ ≥ 2 √ d it holds that

1 -ρ -1 e Θ(|V| ln|V|) ≤ Z(V, λ) Z(G ρ , λ ρ ) ≤ 1 + ρ -1 e Θ(|V| ln|V|) .
Although proving this rate of convergence involves some detailed geometric arguments, there is an intuitive reason why the partition functions converge eventually as ρ → ∞.

Increasing the resolution ρ also linearly increases the side length of the grid and the minimum distance that sphere centers can have. This is equivalent to putting a grid into V with increasing granularity but fixing the radii of spheres instead. However, only scaling the granularity of this grid increases the number of possible configurations by roughly ρ d , which would cause the partition function of the hard-core model to diverge as ρ → ∞. To compensate for this, we scale the weight of each vertex in the hard-core model by the inverse of this factor.

Using this discretization approach, the fugacity bound from Theorem 1 results from simply considering ∆ ρ , the maximum degree of G ρ and comparing λ ρ with the corresponding tree threshold λ c (∆ ρ ). Recall that we assume r = (1/v d )

λ ρ = λ ρ d < λ c 2 d ρ d , for λ < ρ d λ c 2 d ρ d .
This follows from the fact that ρ d λ c 2 d ρ d converges to e/2 d from above for ρ → ∞. Thus, the approximation bound from Theorem 1 and the uniqueness bound in [START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF] coincide with the regime of λ, for which λ ρ is below the tree threshold λ c (∆ ρ ) in the limit ρ → ∞.

The arguments above show that for a sufficiently high resolution ρ the partition function of the hard-sphere model Z(V, λ) is well approximated by the partition function of our discretization (G ρ , λ ρ ) and that (G ρ , λ ρ ) is below the tree threshold for λ < e/2 d . However, Assuming that each vertex should be updated at least once to remove correlations with the initial state, any mixing time that is sublinear in the number of vertices is unlikely. We circumvent this problem by applying dynamics that update multiple vertices at each step but still allow each step to be computed efficiently without constructing the graph explicitly.

I

Block and clique dynamics

Most of the results that we discuss from now on apply to the multivariate version of the hard-core model, that is, each vertex v ∈ V has its own weight λ v . For a given graph G = (V, E) we denote the set of such vertex weights by λ = {λ v } v∈V and write (G, λ) for the resulting multivariate hard-core instance. In the multivariate setting, the contribution of an independent set I ∈ I(G) to the partition function is defined as the product of its vertex weights (i.e., v∈I λ v ), where the contribution of the empty set is fixed to 1. Similar to the univariate hard-core model, the Gibbs distribution assigns a probability to each independent set proportionally to its contribution to the partition function.

As we discussed before, the main problem with approximating the partition function of our discretization (G ρ , λ ρ ) is that the required graph G ρ is exponential in the volume of the original continuous system |V|. As the Glauber dynamics Markov chain only updates a single vertex at each step, the resulting mixing time is usually polynomial in the size of the graph, which is not feasible in our case. Various extensions to Glauber dynamics for updating multiple vertices in each step have been proposed in the literature, two of which we discuss in the following.

Clique dynamics

Recently, in [START_REF] Friedrich | Polymer dynamics via cliques: New conditions for approximations[END_REF] a Markov chain, called clique dynamics, was introduced in order to efficiently sample from the Gibbs distribution of abstract polymer models. Note that this is similar to our algorithmic problem, as abstract polymer models resemble multivariate hard-core instances. For a given graph

G = (V, E), we call a set Λ = {Λ i } i∈[m] ⊆ 2 V a
I(G[Λ i ]) is chosen according to the Gibbs distribution µ (G[Λi],λ[Λi]) .
Note that, as the vertices Λ i form a clique, such an independent set is either the empty set or contains a single vertex from v ∈ Λ i . If the empty set is drawn, all vertices from Λ i are removed from the current independent set. Otherwise, if a single vertex v ∈ Λ i is drawn, the chain tries to add v to the current independent set.

Using a coupling argument, it was proven in [START_REF] Friedrich | Polymer dynamics via cliques: New conditions for approximations[END_REF] that the so-called clique dynamics condition implies that for any clique cover of size m the clique dynamics are mixing in time polynomial in m and Z max , where

Z max = max i∈[m] {Z(G[Λ i ], λ[Λ i ]
)} denotes the maximum partition function of a clique in Λ. This is important for the application to polymer models, as they are usually used to model partition functions of other spin systems, which often results in a multivariate hard-core model of exponential size [START_REF] Helmuth | Algorithmic Pirogov-Sinai theory[END_REF][START_REF] Casel | Zeros and approximations of holant polynomials on the complex plane[END_REF][START_REF] Jenssen | Algorithms for #bis-hard problems on expander graphs[END_REF][START_REF] Chen | Fast algorithms at low temperatures via Markov chains[END_REF][START_REF] Borgs | Efficient sampling and counting algorithms for the Potts model on 𭟋 d at all temperatures[END_REF]8,[START_REF] Galanis | Fast algorithms for general spin systems on bipartite expanders[END_REF]. As discussed in [START_REF] Friedrich | Polymer dynamics via cliques: New conditions for approximations[END_REF], those instances tend to have polynomial size clique covers that arise naturally from the original spin system. In such cases, the mixing time of clique dynamics is still polynomial in the size of original spin system, as long as the clique dynamics condition is satisfied.

This is very similar to our discretization (G ρ , λ ρ ). To see this, set a = 2ρ

Block dynamics

Block dynamics are a very natural generalization of Glauber dynamics to arbitrary sets of vertices. For a given graph G = (V, E), we call a set Λ = {Λ i } i∈[m] ⊆ 2 V a block cover of size m if and only if its union covers all vertices V . We refer to the elements of Λ as blocks. Note that the clique cover discussed before is a special case of a block cover, where all blocks are restricted to be cliques. At each step, the block dynamics Markov chain B(G, λ, Λ) chooses a block Λ i ∈ Λ uniformly at random. Then, the current independent set is updated on Λ i based on the projection of the Gibbs distribution onto Λ i and conditioned on the current independent set outside Λ i .

In fact, block dynamics are defined for a much more general class of spin systems than the hard-core model. However, due to the fact that each step of the Markov chain involves sampling from a conditional Gibbs distribution, block dynamics are rarely used as an algorithmic tool on its own. Instead, they are usually used to deduce rapid mixing of other dynamics.

For spin systems on lattice graphs, close connections between the mixing time of block dynamics and Glauber dynamics are known [START_REF] Martinelli | Lectures on Glauber dynamics for discrete spin models[END_REF]. Such connections were for example applied to improve the mixing time of Glauber dynamics of the Monomer Dimer model on torus graphs [START_REF] Van Den Berg | Random sampling for the monomer-dimer model on a lattice[END_REF]. Moreover, block dynamics were used to improve conditions for rapid mixing of Glauber dynamics on specific graph classes, such as proper colorings [START_REF] Dyer | Randomly coloring sparse random graphs with fewer colors than the maximum degree[END_REF][START_REF] Efthymiou | MCMC sampling colourings and independent sets of g(n, d/n) near uniqueness threshold[END_REF][START_REF] Efthymiou | Sampling random colorings of sparse random graphs[END_REF][START_REF] Mossel | Gibbs rapidly samples colorings of g(n, d/n)[END_REF] or the hard-core model [START_REF] Efthymiou | MCMC sampling colourings and independent sets of g(n, d/n) near uniqueness threshold[END_REF][START_REF] Mossel | Gibbs rapidly samples colorings of g(n, d/n)[END_REF] in sparse random graphs. A very general result for the mixing time of block dynamics was achieved in [START_REF] Blanca | Spatial mixing and nonlocal Markov chains[END_REF], who proved that for all spin systems on a finite subgraph of the d-dimensional integer lattice the mixing time of block dynamics is polynomial in the number of blocks if the spin system exhibits strong spatial mixing. This result was later generalized in [START_REF] Blanca | Swendsen-Wang dynamics for general graphs in the tree uniqueness region[END_REF] for the Ising model on arbitrary graphs. Very recently, block dynamics based random equally-sized blocks where used in [START_REF] Chen | Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion[END_REF] to prove entropy factorization and improve the mixing time of Glauber dynamics for a variety of discrete spin systems up to the tree threshold.

Although our discretization works by restricting sphere positions to the integer lattice, the resulting graph is rather different from the lattice. Thus, results like those in [START_REF] Blanca | Spatial mixing and nonlocal Markov chains[END_REF] do not apply to our setting. However, on the other hand, we do not need to prove rapid mixing for

I

Improved mixing condition for clique dynamics via block dynamics

We analyze the mixing time of clique dynamics for a given clique cover by relating it to the mixing time of block dynamics, using the cliques as blocks. This is done by investigating a notion of pairwise influence between vertices that has also been used to establish rapid mixing of Glauber dynamics up to the tree threshold [START_REF] Anari | Spectral independence in high-dimensional expanders and applications to the hardcore model[END_REF]. Let P G [w] denote the probability of the event that a vertex w ∈ V is in an independent set drawn from µ (G,λ) . Further, let P G [w] denote the probability that w is not in an independent set. We extend this abuse of notation to conditional probabilities, so P G [• | w ] for example denotes the probability of some event conditioned on w not being in an independent set. For a pair of vertices v, w ∈ V the influence Ψ G (v, w) of v on w is defined as

Ψ G (v, w) = 0 if v = w, P G [w | v ] -P G [w | v ] otherwise.
The following condition in terms of pairwise influence is central to our analysis.

▶ Condition 3. Let (G, λ) be an instance of the multivariate hard-core model. There is a constant C ∈ R >0 and a function q : V → R >0 such that for all S ⊆ V and r ∈ S it holds

that v∈S |Ψ G (r, v)|q(v) ≤ Cq(r).
Note that this condition appeared before in [START_REF] Chen | Rapid mixing of Glauber dynamics up to uniqueness via contraction[END_REF], where it was used for bounding the mixing time of Glauber dynamics for anti-ferromagnetic spin systems. Given Condition 3, we obtain the following result for the mixing time of block dynamics based on a clique cover.

▶ Theorem 4. Let (G, λ) be an instance of the multivariate hard-core model that satisfies Condition 3. Let Λ be a clique cover for G of size m, and let

Z max = max i∈[m] {Z(G[Λ i ], λ[Λ i ])}.
The mixing time of the block dynamics B(G, λ, Λ), starting from ∅ ∈ I(G), is bounded by

τ (∅) B (ε) ≤ m O((2+C)C) Z O((2+C)C) max ln 1 ε .
Using a bound for the sum of absolute pairwise influences that was recently established in [START_REF] Chen | Rapid mixing of Glauber dynamics up to uniqueness via contraction[END_REF], it follows that the univariate hard-core model satisfies Condition 3 up to the tree threshold. As a result, we know that the mixing time of block dynamics is polynomial in m and Z max for any clique cover of size m. To the best of our knowledge, this is the first result for the mixing time of block dynamics for the univariate hard-core model on general graphs that holds in this parameter range.

As we aim to apply clique dynamics to avoid sampling from the conditional Gibbs distribution in each step, we still need to prove that Theorem 4 also holds in terms of clique dynamics. To this end, we apply a Markov chain comparison argument from [START_REF] Diaconis | Comparison theorems for reversible Markov chains[END_REF] to prove that using clique dynamics instead of block dynamics for the same clique cover Λ increases

τ (∅) C (ε) ≤ m O(1/δ 2 ) Z O(1/δ 2 ) max ln 1 ε .

A side journey: comparison to multivariate conditions

In fact, Corollary 5 is sufficient for our application to the hard-sphere model. However, we also aim to set Condition 3 in the context of other conditions for rapid mixing of clique dynamics for the multivariate hard-core model. Note that such a rapid mixing result for clique dynamics caries over to Glauber dynamics by taking each vertex as a separate clique of size 1.

To this end, we compare Condition 3 to a strict version of the clique dynamics condition, originally introduced in [START_REF] Friedrich | Polymer dynamics via cliques: New conditions for approximations[END_REF] in the setting of clique dynamics for abstract polymer models. It turns out that this strict version of the clique dynamics condition directly implies Condition 3. This is especially interesting, as the clique dynamics condition was initially introduced as a local condition (only considering the neighborhood of each vertex) and is based on a coupling argument. However, we show that it can as well be understood as a sufficient condition for the global decay of pairwise influence with increasing distance between vertices.

Formally, we say that the strict clique dynamics condition is satisfied for an instance of the multivariate hard-core model (G, λ) if there is a function f : V → R >0 and a constant α ∈ (0, 1) such that for all v ∈ V it holds that

w∈N (v) λ w 1 + λ w f (w) ≤ (1 -α)f (v),
where N (v) is the neighborhood of v in G. This is a strict version of the clique dynamics condition in that the original clique dynamics condition would correspond to the case α = 0 (i.e., the strict clique dynamics condition requires some strictly positive slack α).

The result of our comparison is summarized in the following statement.

▶ Lemma 6. Let (G, λ) be an instance of the multivariate hard-core model. If (G, λ) satisfies the strict clique dynamics condition for a function f and a constant α, then it also satisfies Condition 3 for q = f and C = 1 α .

Lemma 6 is proven by translating the calculation of pairwise influences to the self-avoiding walk tree of the graph, based on a result in [START_REF] Chen | Rapid mixing of Glauber dynamics up to uniqueness via contraction[END_REF], and applying a recursive argument on this tree.

Despite being an interesting relationship between local coupling arguments and global pairwise influence, Lemma 6 also implies that, from an algorithmic perspective, Theorem 4 can be used to produce similar results as those obtained in [START_REF] Friedrich | Polymer dynamics via cliques: New conditions for approximations[END_REF] for abstract polymer models.

Further, note that for the univariate model, using pairwise influence yields strictly better results than any coupling approach in the literature. This raises the question if a refined I C A L P 2 0 2 1 61:10 A spectral independence view on hard spheres via block dynamics argument based on pairwise influences can be used in the multivariate setting to improve on the clique dynamics condition, leading to better approximation results on abstract polymer models.

Analyzing spectral expansion

As core technique for obtaining Theorem 4, we adapt an approach for bounding the mixing time that was recently used to prove rapid mixing of Glauber dynamics for the entire regime below the tree threshold for several applications, such as the hard-core model [START_REF] Anari | Spectral independence in high-dimensional expanders and applications to the hardcore model[END_REF], general two-state spin systems [START_REF] Chen | Rapid mixing of Glauber dynamics up to uniqueness via contraction[END_REF], and proper colorings [START_REF] Chen | Rapid mixing for colorings via spectral independence[END_REF][START_REF] Feng | Rapid mixing from spectral independence beyond the Boolean domain[END_REF]. The idea is to map the desired distribution to a weighted simplicial complex.

A simplicial complex X over a groundset U is a set family X ⊆ 2 U such that for each τ ∈ X every subset of τ is also in X. We call the elements τ ∈ X the faces of X and refer to its cardinality |τ | as dimensionality.

For a univariate hard-core instance (G, λ), the authors of [START_REF] Anari | Spectral independence in high-dimensional expanders and applications to the hardcore model[END_REF] construct a simplicial complex over a ground set U that contains two elements x v , x v ∈ U for each vertex v ∈ V . For every

independent set I ∈ I(G), a face τ I ∈ X is introduced such that x v ∈ τ I if v ∈ I and x v ∈ τ I
otherwise. The simplicial complex is completed by taking the downward closure of these faces.

Note that by construction all maximum faces of the resulting complex are |V |-dimensional and there is a one-to-one correspondence between the maximum faces and the independent sets in I(G). By assigning each maximum face τ I ∈ X an appropriate weight, the Glauber dynamics can be represented as a random walk on those maximum faces, which is sometimes referred to as the two-step walk or down-up walk. Using a local-to-global theorem [START_REF] Levi | Improved analysis of higher order random walks and applications[END_REF], the mixing time of this two-step walk can then be bounded based on certain local expansion properties of the simplicial complex X. It is then proved that such local expansion properties are well captured by the largest eigenvalue of the pairwise influence matrix Ψ G , which is a |V | × |V | matrix that contains the pairwise influence Ψ G (v, w) for all v, w ∈ V . Finally, by bounding those influences a bound on this largest eigenvalue of Ψ G is obtained. This analysis was later refined and generalized in [START_REF] Chen | Rapid mixing of Glauber dynamics up to uniqueness via contraction[END_REF] to general two-state spin systems.

This method was independently extended in [START_REF] Chen | Rapid mixing for colorings via spectral independence[END_REF] and [START_REF] Feng | Rapid mixing from spectral independence beyond the Boolean domain[END_REF] to the non-Boolean domain by applying it to the Glauber dynamics for proper colorings. The main differences to the Boolean domain are that elements of the simplicial complex now represent combinations of a vertex and a color. Furthermore, the bound on the local spectral expansion was obtained by using a different influence matrix, which captures the effect of selecting a certain color for one vertex on the distribution of colors for another vertex.

Although we are dealing with the hard-core model, which is Boolean in nature, the way that we model block dynamics is mainly inspired by the existing work on proper colorings [START_REF] Chen | Rapid mixing for colorings via spectral independence[END_REF]. Assume we have an instance of the multivariate hard-core model (G, λ) and let Λ be a clique cover for G of size m such that every pair of distinct cliques is vertex-disjoint (i.e., Λ is a partition of G into cliques). We construct a simplicial complex X based on a ground set U that contains one element x v ∈ U for each vertex v ∈ V and one additional element

∅ i for each clique Λ i ∈ Λ.
We introduce a face τ I ∈ X for each independent set I ∈ I(G) such that for every Λ i ∈ Λ we have pendent set to the partition function, the block dynamics based on Λ are equivalent to the two-step walk on X. Thus, in order to bound the mixing time of the block dynamics, it is sufficient to study the local expansion properties of X. To this end, we adapt the influence matrix used for proper colorings in [START_REF] Chen | Rapid mixing for colorings via spectral independence[END_REF]. For x ∈ U , let P G [x] denote the probability that

∅ i ∈ τ I if Λ i ∩ I = ∅ and x v ∈ τ I if Λ i ∩ I = {v} for some v ∈ Λ i . The
x ∈ τ I for an independent set I ∈ I(G) drawn from µ (G,λ) and corresponding maximum face τ I ∈ X. Similarly as for defining pairwise influences, we extend this notation to conditional probabilities. The clique influence matrix Φ G,Λ contains an entry Φ G,Λ (x, y) for each

x, y ∈ U with Φ G,Λ (x, y) = 0 if x, y ∈ U i for some i ∈ [m], P G [y | x ] -P G [y] otherwise.
By using similar linear-algebraic arguments as in [START_REF] Chen | Rapid mixing for colorings via spectral independence[END_REF] we prove that the maximum eigenvalue of Φ G,Λ can be used to upper bound the local spectral expansion of X. Note that our simplicial-complex representation is only given under the assumption that the cliques in the clique cover Λ are pairwise disjoint. Indeed, this is a necessary requirement to map the block dynamics to the two-step walk such that the local-global-theorem from [START_REF] Levi | Improved analysis of higher order random walks and applications[END_REF] can be applied. Thus, Lemma 7 only helps to prove Theorem 4 for disjoint clique covers.

However, we relax this requirement by proving that for every clique cover Λ a disjoint clique cover K can be constructed such that the block dynamics B(G, λ, Λ) and B(G, λ, K) have asymptotically the same mixing time. By this comparison argument, we extend Theorem 4

to arbitrary clique covers.

We are aware that, in the case of Glauber dynamics, more recent techniques for combining simplical complex representations with entropy factorization as proposed in [START_REF] Chen | Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion[END_REF] yield superior mixing time results. However, in case of the hard-core model, this approach comes with an additional multiplicative factor of ∆ O(∆ 2 ) in the mixing time (see section 8 of [START_REF] Chen | Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion[END_REF]).

Although negligible for bounded degree graphs, this would be too much for our application, as the degree of our discretization gets exponentially large in the continuous volume |V| of the system. Thus, directly relating local spectral expansion with the spectral gap of block dynamics is more suitable in our case. We leave as an open question, whether a modification of the approach in [START_REF] Chen | Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion[END_REF] can be applied to further improve our mixing time result.

Outlook

We obtain the fugacity bound from Theorem 1 based on the tree threshold λ c (∆) of the hard-core model. An obvious question is whether there are any structural properties of our discretization that can be used to improve this bound. Similar results are known for specific graph classes, such as the 2-dimensional square lattice [48,[START_REF] Vera | Improved bounds on the phase transition for the hard-core model in 2-dimensions[END_REF][START_REF] Weitz | Counting independent sets up to the tree threshold[END_REF]. In [START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF] the authors discuss that a generalization of the connective constant to the continuous Euclidean space might be applicable to improve their uniqueness result for the hard-sphere model. A comparable algorithmic result was already established for the discrete hard-core model in [START_REF] Sinclair | Spatial mixing and the connective constant: Optimal bounds[END_REF]. However, any such improvement for our discretization would require the connective constant of G ρ to be at least by a constant factor small than its maximum degree ∆ ρ . Unfortunately, due to a I C A L P 2 0 2 1 61:12 A spectral independence view on hard spheres via block dynamics result in [START_REF] Mathew D Penrose | Self-avoiding walks and trees in spread-out lattices[END_REF], this is not the case. Although this does not necessarily imply that a similar concept does not work in continuous space, it gives a strong evidence that a more specialized tool instead of the connective constant might be required.

A different direction for future work is to see which other quantities and properties of the model are preserved under discretization. This would especially include the thermodynamic pressure and its analyticity. As a matter of fact, non-analytic points of the pressure along the positive real axis of fugacity in the thermodynamic limit are known to mark phase transitions in infinite volume systems (see for example [START_REF] Michelen | Analyticity for classical gasses via recursion[END_REF]). One way to approach this could be to prove a relation between zero-freeness of the continuous and the discretized partition function in a complex neighborhood of the real axis by extending our convergence result to the complex domain. Along this line, insights could be gained in how far properties like correlation decay and phase transitions (or their absence) are preserved under sufficiently fine discretization.

From a purely technical point of view, it is interesting to see if our result on the mixing time of block dynamics in Theorem 4 also holds without the requirement of using cliques as blocks. Especially: is the mixing time for block dynamics for the univariate hard-core model polynomial in the number of blocks for any block cover? Most of our techniques that we use for clique covers, such as modeling the distribution as a simplicial complex and relating its local spectral expansion to the clique influence matrix, can be generalized in a straightforward way for different choices of blocks. However, the main difficulty is to relate generalized versions of the clique influence matrix to pairwise influences, as we do in Lemma 7. One way to circumvent this might be to not rely on pairwise influences at all but to rather investigate the influence matrix directly, for example, via different computational-tree methods.

Finally, it would be interesting to see if approaches like ours can be extended to other continuous models from statistical physics (see for example coarse-graining [START_REF] Espanol | Statistical mechanics of coarse-graining[END_REF]). We believe that the variety of tools that are already established for discrete spin systems are useful in this setting to establish rigorous computational results for different continuous models. We emphasize that clique and block dynamics are a useful computational tool to handle the exponential blow-ups caused by discretization.

  the randomized setting, Markov chain Monte Carlo methods are known to improve the runtime of the algorithm introduced in [54]. Those approaches use the vertex-wise self-reducibility of the hard-core model to construct a randomized approximation of the partition function based on an approximate sampler for the Gibbs distribution. Commonly, a Markov chain on the state space I(G), called Glauber dynamics, is used to construct the sampling scheme. At each step, a vertex v ∈ V is chosen uniformly at random. With probability λ/(1 + λ) the chain tries to add v to the current independent set and otherwise it tries to remove it. The resulting Markov chain is ergodic and reversible with respect T. Friedrich and A. Göbel and M. S. Krejca and M. Pappik 61:5

  clique cover of size m if and only if its union covers all vertices V and each Λ i ∈ Λ induces a clique in G. For an instance of the multivariate hard-core model (G, λ) and a given clique cover Λ of G with size m the clique dynamics Markov chain C(G, λ, Λ) is defined as follows. First, a clique Λ i ∈ Λ for i ∈ [m] is chosen uniformly at random. Let us write G[Λ i ] for the subgraph, induced by Λ i , and λ[Λ i ] = {λ v } v∈Λi for the corresponding set of vertex weights. Next, an independent set from

√ d r

  and divide the d-dimensional integer lattice of side length ρℓ into cubic regions of side length a. Every pair of integer points within such a cubic region has Euclidean distance less than 2ρr, meaning that the corresponding vertices in G ρ are adjacent. Thus, each such cubic region forms a clique, resulting in a clique cover of size (ρℓ/a) d ∈ O(|V|). This means, there is always a clique cover with size linear in |V| and independent of the resolution ρ. By showing that, for the univariate hard-core model, the mixing time of clique dynamics is polynomial in the size of the clique cover for all λ ρ < λ c (∆ ρ ), we obtain a Markov chain with mixing time polynomial in |V| independent of the resolution ρ. Unfortunately, the clique dynamics condition does not hold for the entire regime up to the tree threshold in the univariate hard-core model. We overcome this problem by proving a new condition for rapid mixing of clique dynamics based on a comparison with block dynamics.

▶ Corollary 5 .

 5 the mixing time by at most a factor 2Z max . The following corollary, which is central for proving Theorem 1, follows immediately. Let (G, λ) be an instance of the univariate hard-core model such that the degree of G is bounded by ∆. Let Λ be a given clique cover of size m with Z max = max i∈[m] {Z(G[Λ i ], λ)}. Denote by C = C(G, λ, Λ) the corresponding clique dynamics. If there is some δ ∈ R >0 such that λ ≤ (1 -δ)λ c (∆) then the mixing time of the clique dynamics C, starting from ∅ ∈ I(G), is bounded by

  simplicial complex is completed by taking the downward closure of these faces. All maximum faces of the resulting complex are m-dimensional and there is a bijection between the maximum faces and the independent sets of G. Furthermore, there is a natural partitioning {U i } i∈[m] of the ground set U , each partition U i corresponding to a clique Λ i , such that every maximum face in X contains exactly one element from each partition U i .By weighting each maximum face of X by the contribution of the corresponding inde-T. Friedrich and A. Göbel and M. S. Krejca and M. Pappik 61:11

0 2 1 61:6 A spectral independence view on hard spheres via block dynamics this

  does not immediately imply an approximation algorithm within the desired runtime bounds. Based on Lemma 2, we still need to choose ρ exponentially large in the volume |V|. Note that the number of vertices in G ρ is roughly |V ρ | ∈ Θ ρ d |V| . Even without explicitly constructing the graph, this causes problems, as the best bound for the mixing time of the Glauber dynamics is polynomial in |V ρ | and thus exponential in |V|. Intuitively, the reason for this mixing time is that the Glauber dynamics only change one vertex at each step.

C A L P 2

0 2 1 61:8 A spectral independence view on hard spheres via block dynamics arbitrary

  block covers. Instead, in order to obtain rapid mixing for clique dynamics, it is sufficient to establish this result for cases where all blocks are cliques.

	Applying block dynamics directly would involve sampling from a conditional Gibbs
	distribution within each clique. Due to the exponential size of the cliques in our discretization,
	this would impose additional algorithmic challenges. Instead, similar to the previous literature,
	we rather use block dynamics as a tool for proving rapid mixing of another Markov chain,
	namely clique dynamics.

C A L P 2

  To obtain Theorem 4 it is then sufficient to relate Condition 3 to the maximum eigenvalue of Φ G,Λ . The following lemma establishes this connection.

▶ Lemma 7. Let (G, λ) be an instance of the multivariate hard-core model that satisfies Condition 3 for a function q and a constant C. For every S ⊆ V and every disjoint clique cover Λ of G[S] it holds that the largest eigenvalue of Φ G[S],Λ is at most (2 + C)C.

S. Krejca: This work was supported by the Paris Île-de-France Region.