In this paper, we give an almost linear time and space algorithms to sample from an exponential mechanism with an $\ell_1$-score function defined over an exponentially large non-convex set. As a direct result, on input an $n$ vertex $m$ edges graph $G$, we present the first $\widetilde{O}(m)$ time and $O(m)$ space algorithms for differentially privately outputting an $n$ vertex $O(m)$ edges synthetic graph that approximates all the cuts and the spectrum of $G$. These are the first private algorithms for releasing synthetic graphs that nearly match this task’s time and space complexity in the non-private setting while achieving the same (or better) utility as the previous works in the more practical sparse regime. Additionally, our algorithms can be extended to private graph analysis under continual observation.

We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds on a broad class of graphs which we refer to as *recursively separable*. In particular, for any $n$-vertex $K_h$-minor-free graph, our algorithm achieve an additive error of $ \widetilde{O}(h(nW)^{1/3} ) $, where $ W $ represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of $ \widetilde{O}(n^{1/4}\sqrt{W}) $. Our approach can be seen as a generalization of the celebrated binary tree mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on a path graph. In essence, our approach is based on generalizing the binary tree mechanism to graphs that are *recursively separable*.

Quantum sampling, a fundamental subroutine in numerous quantum algorithms, involves encoding a given probability distribution in the amplitudes of a pure state. Given the hefty cost of large-scale quantum storage, we initiate the study of quantum sampling in a distributed setting. Specifically, we assume that the data is distributed among multiple machines, and each machine solely maintains a basic oracle that counts the multiplicity of individual elements. Given a quantum sampling task, which is to sample from the joint database, a coordinator can make oracle queries to all machines. We focus on the oblivious communication model, where communications between the coordinator and the machines are predetermined. We present both sequential and parallel algorithms: the sequential algorithm queries the machines sequentially, while the parallel algorithm allows the coordinator to query all machines simultaneously. Furthermore, we prove that both algorithms are optimal in their respective settings.

Abstract. We explore connections between the phenomenon of correlation decay (more precisely, strong spatial mixing) and the location of Lee–Yang and Fisher zeros for various spin systems. In particular we show that, in many instances, proofs showing that weak spatial mixing on the Bethe lattice (infinite [Formula: see text]-regular tree) implies that strong spatial mixing on all graphs of maximum degree [Formula: see text] can be lifted to the complex plane, establishing the absence of zeros of the associated partition function in a complex neighborhood of the region in parameter space corresponding to strong spatial mixing. This allows us to give unified proofs of several recent results of this kind, including the resolution by Peters and Regts of the Sokal conjecture for the partition function of the hard-core lattice gas. It also allows us to prove new results on the location of Lee–Yang zeros of the antiferromagnetic Ising model. We show further that our methods extend to the case when weak spatial mixing on the Bethe lattice is not known to be equivalent to strong spatial mixing on all graphs. In particular, we show that results on strong spatial mixing in the antiferromagnetic Potts model can be lifted to the complex plane to give new zero-freeness results for the associated partition function, significantly sharpening previous results of Sokal and others. This new extension is also of independent algorithmic interest: it allows us to give the first polynomial time deterministic approximation algorithm (a fully polynomial time approximation scheme (FPTAS)) for counting the number of [Formula: see text]-colorings of a graph of maximum degree [Formula: see text] provided only that [Formula: see text], a question that has been studied intensively. This matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. In the case when the graph is also triangle-free, we show that our algorithm applies under the weaker condition [Formula: see text], where [Formula: see text] and [Formula: see text] are absolute constants.

We propose an efficient ɛ-differentially private algorithm, that given a simple weighted n-vertex, m-edge graph G with a maximum unweighted degree Δ(G) ≤ n - 1, outputs a synthetic graph which approximates the spectrum with Õ(min{Δ(G), √n}) bound on the purely additive error. To the best of our knowledge, this is the first ɛ-differentially private algorithm with a non-trivial additive error for approximating the spectrum of the graph. One of our subroutines also precisely simulates the exponential mechanism over a non-convex set, which could be of independent interest given the recent interest in sampling from a log-concave distribution defined over a convex set. As a direct application of our result, we give the first non-trivial bound on approximating all-pairs effective resistances by a synthetic graph, which also implies approximating hitting/commute time and cover time of random walks on the graph. Given the significance of effective resistance in understanding the statistical properties of a graph, we believe our result would have further implications.

