BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Leslie Ann Goldberg

Leslie Ann Goldberg contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational Complexitymath.CODiscrete MathematicsData Structures and Algorithmsmath.PRComputational Engineering, Finance, and ScienceComputer Science and Game TheoryPopulations and EvolutionSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
31works
0followers
9topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

31 published item(s)

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

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

Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2

We study the problem of computing the parity of the number of homomorphisms from an input graph $G$ to a fixed graph $H$. Faben and Jerrum [ToC&#39;15] introduced an explicit criterion on the graph $H$ and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class $\oplus\mathrm{P}$ of parity problems. We verify their conjecture for all graphs $H$ that exclude the complete graph on $4$ vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the $\oplus\mathrm{P}$-complete cases, assuming the randomised Exponential Time Hypothesis. Our proofs introduce a novel method of deriving hardness from globally defined substructures of the fixed graph $H$. Using this, we subsume all prior progress towards resolving the conjecture (Faben and Jerrum [ToC&#39;15]; Göbel, Goldberg and Richerby [ToCT&#39;14,&#39;16]). As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most $3$, as well as a full classification for the problem of counting list homomorphisms, modulo $2$.

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 &#34;conservative&#34; 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 &#34;long-range&#34; 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

The Complexity of Approximately Counting Retractions

Let $G$ be a graph that contains an induced subgraph $H$. A retraction from $G$ to $H$ is a homomorphism from $G$ to $H$ that is the identity function on $H$. Retractions are very well-studied: Given $H$, the complexity of deciding whether there is a retraction from an input graph $G$ to $H$ is completely classified, in the sense that it is known for which $H$ this problem is tractable (assuming $\mathrm{P}\neq \mathrm{NP}$). Similarly, the complexity of (exactly) counting retractions from $G$ to $H$ is classified (assuming $\mathrm{FP}\neq \#\mathrm{P}$). However, almost nothing is known about approximately counting retractions. Our first contribution is to give a complete trichotomy for approximately counting retractions to graphs of girth at least $5$. Our second contribution is to locate the retraction counting problem for each $H$ in the complexity landscape of related approximate counting problems. Interestingly, our results are in contrast to the situation in the exact counting context. We show that the problem of approximately counting retractions is separated both from the problem of approximately counting homomorphisms and from the problem of approximately counting list homomorphisms --- whereas for exact counting all three of these problems are interreducible. We also show that the number of retractions is at least as hard to approximate as both the number of surjective homomorphisms and the number of compactions. In contrast, exactly counting compactions is the hardest of all of these exact counting problems.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin

We analyse the complexity of approximate counting constraint satisfactions problems $\mathrm{\#CSP}(\mathcal{F})$, where $\mathcal{F}$ is a set of nonnegative rational-valued functions of Boolean variables. A complete classification is known in the conservative case, where $\mathcal{F}$ is assumed to contain arbitrary unary functions. We strengthen this result by fixing any permissive strictly increasing unary function and any permissive strictly decreasing unary function, and adding only those to $\mathcal{F}$: this is weak conservativity. The resulting classification is employed to characterise the complexity of a wide range of two-spin problems, fully classifying the ferromagnetic case. In a further weakening of conservativity, we also consider what happens if only the pinning functions are assumed to be in $\mathcal{F}$ (instead of the two permissive unaries). We show that any set of functions for which pinning is not sufficient to recover the two kinds of permissive unaries must either have a very simple range, or must satisfy a certain monotonicity condition. We exhibit a non-trivial example of a set of functions satisfying the monotonicity condition.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Counting list matrix partitions of graphs

Given a symmetric D*D matrix M over {0,1,*}, a list M-partition of a graph G is a partition of G&#39;s vertices into D parts associated with the rows of M. The part of each vertex is chosen from a given list so that no edge of G maps to a 0 in M and no non-edge of G maps to a 1 in M. Many important graph-theoretic structures can be represented as list M-partitions, such as graph colourings, split graphs and homogeneous sets and pairs, which arise in the proofs of the weak and strong perfect graph conjectures. There has been quite a bit of work on determining for which matrices M computations involving list M-partitions are tractable. We focus on counting list M-partitions, given a graph G and a list for each vertex of G. We identify a set of &#34;tractable&#34; matrices and give an algorithm that counts list M-partitions in polynomial time for every (fixed) matrix M in this set. The algorithm uses data structures such as sparse-dense partitions and subcube decompositions to reduce each instance to a sequence of instances in which the lists restrict access to portions of M in which the interaction of 0s and 1s is controlled. We solve the resulting restricted instances by converting them into counting constraint satisfaction problems (#CSPs) which we solve using arc-consistency. For every matrix M for which our algorithm fails, we show that counting list M-partitions is #P-complete. Further, we give an explicit characterisation of the dichotomy theorem: counting list M-partitions is in FP if M has a structure called a derectangularising sequence; otherwise, counting list M-partitions is #P-hard. We show that the meta-problem of determining whether a given matrix has a derectangularising sequence is NP-complete. Finally, we show that lists can be used to encode cardinality restrictions in M-partitions problems and use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Absorption Time of the Moran Process

The Moran process models the spread of mutations in populations on graphs. We investigate the absorption time of the process, which is the time taken for a mutation introduced at a randomly chosen vertex to either spread to the whole population, or to become extinct. It is known that the expected absorption time for an advantageous mutation is O(n^4) on an n-vertex undirected graph, which allows the behaviour of the process on undirected graphs to be analysed using the Markov chain Monte Carlo method. We show that this does not extend to directed graphs by exhibiting an infinite family of directed graphs for which the expected absorption time is exponential in the number of vertices. However, for regular directed graphs, we show that the expected absorption time is Omega(n log n) and O(n^2). We exhibit families of graphs matching these bounds and give improved bounds for other families of graphs, based on isoperimetric number. Our results are obtained via stochastic dominations which we demonstrate by establishing a coupling in a related continuous-time model. The coupling also implies several natural domination results regarding the fixation probability of the original (discrete-time) process, resolving a conjecture of Shakarian, Roos and Johnson.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Approximating Fixation Probabilities in the Generalized Moran Process

We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned &#39;fitness&#39; value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness $r>0$ placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when $r\geq 1$) and of extinction (for all $r>0$).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Approximating the partition function of planar two-state spin systems

We consider the problem of approximating the partition function of the hard-core model on planar graphs of degree at most 4. We show that when the activity lambda is sufficiently large, there is no fully polynomial randomised approximation scheme for evaluating the partition function unless NP=RP. The result extends to a nearby region of the parameter space in a more general two-state spin system with three parameters. We also give a polynomial-time randomised approximation scheme for the logarithm of the partition function.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Complexity of Approximately Counting Tree Homomorphisms

We study two computational problems, parameterised by a fixed tree H. #HomsTo(H) is the problem of counting homomorphisms from an input graph G to H. #WHomsTo(H) is the problem of counting weighted homomorphisms to H, given an input graph G and a weight function for each vertex v of G. Even though H is a tree, these problems turn out to be sufficiently rich to capture all of the known approximation behaviour in #P. We give a complete trichotomy for #WHomsTo(H). If H is a star then #WHomsTo(H) is in FP. If H is not a star but it does not contain a certain induced subgraph J_3 then #WHomsTo(H) is equivalent under approximation-preserving (AP) reductions to #BIS, the problem of counting independent sets in a bipartite graph. This problem is complete for the class #RHPi_1 under AP-reductions. Finally, if H contains an induced J_3 then #WHomsTo(H) is equivalent under AP-reductions to #SAT, the problem of counting satisfying assignments to a CNF Boolean formula. Thus, #WHomsTo(H) is complete for #P under AP-reductions. The results are similar for #HomsTo(H) except that a rich structure emerges if H contains an induced J_3. We show that there are trees H for which #HomsTo(H) is #SAT-equivalent (disproving a plausible conjecture of Kelk). There is an interesting connection between these homomorphism-counting problems and the problem of approximating the partition function of the ferromagnetic Potts model. In particular, we show that for a family of graphs J_q, parameterised by a positive integer q, the problem #HomsTo(H) is AP-interreducible with the problem of approximating the partition function of the q-state Potts model. It was not previously known that the Potts model had a homomorphism-counting interpretation. We use this connection to obtain some additional upper bounds for the approximation complexity of #HomsTo(J_q).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The complexity of approximating conservative counting CSPs

We study the complexity of approximately solving the weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, there is a classification known for the case in which the domain of functions in F is Boolean. In this paper, we give a classification for the more general problem where functions in F have an arbitrary finite domain. We define the notions of weak log-modularity and weak log-supermodularity. We show that if F is weakly log-modular, then #CSP(F)is in FP. Otherwise, it is at least as difficult to approximate as #BIS, the problem of counting independent sets in bipartite graphs. #BIS is complete with respect to approximation-preserving reductions for a logically-defined complexity class #RHPi1, and is believed to be intractable. We further sub-divide the #BIS-hard case. If F is weakly log-supermodular, then we show that #CSP(F) is as easy as a (Boolean) log-supermodular weighted #CSP. Otherwise, we show that it is NP-hard to approximate. Finally, we give a full trichotomy for the arity-2 case, where #CSP(F) is in FP, or is #BIS-equivalent, or is equivalent in difficulty to #SAT, the problem of approximately counting the satisfying assignments of a Boolean formula in conjunctive normal form. We also discuss the algorithmic aspects of our classification.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Complexity of Computing the Sign of the Tutte Polynomial

We study the complexity of computing the sign of the Tutte polynomial of a graph. As there are only three possible outcomes (positive, negative, and zero), this seems at first sight more like a decision problem than a counting problem. Surprisingly, however, there are large regions of the parameter space for which computing the sign of the Tutte polynomial is actually #P-hard. As a trivial consequence, approximating the polynomial is also #P-hard in this case. Thus, approximately evaluating the Tutte polynomial in these regions is as hard as exactly counting the satisfying assignments to a CNF Boolean formula. For most other points in the parameter space, we show that computing the sign of the polynomial is in FP, whereas approximating the polynomial can be done in polynomial time with an NP oracle. As a special case, we completely resolve the complexity of computing the sign of the chromatic polynomial - this is easily computable at q=2 and when q is less than or equal to 32/27, and is NP-hard to compute for all other values of the parameter q.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2

A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this paper, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph H has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs H, counting homomorphisms to H modulo 2 can be done in polynomial time. For every other fixed cactus graph H, the problem is complete for the complexity class parity-P which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which H lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which H is a tree.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid

We investigate the computational difficulty of approximating the partition function of the ferromagnetic Ising model on a regular matroid. Jerrum and Sinclair have shown that there is a fully polynomial randomised approximation scheme (FPRAS) for the class of graphic matroids. On the other hand, the authors have previously shown, subject to a complexity-theoretic assumption, that there is no FPRAS for the class of binary matroids, which is a proper superset of the class of graphic matroids. In order to map out the region where approximation is feasible, we focus on the class of regular matroids, an important class of matroids which properly includes the class of graphic matroids, and is properly included in the class of binary matroids. Using Seymour&#39;s decomposition theorem, we give an FPRAS for the class of regular matroids.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Ranking Games that have Competitiveness-based Strategies

An extensive literature in economics and social science addresses contests, in which players compete to outperform each other on some measurable criterion, often referred to as a player&#39;s score, or output. Players incur costs that are an increasing function of score, but receive prizes for obtaining higher score than their competitors. In this paper we study finite games that are discretized contests, and the problems of computing exact and approximate Nash equilibria. Our motivation is the worst-case hardness of Nash equilibrium computation, and the resulting interest in important classes of games that admit polynomial-time algorithms. For games that have a tie-breaking rule for players&#39; scores, we present a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and for multiple players, a characterization of Nash equilibria that shows an interesting parallel between these games and unrestricted 2-player games in normal form. When ties are allowed, via a reduction from these games to a subclass of anonymous games, we give approximation schemes for two special cases: constant-sized set of strategies, and constant number of players.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Approximating the partition function of the ferromagnetic Potts model

We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic q-state Potts model when q>2. Specifically we show that the partition function is hard for the complexity class #RHPi_1 under approximation-preserving reducibility. Thus, it is as hard to approximate the partition function as it is to find approximate solutions to a wide range of counting problems, including that of determining the number of independent sets in a bipartite graph. Our proof exploits the first order phase transition of the &#34;random cluster&#34; model, which is a probability distribution on graphs that is closely related to the q-state Potts model.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials

We consider the problem of approximating certain combinatorial polynomials. First, we consider the problem of approximating the Tutte polynomial of a binary matroid with parameters q>= 2 and gamma. (Relative to the classical (x,y) parameterisation, q=(x-1)(y-1) and gamma=y-1.) A graph is a special case of a binary matroid, so earlier work by the authors shows inapproximability (subject to certain complexity assumptions) for q>2, apart from the trivial case gamma=0. The situation for q=2 is different. Previous results for graphs imply inapproximability in the region -2<=gamma<0, apart from at two &#34;special points&#34; where the polynomial can be computed exactly in polynomial time. For binary matroids, we extend this result by showing (i) there is no FPRAS in the region gamma<-2 unless NP=RP, and (ii) in the region gamma>0, the approximation problem is hard for the complexity class #RHPi_1 under approximation-preserving (AP) reducibility. The latter result indicates a gap in approximation complexity at q=2: whereas an FPRAS is known in the graphical case, there can be none in the binary matroid case, unless there is an FPRAS for all of #RHPi_1. The result also implies that it is computationally difficult to approximate the weight enumerator of a binary linear code, apart from at the special weights at which the problem is exactly solvable in polynomial time. As a consequence, we show that approximating the cycle index polynomial of a permutation group is hard for #RHPi_1 under AP-reducibility, partially resolving a question that we first posed in 1992.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Fixation Probability of Superstars

The Moran process models the spread of genetic mutations through a population. A mutant with relative fitness $r$ is introduced into a population and the system evolves, either reaching fixation (in which every individual is a mutant) or extinction (in which none is). In a widely cited paper (Nature, 2005), Lieberman, Hauert and Nowak generalize the model to populations on the vertices of graphs. They describe a class of graphs (called &#34;superstars&#34;), with a parameter $k$. Superstars are designed to have an increasing fixation probability as $k$ increases. They state that the probability of fixation tends to $1-r^{-k}$ as graphs get larger but we show that this claim is untrue as stated. Specifically, for $k=5$, we show that the true fixation probability (in the limit, as graphs get larger) is at most $1-1/j(r)$ where $j(r)=Θ(r^4)$, contrary to the claimed result. We do believe that the qualitative claim of Lieberman et al.\ --- that the fixation probability of superstars tends to 1 as $k$ increases --- is correct, and that it can probably be proved along the lines of their sketch. We were able to run larger computer simulations than the ones presented in their paper. However, simulations on graphs of around 40,000 vertices do not support their claim. Perhaps these graphs are too small to exhibit the limiting behaviour.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Complexity of Approximately Counting Stable Matchings

We investigate the complexity of approximately counting stable matchings in the $k$-attribute model, where the preference lists are determined by dot products of &#34;preference vectors&#34; with &#34;attribute vectors&#34;, or by Euclidean distances between &#34;preference points&#34; and &#34;attribute points&#34;. Irving and Leather proved that counting the number of stable matchings in the general case is $#P$-complete. Counting the number of stable matchings is reducible to counting the number of downsets in a (related) partial order and is interreducible, in an approximation-preserving sense, to a class of problems that includes counting the number of independent sets in a bipartite graph ($#BIS$). It is conjectured that no FPRAS exists for this class of problems. We show this approximation-preserving interreducibilty remains even in the restricted $k$-attribute setting when $k \geq 3$ (dot products) or $k \geq 2$ (Euclidean distances). Finally, we show it is easy to count the number of stable matchings in the 1-attribute dot-product setting.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Complexity of Approximately Counting Stable Roommate Assignments

We investigate the complexity of approximately counting stable roommate assignments in two models: (i) the $k$-attribute model, in which the preference lists are determined by dot products of &#34;preference vectors&#34; with &#34;attribute vectors&#34; and (ii) the $k$-Euclidean model, in which the preference lists are determined by the closeness of the &#34;positions&#34; of the people to their &#34;preferred positions&#34;. Exactly counting the number of assignments is #P-complete, since Irving and Leather demonstrated #P-completeness for the special case of the stable marriage problem. We show that counting the number of stable roommate assignments in the $k$-attribute model ($k \geq 4$) and the 3-Euclidean model($k \geq 3$) is interreducible, in an approximation-preserving sense, with counting independent sets (of all sizes) (#IS) in a graph, or counting the number of satisfying assignments of a Boolean formula (#SAT). This means that there can be no FPRAS for any of these problems unless NP=RP. As a consequence, we infer that there is no FPRAS for counting stable roommate assignments (#SR) unless NP=RP. Utilizing previous results by the authors, we give an approximation-preserving reduction from counting the number of independent sets in a bipartite graph (#BIS) to counting the number of stable roommate assignments both in the 3-attribute model and in the 2-Euclidean model. #BIS is complete with respect to approximation-preserving reductions in the logically-defined complexity class $#RHΠ_1$. Hence, our result shows that an FPRAS for counting stable roommate assignments in the 3-attribute model would give an FPRAS for all of $#RHΠ_1$. We also show that the 1-attribute stable roommate problem always has either one or two stable roommate assignments, so the number of assignments can be determined exactly in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The expressibility of functions on the Boolean domain, with applications to Counting CSPs

An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using primitive positive formulas over a particular set of base relations. Post&#39;s lattice gives a complete classification of all Boolean relational clones, and this has been used to classify the computational difficulty of CSPs. Motivated by a desire to understand the computational complexity of (weighted) counting CSPs, we develop an analogous notion of functional clones and study the landscape of these clones. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In the conservative case (where all nonnegative unary functions are available), we show that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard to approximate as any problem in #P. Furthermore, we show that any non-trivial functional clone (in a sense that will be made precise) contains the binary function &#34;implies&#34;. As a consequence, in the conservative case, all non-trivial counting CSPs are as hard as #BIS, the problem of counting independent sets in a bipartite graph. Given the complexity-theoretic results, it is natural to ask whether the &#34;implies&#34; clone is equivalent to the clone of lsm functions. We use the Mobius transform and the Fourier transform to show that these clones coincide precisely up to arity 3. It is an intriguing open question whether the lsm clone is finitely generated. Finally, we investigate functional clones in which only restricted classes of unary functions are available.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Counterexample to rapid mixing of the Ge-Stefankovic Process

Ge and Stefankovic have recently introduced a novel two-variable graph polynomial. When specialised to a bipartite graphs G and evaluated at the point (1/2,1) this polynomial gives the number of independent sets in the graph. Inspired by this polynomial, they also introduced a Markov chain which, if rapidly mixing, would provide an efficient sampling procedure for independent sets in G. This sampling procedure in turn would imply the existence of efficient approximation algorithms for a number of significant counting problems whose complexity is so far unresolved. The proposed Markov chain is promising, in the sense that it overcomes the most obvious barrier to mixing. However, we show here, by exhibiting a sequence of counterexamples, that the mixing time of their Markov chain is exponential in the size of the input when the input is chosen from a particular infinite family of bipartite graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Adaptive Drift Analysis

We show that, for any c>0, the (1+1) evolutionary algorithm using an arbitrary mutation rate p_n = c/n finds the optimum of a linear objective function over bit strings of length n in expected time Theta(n log n). Previously, this was only known for c at most 1. Since previous work also shows that universal drift functions cannot exist for c larger than a certain constant, we instead define drift functions which depend crucially on the relevant objective functions (and also on c itself). Using these carefully-constructed drift functions, we prove that the expected optimisation time is Theta(n log n). By giving an alternative proof of the multiplicative drift theorem, we also show that our optimisation-time bound holds with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Inapproximability of the Tutte polynomial of a planar graph

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: given as input a planar graph G, determine T(G;x,y). Vertigan completely mapped the complexity of exactly computing the Tutte polynomial of a planar graph. He showed that the problem can be solved in polynomial time if (x,y) is on the hyperbola H_q given by (x-1)(y-1)=q for q=1 or q=2 or if (x,y) is one of the two special points (x,y)=(-1,-1) or (x,y)=(1,1). Otherwise, the problem is #P-hard. In this paper, we consider the problem of approximating T(G;x,y), in the usual sense of &#34;fully polynomial randomised approximation scheme&#34; or FPRAS. Roughly speaking, an FPRAS is required to produce, in polynomial time and with high probability, an answer that has small relative error. Assuming that NP is different from RP, we show that there is no FPRAS for the Tutte polynomial in a large portion of the (x,y) plane. In particular, there is no FPRAS if x>1, y<-1 or if y>1, x<-1 or if x<0, y<0 and q>5. Also, there is no FPRAS if x<1, y<1 and q=3. For q>5, our result is intriguing because it shows that there is no FPRAS at (x,y)=(1-q/(1+epsilon),-epsilon) for any positive epsilon but it leaves open the limit point epsilon=0, which corresponds to approximately counting q-colourings of a planar graph.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Complexity of Approximating Bounded-Degree Boolean \sharp CSP

The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum allowed degree is large enough (at least 6) we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP=RP. For lower degree bounds, additional cases arise, where the complexity is related to the complexity of approximately counting independent sets in hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A complexity dichotomy for hypergraph partition functions

We consider the complexity of counting homomorphisms from an $r$-uniform hypergraph $G$ to a symmetric $r$-ary relation $H$. We give a dichotomy theorem for $r>2$, showing for which $H$ this problem is in FP and for which $H$ it is #P-complete. This generalises a theorem of Dyer and Greenhill (2000) for the case $r=2$, which corresponds to counting graph homomorphisms. Our dichotomy theorem extends to the case in which the relation $H$ is weighted, and the goal is to compute the \emph{partition function}, which is the sum of weights of the homomorphisms. This problem is motivated by statistical physics, where it arises as computing the partition function for particle models in which certain combinations of $r$ sites interact symmetrically. In the weighted case, our dichotomy theorem generalises a result of Bulatov and Grohe (2005) for graphs, where $r=2$. When $r=2$, the polynomial time cases of the dichotomy correspond simply to rank-1 weights. Surprisingly, for all $r>2$ the polynomial time cases of the dichotomy have rather more structure. It turns out that the weights must be superimposed on a combinatorial structure defined by solutions of an equation over an Abelian group. Our result also gives a dichotomy for a closely related constraint satisfaction problem.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract)

The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum degree is at least 25 we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP=RP. For lower degree bounds, additional cases arise in which the complexity is related to the complexity of approximately counting independent sets in hypergraphs.

0 citations0 reviewsNo code linkedOpen access