4,639 research outputs found
Approximating Observables Is as Hard as Counting
No full textWe study the computational complexity of estimating local observables for Gibbs distributions. A simple combinatorial example is the average size of an independent set in a graph. A recent work of Galanis et al (2021) established NP-hardness of approximating the average size of an independent set utilizing hardness of the corresponding optimization problem and the related phase transition behavior. We instead consider settings where the underlying optimization problem is easily solvable. Our main contribution is to classify the complexity of approximating a wide class of observables via a generic reduction from approximate counting to the problem of estimating local observables. The key idea is to use the observables to interpolate the counting problem.
Using this new approach, we are able to study observables on bipartite graphs where the underlying optimization problem is easy but the counting problem is believed to be hard. The most-well studied class of graphs that was excluded from previous hardness results were bipartite graphs. We establish hardness for estimating the average size of the independent set in bipartite graphs of maximum degree 6; more generally, we show tight hardness results for general vertex-edge observables for antiferromagnetic 2-spin systems on bipartite graphs. Our techniques go beyond 2-spin systems, and for the ferromagnetic Potts model we establish hardness of approximating the number of monochromatic edges in the same region as known hardness of approximate counting results
One-shot learning for k-SAT
No full textConsider a k-SAT formula Φ where every variable appears at most d times, and let σ be a satisfying assignment of Φ sampled proportionally to e βm(σ) where m(σ) is the number of variables set to true and β is a real parameter. Given Φ and σ, can we learn the value of β efficiently?
This problem falls into a recent line of works about single-sample (“one-shot”) learning of Markov random fields. The k-SAT setting we consider here was recently studied by Galanis, Kandiros, and Kalavasis (SODA’24) where they showed that single-sample learning is possible when roughly d ≤ 2k/6.45 and impossible when d ≥ (k+1)2k−1 . Crucially, for their impossibility results they used the existence of unsatisfiable instances which, aside from the gap in d, left open the question of whether the feasibility threshold for one-shot learning is dictated by the satisfiability threshold of k-SAT formulas of bounded degree.
Our main contribution is to answer this question negatively. We show that one-shot learning for k-SAT is infeasible well below the satisfiability threshold; in fact, we obtain impossibility results for degrees d as low as k2 when β is sufficiently large, and bootstrap this to small values of β when dscales exponentially with k, via a probabilistic construction. On the positive side, we simplify the analysis of the learning algorithm and obtain significantly stronger bounds on d in terms of β. In particular, for the uniform case β → 0 that has been studied extensively in the sampling literature, our analysis shows that learning is possible under the condition d ≲ 2k/2. This is nearly optimal (up to constant factors) in the sense that it is known that sampling a uniformly-distributed satisfying assignment is NP-hard for d ≳ 2k/2
Swendsen-Wang Algorithm on the Mean-Field Potts Model
No full textWe study the q-state ferromagnetic Potts model on the n-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics. The case q=2 (the Swendsen-Wang algorithm for the ferromagnetic Ising model) undergoes a slow-down at the uniqueness/non-uniqueness critical temperature for the infinite Delta-regular tree (Long et al., 2014) but yet still has polynomial mixing time at all (inverse) temperatures beta>0 (Cooper et al., 2000). In contrast for q>=3 there are two critical temperatures 0=beta_rc. These results complement refined results of Cuff et al. (2012) on the mixing time of the Glauber dynamics for the ferromagnetic Potts model. The most interesting aspect of our analysis is at the critical temperature beta=beta_u, which requires a delicate choice of a potential function to balance the conflating factors for the slow drift away from a fixed point (which is repulsive but not Jacobian repulsive): close to the fixed point the variance from the percolation step dominates and sufficiently far from the fixed point the dynamics of the size of the dominant color class takes over
On sampling from Ising models with spectral constraints
No full textWe consider the problem of sampling from the Ising model when the underlying interaction matrix has eigenvalues lying within an interval of length . Recent work in this setting has shown various algorithmic results that apply roughly when 2.
To this end, Kunisky (SODA’24) recently provided evidence that the problem becomes hard already when > 1 based on the low-degree hardness for an inference problem on random matrices. Based on this, he conjectured that sampling from the Ising model in the same range of is NP-hard.
Here we confirm this conjecture, complementing in particular the known algorithmic results by showing NP-hardness results for approximately counting and sampling when > 1, with strong inapproximability guarantees; we also obtain a more refined hardness result for matrices where only a constant number of entries per row are allowed to be non-zero. The main observation in our reductions is that, for > 1, Glauber dynamics mixes slowly when the interactions are all positive (ferromagnetic) for the complete and random regular graphs, due to a bimodality in the underlying distribution. While ferromagnetic interactions typically preclude NP-hardness results, here we work around this by introducing in an appropriate way mild antiferromagnetism, keeping the spectrum roughly within the same range. This allows us to exploit the bimodality of the aforementioned graphs and show the target NPhardness by adapting suitably previous inapproximability techniques developed for antiferromagnetic systems
Fast mixing via polymers for random graphs with unbounded degree
No full textThe polymer model framework is a classical tool from statistical mechanics that has recently been used to obtain approximation algorithms for spin systems on classes of bounded-degree graphs; examples include the ferromagnetic Potts model on expanders and on the grid. One of the key ingredients in the analysis of polymer models is controlling the growth rate of the number of polymers, which has been typically achieved so far by invoking the bounded-degree assumption. Nevertheless, this assumption is often restrictive and obstructs the applicability of the method to more general graphs. For example, sparse random graphs typically have bounded average degree and good expansion properties, but they include vertices with unbounded degree, and therefore are excluded from the current polymer-model framework.
We develop a less restrictive framework for polymer models that relaxes the standard bounded-degree assumption, by reworking the relevant polymer models from the edge perspective. The edge perspective allows us to bound the growth rate of the number of polymers in terms of the total degree of polymers, which in turn can be related more easily to the expansion properties of the underlying graph. To apply our methods, we consider random graphs with unbounded degrees from a fixed degree sequence (with minimum degree at least 3) and obtain approximation algorithms for the ferromagnetic Potts model, which is a standard benchmark for polymer models. Our techniques also extend to more general spin systems
Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems
No full textWe study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language Gamma and a degree bound Delta, we study the complexity of #CSP_Delta(Gamma), which is the problem of counting satisfying assignments to CSP instances with constraints from Gamma and whose variables can appear at most Delta times. Our main result shows that: (i) if every function in Gamma is affine, then #CSP_Delta(Gamma) is in FP for all Delta, (ii) otherwise, if every function in Gamma is in a class called IM_2, then for all sufficiently large Delta, #CSP_Delta(Gamma) is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large Delta, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSP_Delta(Gamma), even within an exponential factor. Our result extends previous results, which apply only in the so-called "conservative" case
Inapproximability of the Independent Set Polynomial Below the Shearer Threshold
No full textWe study the problem of approximately evaluating the independent set polynomial of bounded-degree graphs at a point lambda or, equivalently, the problem of approximating the partition function of the hard-core model with activity lambda on graphs G of max degree D. For lambda>0, breakthrough results of Weitz and Sly established a computational transition from easy to hard at lambda_c(D)=(D-1)^(D-1)/(D-2)^D, which coincides with the tree uniqueness phase transition from statistical physics.
For lambda<0, the evaluation of the independent set polynomial is connected to the conditions of the Lovasz Local Lemma. Shearer identified the threshold lambda*(D)=(D-1)^(D-1)/D^D as the maximum value p such that every family of events with failure probability at most p and whose dependency graph has max degree D has nonempty intersection. Very recently, Patel and Regts, and Harvey et al. have independently designed FPTASes for approximating the partition function whenever |lambda|<lambda*(D).
Our main result establishes for the first time a computational transition at the Shearer threshold. We show that for all D>=3, for all lambda-lambda*(D), establishes a phase transition for negative activities. In fact, we now have the following picture for the problem of approximating the partition function with activity lambda on graphs G of max degree D.
1. For -lambda*(D)<lambda<lambda_c(D), the problem admits an FPTAS.
2. For lambdalambda_c(D), the problem is NP-hard.
Rather than the tree uniqueness threshold of the positive case, the phase transition for negative activities corresponds to the existence of zeros for the partition function of the tree below -lambda*(D)
A complexity trichotomy for approximately counting list H-colourings
No full textWe examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph then approximately counting list H-colourings is equivalent to #BIS, the problem of approximately counting independent sets in a bipartite graph. This is a well-studied problem which is believed to be of intermediate complexity – it is believed that it does not have an FPRAS, but that it is not as difficult as approximating the most difficult counting problems in #P. For every other graph H, approximately counting list H-colourings is complete for #P with respect to approximation-preserving reductions (so there is no FPRAS unless NP = RP). Two pleasing features of the trichotomy are (i) it has a natural formulation in terms of hereditary graph classes, and (ii) the proof is largely self-contained and does not require any universal algebra (unlike similar dichotomies in the weighted case). We are able to extend the hardness results to the bounded-degree setting, showing that all hardness results apply to input graphs with maximum degree at most 6
The Complexity of Approximating the Complex-Valued Potts Model
No full textWe study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane.
Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations
Regional Microglial Response in Entorhino-Hippocampal Slice Cultures to Schaffer Collateral Lesion and Metalloproteinases Modulation
No full text- …