We characterize the uniqueness condition in the hardcore model for bipartite graphs with degree bounds only on one side, and provide a nearly linear time sampling algorithm that works up to the uniqueness threshold. We show that the uniqueness threshold for bipartite graph has almost the same form of the tree uniqueness threshold for general graphs, except with degree bounds only on one side of the bipartition. The hardcore model is originated in statistical physics for modeling equilibrium of lattice gas. Combinatorially, it can also be seen as a weighted enumeration of independent sets. Counting the number of independent sets in a bipartite graph (#BIS) is a central open problem in approximate counting. Compared to the same problem in a general graph, surprising tractable regime have been identified that are believed to be hard in general. This is made possible by two lines of algorithmic approach: the high-temperature algorithms starting from Liu and Lu (STOC 2015), and the low-temperature algorithms starting from Helmuth, Perkins, and Regts (STOC 2019).In this work, we study the limit of these algorithms in the high-temperature case. Our characterization of the uniqueness condition is obtained by proving decay of correlations for arguably the best possible regime, which involves locating fixpoints of multivariate iterative rational maps and showing their contraction. Interestingly, we are able to show that a regime that was considered “low-temperature” is actually well within the uniqueness (high-temperature) regime. We also give a nearly linear time sampling algorithm based on simulating field dynamics only on one side of the bipartite graph that works up to the uniqueness threshold. Our algorithm is very different from the original high-temperature algorithm of Liu and Lu (STOC 2015), and it makes use of a connection between correlation decay and spectral independence of Markov chains. Along the way, we also build an explicit connection between the very recent developments of negative-fields stochastic localization schemes and field dynamics. Last but not the least, we are able to show that the standard Glauber dynamics on both side of the bipartite graph mixes in polynomial time up to the uniqueness. Remarkably, this is a model where both the total influence and the spectral radius of the adjacency matrix can be unbounded, yet we are able to prove mixing time bounds through the framework of spectral independence.

We study zeros of the partition functions of ferromagnetic 2-state spin systems in terms of the external field, and obtain new zero-free regions of these systems via a refinement of Asano's and Ruelle's contraction method. The strength of our results is that they do not depend on the maximum degree of the underlying graph. Via Barvinok's method, we also obtain new efficient and deterministic approximate counting algorithms. When the edge interaction is attractive for both spins, our algorithm outperforms all other methods such as Markov chain Monte Carlo and correlation decay.

We give a polynomial time deterministic approximation algorithm (an FPTAS) for counting the number of q-colorings of a graph of maximum degree Delta, provided only that q ≥ 2Delta. This substantially improves on previous deterministic algorithms for this problem, the best of which requires q ≥ 2.58Delta, and matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. In the case when the graph is also triangle-free, we show that our algorithm applies under the weaker condition q ≥ αΔ+β, where α ≈ 1.764 and β = β(α) are absolute constants. Our result applies more generally to list colorings, and to the partition function of the anti-ferromagnetic Potts model. The core of our argument is the establishment of a region in the complex plane in which the Potts model partition function (a classical graph polynomial) has no zeros. This result, which substantially sharpens previous work on the same problem, is of independent interest. Our algorithms follow immediately from zero-freeness via the “polynomial interpolation" method of Barvinok. Interestingly, our method for identifying the zero-free region leverages probabilistic and combinatorial ideas that have been used in the analysis of Markov chains.

The Ising model originated in statistical physics as a means of studying phase transitions in magnets, and has been the object of intensive study for almost a century. Combinatorially, it can be viewed as a natural distribution over cuts in a graph, and it has also been widely studied in computer science, especially in the context of approximate counting and sampling. In this paper, we study the complex zeros of the partition function of the Ising model, viewed as a polynomial in the "interaction parameter"; these are known as Fisher zeros in light of their introduction by Fisher in 1965. While the zeros of the partition function as a polynomial in the "field" parameter have been extensively studied since the classical work of Lee and Yang, comparatively little is known about Fisher zeros. Our main result shows that the zero-field Ising model has no Fisher zeros in a complex neighborhood of the entire region of parameters where the model exhibits correlation decay. In addition to shedding light on Fisher zeros themselves, this result also establishes a formal connection between two distinct notions of phase transition for the Ising model: the absence of complex zeros (analyticity of the free energy, or the logarithm of the partition function) and decay of correlations with distance. We also discuss the consequences of our result for efficient deterministic approximation of the partition function. Our proof relies heavily on algorithmic techniques, notably Weitz's self-avoiding walk tree, and as such belongs to a growing body of work that uses algorithmic methods to resolve classical questions in statistical physics.

Differentially Private algorithms often need to select the best amongst many candidate options. Classical works on this selection problem require that the candidates’ goodness, measured as a real-valued score function, does not change by much when one person’s data changes. In many applications such as hyperparameter optimization, this stability assumption is much too strong. In this work, we consider the selection problem under a much weaker stability assumption on the candidates, namely that the score functions are differentially private. Under this assumption, we present algorithms that are near-optimal along the three relevant dimensions: privacy, utility and computational efficiency.

We propose a new algorithmic framework, called partial rejection sampling , to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds new connections between the variable framework of the Lovász Local Lemma and some classical sampling algorithms such as the cycle-popping algorithm for rooted spanning trees. Among other applications, we discover new algorithms to sample satisfying assignments of k -CNF formulas with bounded variable occurrences.

We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters β (the interaction) and λ (the external field), except for the case |λ| = 1 (the “zero-field” case). A randomized algorithm (FPRAS) for all graphs, and all β, λ, has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the “decay of correlations” property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Our approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.

We propose a new algorithmic framework, called “partial rejection sampling”, to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds (perhaps surprising) new connections between the variable framework of the Lovász Local Lemma and some clas- sical sampling algorithms such as the “cycle-popping” algorithm for rooted spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.

A monotone CNF formula is a Boolean formula in conjunctive normal form where each variable appears positively. We design a deterministic fully polynomial-time approximation scheme (FPTAS) for counting the number of satisfying assignments for a given monotone CNF formula when each variable appears in at most 5 clauses. Equivalently, this is also an FPTAS for counting set covers where each set contains at most 5 elements. If we allow variables to appear in a maximum of 6 clauses (or sets to contain 6 elements), it is NP-hard to approximate it. Thus, this gives a complete understanding of the approximability of counting for monotone CNF formulas. It is also an important step towards a complete characterization of the approximability for all bounded degree Boolean #CSP problems. In addition, we study the hypergraph matching problem, which arises naturally towards a complete classification of bounded degree Boolean #CSP problems, and show an FPTAS for counting 3D matchings of hypergraphs with maximum degree 4. Our main technique is correlation decay, a powerful tool to design deterministic FPTAS for counting problems defined by local constraints among a number of variables. All previous uses of this design technique fall into two categories: each constraint involves at most two variables, such as independent set, coloring, and spin systems in general; or each variable appears in at most two constraints, such as matching, edge cover, and holant problem in general. The CNF problems studied here have more complicated structures than these problems and require new design and proof techniques. As it turns out, the technique we developed for the CNF problem also works for the hypergraph matching problem. We believe that it may also find applications in other CSP or more general counting problems.

Counting the number of independent sets for a bipartite graph (#BIS) plays a crucial role in the study of approximate counting. It has been conjectured that there is no fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for #BIS, and it was proved that the problem for instances with a maximum degree of 6 is already as hard as the general problem. In this paper, we obtain a surprising tractability result for a family of #BIS instances. We design a very simple deterministic fully polynomial-time approximation scheme (FPTAS) for #BIS when the maximum degree for one side is no larger than 5. There is no restriction for the degrees on the other side, which do not even have to be bounded by a constant. Previously, FPTAS was only known for instances with a maximum degree of 5 for both sides.

We study the approximability of computing the partition function for ferromagnetic two-state spin systems. The remarkable algorithm by Jerrum and Sinclair showed that there is a fully polynomial-time randomized approximation scheme (FPRAS) for the special ferromagnetic Ising model with any given uniform external field. Later, Goldberg and Jerrum proved that it is #BIS-hard for Ising model if we allow inconsistent external fields on different nodes. In contrast to these two results, we prove that for any ferromagnetic two-state spin systems except the Ising model, there exists a threshold for external fields beyond which the problem is #BIS-hard, even if the external field is uniform.

An edge cover of a graph is a set of edges such that every vertex has at least an adjacent edge in it. We design a very simple deterministic fully polynomial-time approximation scheme (FPTAS) for counting the number of edge covers for any graph. Previously, approximation algorithm is only known for 3 regular graphs and it is randomized [3]. Our main technique is correlation decay, which is a powerful tool to design FPTAS for counting problems. In order to get FPTAS for general graphs without degree bound, we make use of a stronger notion called computationally efficient correlation decay, which was introduced in [19].