Andreas Galanis

I&C Journal 2025 Journal Article

One-shot learning for k-SAT

• Andreas Galanis
• Leslie Ann Goldberg
• Xusheng Zhang

Consider a k-SAT formula Φ where every variable appears at most d times. Let σ be a satisfying assignment, sampled proportionally to e β m ( σ ) where m ( σ ) is the number of true variables and β is a real parameter. Given Φ and σ, can we efficiently learn β? This problem falls into a recent line of work about single-sample (“one-shot”) learning of Markov random fields. Our k-SAT setting was recently studied by Galanis, Kalavasis, Kandiros (SODA24). They showed that single-sample learning is possible when roughly d ≤ 2 k / 6. 45 and impossible when d ≥ ( k + 1 ) 2 k − 1. In addition to the gap in d, their impossibility result left open the question of whether the feasibility threshold for one-shot learning is dictated by the satisfiability threshold for bounded-degree k-SAT formulas. 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 k 2 when β is sufficiently large, and bootstrap this to small values of β when d scales exponentially with k, via a probabilistic construction. On the positive side, we simplify the analysis of the learning algorithm, obtaining significantly stronger bounds on d in terms of β. For the uniform case β → 0, we show that learning is possible under the condition d ≲ 2 k / 2. This is (up to constant factors) all the way to the sampling threshold – it is known that sampling a uniformly-distributed satisfying assignment is NP-hard for d ≳ 2 k / 2.

SODA Conference 2024 Conference Paper

Learning Hard-Constrained Models with One Sample

• Andreas Galanis
• Alkis Kalavasis
• Anthimos Vardis Kandiros

TCS Journal 2023 Journal Article

Implementations and the independent set polynomial below the Shearer threshold

• Andreas Galanis
• Leslie Ann Goldberg
• Daniel Štefankovič

The independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer Δ ≥ 2, the Shearer threshold is the value λ ⁎ ( Δ ) = ( Δ − 1 ) Δ − 1 / Δ Δ. It is known that for λ < − λ ⁎ ( Δ ), there are graphs G with maximum degree Δ whose independent set polynomial, evaluated at λ, is at most 0. Also, there are no such graphs for any λ > − λ ⁎ ( Δ ). This paper is motivated by the computational problem of approximating the independent set polynomial when λ < − λ ⁎ ( Δ ). The key issue in complexity bounds for this problem is “implementation”. Informally, an implementation of a real number λ ′ is a graph whose hard-core partition function, evaluated at λ, simulates a vertex-weight of λ ′ in the sense that λ ′ is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any λ < − λ ⁎ ( Δ ), it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any λ > λ ⁎ ( Δ ). Our result has already been used in a paper with Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most Δ at any value λ < − λ ⁎ ( Δ ). In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NP-hardness).

I&C Journal 2022 Journal Article

Fast mixing via polymers for random graphs with unbounded degree

• Andreas Galanis
• Leslie Ann Goldberg
• James Stewart

The 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.

SODA Conference 2022 Conference Paper

Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region

• Zongchen Chen
• Andreas Galanis
• Daniel Stefankovic
• Eric Vigoda

