BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Andreas Galanis

Andreas Galanis appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityDiscrete Mathematicsmath.PRData Structures and Algorithmsmath-phmath.COmath.MPPopulations and EvolutionSocial and Information Networks

Catalog footprint

What is connected

17works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

17 published item(s)

preprint2022arXiv

Approximating observables is as hard as counting

We 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. In a recent work, we 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. Here, 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fast mixing via polymers for random graphs with unbounded degree

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Inapproximability of counting hypergraph colourings

Recent developments in approximate counting have made startling progress in developing fast algorithmic methods for approximating the number of solutions to constraint satisfaction problems (CSPs) with large arities, using connections to the Lovasz Local Lemma. Nevertheless, the boundaries of these methods for CSPs with non-Boolean domain are not well-understood. Our goal in this paper is to fill in this gap and obtain strong inapproximability results by studying the prototypical problem in this class of CSPs, hypergraph colourings. More precisely, we focus on the problem of approximately counting $q$-colourings on $K$-uniform hypergraphs with bounded degree $Δ$. An efficient algorithm exists if $Δ\lesssim \frac{q^{K/3-1}}{4^KK^2}$ (Jain, Pham, and Vuong, 2021; He, Sun, and Wu, 2021). Somewhat surprisingly however, a hardness bound is not known even for the easier problem of finding colourings. For the counting problem, the situation is even less clear and there is no evidence of the right constant controlling the growth of the exponent in terms of $K$. To this end, we first establish that for general $q$ computational hardness for finding a colouring on simple/linear hypergraphs occurs at $Δ\gtrsim Kq^K$, almost matching the algorithm from the Lovasz Local Lemma. Our second and main contribution is to obtain a far more refined bound for the counting problem that goes well beyond the hardness of finding a colouring and which we conjecture that is asymptotically tight (up to constant factors). We show in particular that for all even $q\geq 4$ it is NP-hard to approximate the number of colourings when $Δ\gtrsim q^{K/2}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The complexity of approximating the complex-valued Ising model on bounded degree graphs

We study the complexity of approximating the partition function $Z_{\mathrm{Ising}}(G; β)$ of the Ising model in terms of the relation between the edge interaction $β$ and a parameter $Δ$ which is an upper bound on the maximum degree of the input graph $G$. Following recent trends in both statistical physics and algorithmic research, we allow the edge interaction $β$ to be any complex number. Many recent partition function results focus on complex parameters, both because of physical relevance and because of the key role of the complex case in delineating the tractability/intractability phase transition of the approximation problem. In this work we establish both new tractability results and new intractability results. Our tractability results show that $Z_{\mathrm{Ising}}(-; β)$ has an FPTAS when $\lvert β- 1 \rvert / \lvert β+ 1 \rvert < \tan(π/ (4 Δ- 4))$. The core of the proof is showing that there are no inputs~$G$ that make the partition function $0$ when $β$ is in this range. Our result significantly extends the known zero-free region of the Ising model (and hence the known approximation results). Our intractability results show that it is $\mathrm{\#P}$-hard to multiplicatively approximate the norm and to additively approximate the argument of $Z_{\mathrm{Ising}}(-; β)$ when $β\in \mathbb{C}$ is an algebraic number such that $β\not \in \mathbb{R} \cup \{i,-i\}$ and $\lvert β- 1\rvert / \lvert β+ 1 \rvert > 1 / \sqrt{Δ- 1}$. These are the first results to show intractability of approximating $Z_{\mathrm{Ising}}(-, β)$ on bounded degree graphs with complex $β$. Moreover, we demonstrate situations in which zeros of the partition function imply hardness of approximation in the Ising model.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

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

We study the computational complexity of approximating the partition function of the ferromagnetic Ising model with the external field parameter $λ$ on the unit circle in the complex plane. 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 $|λ|\neq 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 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$, and more generally on the entire unit circle. For an integer $Δ\geq 3$ and edge interaction parameter $b\in (0,1)$ we show #P-hardness for approximating the partition function on graphs of maximum degree $Δ$ on the arc of the unit circle where the Lee-Yang zeros are dense. This result contrasts with known approximation algorithms when $|λ|\neq 1$ or when $λ$ is in the complementary arc around $1$ of the unit circle. Our work thus gives a direct connection between the presence/absence of Lee-Yang zeros and the tractability of efficiently approximating the partition function on bounded-degree graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

The complexity of approximating the matching polynomial in the complex plane

We study the problem of approximating the value of the matching polynomial on graphs with edge parameter $γ$, where $γ$ takes arbitrary values in the complex plane. When $γ$ is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of $γ$, Patel and Regts, building on methods developed by Barvinok, showed that the problem admits an FPTAS on graphs of maximum degree $Δ$ as long as $γ$ is not a negative real number less than or equal to $-1/(4(Δ-1))$. Our first main result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all $Δ\geq 3$ and all real $γ$ less than $-1/(4(Δ-1))$, the problem of approximating the value of the matching polynomial on graphs of maximum degree $Δ$ with edge parameter $γ$ is #P-hard. We then explore whether the maximum degree parameter can be replaced by the connective constant. Sinclair et al. showed that for positive real $γ$ it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this result does not extend in general in the complex plane; in particular, the problem is #P-hard on graphs with bounded connective constant for a dense set of $γ$ values on the negative real axis. Nevertheless, we show that the result does extend for any complex value $γ$ that does not lie on the negative real axis. Our analysis accounts for complex values of $γ$ using geodesic distances in the complex plane in the metric defined by an appropriate density function.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems

We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language $Γ$ and a degree bound $Δ$, we study the complexity of #CSP$_Δ(Γ)$, which is the problem of counting satisfying assignments to CSP instances with constraints from $Γ$ and whose variables can appear at most $Δ$ times. Our main result shows that: (i) if every function in $Γ$ is affine, then #CSP$_Δ(Γ)$ is in FP for all $Δ$, (ii) otherwise, if every function in $Γ$ is in a class called IM$_2$, then for all sufficiently large $Δ$, #CSP$_Δ(Γ)$ 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 $Δ$, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSP$_Δ(Γ)$, even within an exponential factor. Our result extends previous results, which apply only in the so-called "conservative" case.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Random Walks on Small World Networks

We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices $\{u,v\}$ with distance $d>1$ is added as a "long-range" edge with probability proportional to $d^{-r}$, where $r\geq 0$ is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the (decentralised) routing time is $O((\log n)^2)$ when $r=2$ and $n^{Ω(1)}$ when $r\neq 2$. Here, we prove that the random walk also undergoes a phase transition at $r=2$, but in this case the phase transition is of a different form. We establish that the mixing time is $Θ(\log n)$ for $r<2$, $O((\log n)^4)$ for $r=2$ and $n^{Ω(1)}$ for $r>2$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rapid Mixing for Colorings via Spectral Independence

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 $α^*\approx 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\geqαΔ+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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Amplifiers for the Moran Process

The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen u.a.r.) possesses a mutation, with fitness r>1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or non-mutant) is passed on to an out-neighbour which is chosen u.a.r. If the underlying graph is strongly connected then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r>1, the extinction probability tends to 0 as the number of vertices increases. Lieberman et al. proposed two potentially strongly-amplifying families - superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this paper, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars". When the algorithm is run on an n-vertex graph in this family, starting with a uniformly-chosen mutant, the extinction probability is roughly $n^{-1/2}$ (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results