We give an FPRAS for counting q -colorings for even on almost every Δ-regular bipartite graph. This improves significantly upon the previous best bound of by Jenssen, Keevash, and Perkins (SODA'19). Analogously, for the hard-core model on independentsets weighted by λ > 0, we present an FPRAS for estimating the partition function when, which improves upon previous results by an Ω(log Δ) factor. Our results for the colorings and hard-core models follow from a general result that applies to arbitrary spin systems. Our main contribution is to show how to elevate probabilistic/analytic bounds on the marginal probabilities for the typical structure of phases on random bipartite regular graphs into efficient algorithms, using the polymer method. We further show evidence that our results for colorings and independent sets are within a constant factor of best possible using current polymer-method approaches.

SODA Conference 2021 Conference Paper

Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs

• Pjotr Buys
• Andreas Galanis
• Viresh Patel
• Guus Regts

We study the computational complexity of approximating the partition function of the ferromagnetic Ising model in the Lee-Yang circle of zeros given by |λ| = 1, where λ is the external field of the model. Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics, but have also been key in the recent deterministic approximation scheme for all |λ| ≠ 1 by Liu, Sinclair, and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle, and on the tantalising question of what happens in the circular arc around λ = 1, where on one hand the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability, and on the other hand the presence of Lee-Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point λ = 1; in fact, our techniques apply more generally to the whole unit circle |λ| = 1. We show #P-hardness for approximating the partition function on graphs of maximum degree Δ when b, the edge-interaction parameter, is in the interval and λ is a non-real on the unit circle. This result contrasts with known approximation algorithms when, and shows that the Lee-Yang circle of zeros is computationally intractable, even on bounded-degree graphs. Our inapproximability result is based on constructing rooted tree gadgets via a detailed understanding of the underlying dynamical systems, which are further parameterised by the degree of the root. The ferromagnetic Ising model has radically different behaviour than previously considered anti-ferromagnetic models, and showing our #P-hardness results in the whole Lee-Yang circle requires a new high-level strategy to construct the gadgets. To this end, we devise an elaborate inductive procedure to construct the required gadgets by taking into account the dependence between the degree of the root of the tree and the magnitude of the derivative at the fixpoint of the corresponding dynamical system. The full version (with all proofs) is available on arXiv at arxiv. org/abs/2006. 14828.

SODA Conference 2021 Conference Paper

Rapid Mixing for Colorings via Spectral Independence

• Zongchen Chen
• Andreas Galanis
• Daniel Stefankovic
• Eric Vigoda

The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber dynamics for the hard-core model defined on weighted independent sets. We develop the spectral independence approach for colorings, and obtain new algorithmic results for the corresponding counting/sampling problems. Let α ∗ ≈ 1. 763 denote the solution to exp(1/ x ) = x and let α > α ∗. We prove that, for any triangle-free graph G = ( V, E ) with maximum degree Δ, for all q ≥ α Δ + 1, the mixing time of the Glauber dynamics for q -colorings is polynomial in n = |V|, with the exponent of the polynomial independent of Δ and q. In comparison, previous approximate counting results for colorings held for a similar range of q (asymptotically in Δ) but with larger girth requirement or with a running time where the polynomial exponent depended on Δ and q (exponentially). One further feature of using the spectral independence approach to study colorings is that it avoids many of the technical complications in previous approaches caused by coupling arguments or by passing to the complex plane; the key improvement on the running time is based on relatively simple combinatorial arguments which are then translated into spectral bounds.

MFCS Conference 2020 Conference Paper

Fast Algorithms for General Spin Systems on Bipartite Expanders

• Andreas Galanis
• Leslie Ann Goldberg
• James Stewart 0001

A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assignment can also be viewed as a weighted graph homomorphism. The problem of approximating the partition function (the aggregate weight of spin assignments) or of sampling from the resulting probability distribution is typically intractable for general graphs. In this work, we consider arbitrary spin systems on bipartite expander Δ-regular graphs, including the canonical class of bipartite random Δ-regular graphs. We develop fast approximate sampling and counting algorithms for general spin systems whenever the degree and the spectral gap of the graph are sufficiently large. Our approach generalises the techniques of Jenssen et al. and Chen et al. by showing that typical configurations on bipartite expanders correspond to "bicliques" of the spin system; then, using suitable polymer models, we show how to sample such configurations and approximate the partition function in Õ(n²) time, where n is the size of the graph.

FOCS Conference 2020 Conference Paper

The complexity of approximating averages on bounded-degree graphs

• Andreas Galanis
• Daniel Stefankovic
• Eric Vigoda

We prove that, unless P=NP, there is no polynomial-time algorithm to approximate within some multiplicative constant the average size of an independent set in graphs of maximum degree 6. This is a special case of a more general result for the hard-core model defined on independent sets weighted by a parameter. In the general setting, we prove that, unless P=NP, for all Δ ≥ 3, all, there is no FPTAS which applies to all graphs of maximum degree Δ for computing the average size of the independent set in the Gibbs distribution, where λ c (Δ) is the critical point for the uniqueness/non-uniqueness phase transition on the Δ-regular tree. Moreover, we prove that for λ in a dense set of this non-uniqueness region the problem is NP-hard to approximate within some constant factor. Our work extends to the antiferromagnetic Ising model and generalizes to all 2-spin antiferromagnetic models, establishing hardness of computing the average magnetization in the tree non-uniqueness region. Previously, Schulman, Sinclair and Srivastava (2015) showed that it is #P-hard to compute the average magnetization exactly, but no hardness of approximation results were known. Hardness results of Sly (2010) and Sly and Sun (2014) for approximating the partition function do not imply hardness of computing averages. The new ingredient in our reduction is an intricate construction of pairs of rooted trees whose marginal distributions at the root agree but their derivatives disagree. The main technical contribution is controlling what marginal distributions and derivatives are achievable and using Cauchy's functional equation to argue existence of the gadgets. The full version of this paper with detailed proofs to all lemmas and theorems can be found out at https: //arxiv. org/abs/2004. 09238.

MFCS Conference 2020 Conference Paper

The Complexity of Approximating the Complex-Valued Potts Model

• Andreas Galanis
• Leslie Ann Goldberg
• Andrés Herrera-Poyatos

We 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.

STOC Conference 2018 Conference Paper

Inapproximability of the independent set polynomial in the complex plane

• Ivona Bezáková
• Andreas Galanis
• Leslie Ann Goldberg
• Daniel Stefankovic

We study the complexity of approximating the value of the independent set polynomial Z G (λ) of a graph G with maximum degree Δ when the activity λ is a complex number. When λ is real, the complexity picture is well-understood, and is captured by two real-valued thresholds λ * and λ c , which depend on Δ and satisfy 0 0, resolving in the affirmative a conjecture of Harvey, Srivastava and Vondrak. Our proof techniques are based around tools from complex analysis — specifically the study of iterative multivariate rational maps.

SODA Conference 2016 Conference Paper

The complexity of approximately counting in 2-spin systems on k -uniform bounded-degree hypergraphs

• Andreas Galanis
• Leslie Ann Goldberg

One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-called uniqueness phase transition from statistical physics on the infinite Δ-regular tree. Our objective is to study the impact of this classification on unweighted 2-spin models on k -uniform hypergraphs. As has already been indicated by Yin and Zhao, the connection between the uniqueness phase transition and the complexity of approximate counting breaks down in the hypergraph setting. Nevertheless, we show that for every non-trivial symmetric k -ary Boolean function f there exists a degree bound Δ 0 so that for all Δ ≥ Δ 0 the following problem is NP-hard: given a k -uniform hypergraph with maximum degree at most Δ, approximate the partition function of the hypergraph 2-spin model associated with f. It is NP-hard to approximate this partition function even within an exponential factor. By contrast, if f is a trivial symmetric Boolean function (e. g. , any function f that is excluded from our result), then the partition function of the corresponding hypergraph 2-spin model can be computed exactly in polynomial time. The full version of this paper is available at arxiv. org/abs/1505. 06146. For the convenience of the reader, we have also included in the theorem statements the number of the respective theorem in the full version.

I&C Journal 2016 Journal Article

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

• Andreas Galanis
• Leslie Ann Goldberg

One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-called uniqueness phase transition from statistical physics on the infinite Δ-regular tree. Our objective is to study the impact of this classification on unweighted 2-spin models on k-uniform hypergraphs. As has already been indicated by Yin and Zhao, the connection between the uniqueness phase transition and the complexity of approximate counting breaks down in the hypergraph setting. Nevertheless, we show that for every non-trivial symmetric k-ary Boolean function f there exists a degree bound Δ 0 so that for all Δ ≥ Δ 0 the following problem is NP -hard: given a k-uniform hypergraph with maximum degree at most Δ, approximate the partition function of the hypergraph 2-spin model associated with f. It is NP -hard to approximate this partition function even within an exponential factor. By contrast, if f is a trivial symmetric Boolean function (e. g. , any function f that is excluded from our result), then the partition function of the corresponding hypergraph 2-spin model can be computed exactly in polynomial time.

STOC Conference 2014 Conference Paper

Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region

• Andreas Galanis
• Daniel Stefankovic
• Eric Vigoda