Recent results establish for 2-spin antiferromagnetic systems that the computational complexity of approximating the partition function on graphs of maximum degree D undergoes a phase transition that coincides with the uniqueness phase transition on the infinite D-regular tree. For the ferromagnetic Potts model we investigate whether analogous hardness results hold. Goldberg and Jerrum showed that approximating the partition function of the ferromagnetic Potts model is at least as hard as approximating the number of independent sets in bipartite graphs (#BIS-hardness). We improve this hardness result by establishing it for bipartite graphs of maximum degree D. We first present a detailed picture for the phase diagram for the infinite D-regular tree, giving a refined picture of its first-order phase transition and establishing the critical temperature for the coexistence of the disordered and ordered phases. We then prove for all temperatures below this critical temperature that it is #BIS-hard to approximate the partition function on bipartite graphs of maximum degree D. As a corollary, it is #BIS-hard to approximate the number of k-colorings on bipartite graphs of maximum degree D when k <= D/(2 ln D). The #BIS-hardness result for the ferromagnetic Potts model uses random bipartite regular graphs as a gadget in the reduction. The analysis of these random graphs relies on recent connections between the maxima of the expectation of their partition function, attractive fixpoints of the associated tree recursions, and induced matrix norms. We extend these connections to random regular graphs for all ferromagnetic models and establish the Bethe prediction for every ferromagnetic spin system on random regular graphs. We also prove for the ferromagnetic Potts model that the Swendsen-Wang algorithm is torpidly mixing on random D-regular graphs at the critical temperature for large q.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models

Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006) establish a beautiful picture for the computational complexity of approximating the partition function of the hard-core model. Let $λ_c(T_Δ)$ denote the critical activity for the hard-model on the infinite $Δ$-regular tree. Weitz presented an FPTAS for the partition function when $λ<λ_c(T_Δ)$ for graphs with constant maximum degree $Δ$. In contrast, Sly showed that for all $Δ\geq 3$, there exists $ε_Δ>0$ such that (unless RP=NP) there is no FPRAS for approximating the partition function on graphs of maximum degree $Δ$ for activities $λ$ satisfying $λ_c(T_Δ)<λ<λ_c(T_Δ)+ε_Δ$. We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Recent results of Li et al. and Sinclair et al. extend Weitz's approach to any 2-spin model, which includes the antiferromagnetic Ising model, to yield an FPTAS for the partition function for all graphs of constant maximum degree $Δ$ when the parameters of the model lie in the uniqueness regime of the infinite tree $T_Δ$. We prove the complementary result that for the antiferrogmanetic Ising model without external field that, unless RP=NP, for all $Δ\geq 3$, there is no FPRAS for approximating the partition function on graphs of maximum degree $Δ$ when the inverse temperature lies in the non-uniqueness regime of the infinite tree $T_Δ$. Our results extend to a region of the parameter space for general 2-spin models. Our proof works by relating certain second moment calculations for random $Δ$-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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

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 $Δ\geq Δ_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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region

Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to approximate. We study #BIS in the general framework of two-state spin systems on bipartite graphs. We define two notions, nearly-independent phase-correlated spins and unary symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any 2-spin system on bipartite graphs supporting these two notions. As a consequence, we classify the complexity of approximating the partition function of antiferromagnetic 2-spin systems on bounded-degree bipartite graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Approximately Counting H-Colourings is #BIS-Hard

We consider the problem of counting H-colourings from an input graph G to a target graph H. We show that if H is any fixed graph without trivial components, then the problem is as hard as the well-known problem #BIS, which is the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in an important complexity class for approximate counting, and is believed not to have an FPRAS. If this is so, then our result shows that for every graph H without trivial components, the H-colouring counting problem has no FPRAS. This problem was studied a decade ago by Goldberg, Kelk and Paterson. They were able to show that approximately sampling H-colourings is #BIS-hard, but it was not known how to get the result for approximate counting. Our solution builds on non-constructive ideas using the work of Lovasz.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region

A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree D undergoes a phase transition that coincides with the statistical physics uniqueness/non-uniqueness phase transition on the infinite D-regular tree. Despite this clear picture for 2-spin systems, there is little known for multi-spin systems. We present the first analog of the above inapproximability results for multi-spin systems. The main difficulty in previous inapproximability results was analyzing the behavior of the model on random D-regular bipartite graphs, which served as the gadget in the reduction. To this end one needs to understand the moments of the partition function. Our key contribution is connecting: (i) induced matrix norms, (ii) maxima of the expectation of the partition function, and (iii) attractive fixed points of the associated tree recursions (belief propagation). The view through matrix norms allows a simple and generic analysis of the second moment for any spin system on random D-regular bipartite graphs. This yields concentration results for any spin system in which one can analyze the maxima of the first moment. The connection to fixed points of the tree recursions enables an analysis of the maxima of the first moment for specific models of interest. For k-colorings we prove that for even k, in the tree non-uniqueness region (which corresponds to k<D) it is NP-hard, unless NP=RP, to approximate the number of colorings for triangle-free D-regular graphs. Our proof extends to the antiferromagnetic Potts model, and, in fact, to every antiferromagnetic model under a mild condition.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model

We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Delta. More generally, for an input graph G=(V,E) and an activity lambda>0, we are interested in the quantity Z_G(lambda) defined as the sum over independent sets I weighted as w(I) = lambda^|I|. In statistical physics, Z_G(lambda) is the partition function for the hard-core model, which is an idealized model of a gas where the particles have non-negibile size. Recently, an interesting phase transition was shown to occur for the complexity of approximating the partition function. Weitz showed an FPAS for the partition function for any graph of maximum degree Delta when Delta is constant and lambda< lambda_c(Tree_Delta):=(Delta-1)^(Delta-1)/(Delta-2)^Delta. The quantity lambda_c(Tree_Delta) is the critical point for the so-called uniqueness threshold on the infinite, regular tree of degree Delta. On the other side, Sly proved that there does not exist efficient (randomized) approximation algorithms for lambda_c(Tree_Delta) < lambda < lambda_c(Tree_Delta)+epsilon(Delta), unless NP=RP, for some function epsilon(Delta)>0. We remove the upper bound in the assumptions of Sly's result for Delta not equal to 4 and 5, that is, we show that there does not exist efficient randomized approximation algorithms for all lambda>lambda_c(Tree_Delta) for Delta=3 and Delta>= 6. Sly's inapproximability result uses a clever reduction, combined with a second-moment analysis of Mossel, Weitz and Wormald which prove torpid mixing of the Glauber dynamics for sampling from the associated Gibbs distribution on almost every regular graph of degree Delta for the same range of lambda as in Sly's result. We extend Sly's result by improving upon the technical work of Mossel et al., via a more detailed analysis of independent sets in random regular graphs.

0 citations0 reviewsNo code linkedOpen access