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

Daniel Stefankovic

Daniel Stefankovic 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.MPLogic in Computer ScienceMachine Learningmath.STPopulations and EvolutionStatistics Theory

Catalog footprint

What is connected

17works
12topics
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
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
preprint2016arXiv

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

We study the hard-core model defined on independent sets of an input graph where the independent sets are weighted by a parameter $λ>0$. For constant $Δ$, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree $Δ$ when $λ< λ_c(Δ)$. The threshold $λ_c(Δ)$ is the critical point for the phase transition for uniqueness/non-uniqueness on the infinite $Δ$-regular trees. Sly (2010) showed that there is no FPRAS, unless NP=RP, when $λ>λ_c(Δ)$. The running time of Weitz's algorithm is exponential in $\log(Δ)$. Here we present an FPRAS for the partition function whose running time is $O^*(n^2)$. We analyze the simple single-site Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant $Δ_0$ such that for all graphs with maximum degree $Δ\geqΔ_0$ and girth $\geq 7$, the mixing time of the Glauber dynamics is $O(n\log(n))$ when $λ<λ_c(Δ)$. Our work complements that of Weitz which applies for constant $Δ$ whereas our work applies for all $Δ\geq Δ_0$. We utilize loopy BP (belief propagation), a widely-used inference algorithm. A novel aspect of our work is using the principal eigenvector for the BP operator to design a distance function which contracts in expectation for pairs of states that behave like the BP fixed point. We also prove that the Glauber dynamics behaves locally like loopy BP. As a byproduct we obtain that the Glauber dynamics converges, after a short burn-in period, close to the BP fixed point, and this implies that the fixed point of loopy BP is a close approximation to the Gibbs distribution. Using these connections we establish that loopy BP quickly converges to the Gibbs distribution when the girth $\geq 6$ and $λ<λ_c(Δ)$.

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
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
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
preprint2013arXiv

Reasoning Under the Principle of Maximum Entropy for Modal Logics K45, KD45, and S5

We propose modal Markov logic as an extension of propositional Markov logic to reason under the principle of maximum entropy for modal logics K45, KD45, and S5. Analogous to propositional Markov logic, the knowledge base consists of weighted formulas, whose weights are learned from data. However, in contrast to Markov logic, in our framework we use the knowledge base to define a probability distribution over non-equivalent epistemic situations (pointed Kripke structures) rather than over atoms, and use this distribution to assign probabilities to modal formulas. As in all probabilistic representations, the central task in our framework is inference. Although the size of the state space grows doubly exponentially in the number of propositions in the domain, we provide an algorithm that scales only exponentially in the size of the knowledge base. Finally, we briefly discuss the case of languages with an infinite number of propositions.

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
preprint2012arXiv

Subset Selection for Gaussian Markov Random Fields

Given a Gaussian Markov random field, we consider the problem of selecting a subset of variables to observe which minimizes the total expected squared prediction error of the unobserved variables. We first show that finding an exact solution is NP-hard even for a restricted class of Gaussian Markov random fields, called Gaussian free fields, which arise in semi-supervised learning and computer vision. We then give a simple greedy approximation algorithm for Gaussian free fields on arbitrary graphs. Finally, we give a message passing algorithm for general Gaussian Markov random fields on bounded tree-width graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Fast Convergence of MCMC Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species

This paper studies a Markov chain for phylogenetic reconstruction which uses a popular transition between tree topologies known as subtree pruning-and-regrafting (SPR). We analyze the Markov chain in the simpler setting that the generating tree consists of very short edge lengths, short enough so that each sample from the generating tree (or character in phylogenetic terminology) is likely to have only one mutation, and that there enough samples so that the data looks like the generating distribution. We prove in this setting that the Markov chain is rapidly mixing, i.e., it quickly converges to its stationary distribution, which is the posterior distribution over tree topologies. Our proofs use that the leading term of the maximum likelihood function of a tree T is the maximum parsimony score, which is the size of the minimum cut in T needed to realize single edge cuts of the generating tree. Our main contribution is a combinatorial proof that in our simplified setting, SPR moves are guaranteed to converge quickly to the maximum parsimony tree. Our results are in contrast to recent works showing examples with heterogeneous data (namely, the data is generated from a mixture distribution) where many natural Markov chains are exponentially slow to converge to the stationary distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Negative Examples for Sequential Importance Sampling of Binary Contingency Tables

The sequential importance sampling (SIS) algorithm has gained considerable popularity for its empirical success. One of its noted applications is to the binary contingency tables problem, an important problem in statistics, where the goal is to estimate the number of 0/1 matrices with prescribed row and column sums. We give a family of examples in which the SIS procedure, if run for any subexponential number of trials, will underestimate the number of tables by an exponential factor. This result holds for any of the usual design choices in the SIS algorithm, namely the ordering of the columns and rows. These are apparently the first theoretical results on the efficiency of the SIS algorithm for binary contingency tables. Finally, we present experimental evidence that the SIS algorithm is efficient for row and column sums that are regular. Our work is a first step in determining the class of inputs for which SIS is effective.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions

Given n elements with nonnegative integer weights w1,..., wn and an integer capacity C, we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most the given capacity. We give a deterministic algorithm that estimates the number of solutions to within relative error 1+-eps in time polynomial in n and 1/eps (fully polynomial approximation scheme). More precisely, our algorithm takes time O(n^3 (1/eps) log (n/eps)). Our algorithm is based on dynamic programming. Previously, randomized polynomial time approximation schemes were known first by Morris and Sinclair via Markov chain Monte Carlo techniques, and subsequently by Dyer via dynamic programming and rejection sampling.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A graph polynomial for independent sets of bipartite graphs

We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings and the number of perfect matchings. Most importantly, for bipartite graphs the polynomial encodes the number of independent sets (#BIS). We analyze the complexity of exact evaluation of the polynomial at rational points and show that for most points exact evaluation is #P-hard (assuming the generalized Riemann hypothesis) and for the rest of the points exact evaluation is trivial. We conjecture that a natural Markov chain can be used to approximately evaluate the polynomial for a range of parameters. The conjecture, if true, would imply an approximate counting algorithm for #BIS, a problem shown, by [Dyer et al. 2004], to be complete (with respect to, so called, AP-reductions) for a rich logically defined sub-class of #P. We give a mild support for our conjecture by proving that the Markov chain is rapidly mixing on trees. As a by-product we show that the "single bond flip" Markov chain for the random cluster model is rapidly mixing on constant tree-width graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees

We study the effect of boundary conditions on the relaxation time of the Glauber dynamics for the hard-core model on the tree. The hard-core model is defined on the set of independent sets weighted by a parameter $λ$, called the activity. The Glauber dynamics is the Markov chain that updates a randomly chosen vertex in each step. On the infinite tree with branching factor $b$, the hard-core model can be equivalently defined as a broadcasting process with a parameter $ω$ which is the positive solution to $λ=ω(1+ω)^b$, and vertices are occupied with probability $ω/(1+ω)$ when their parent is unoccupied. This broadcasting process undergoes a phase transition between the so-called reconstruction and non-reconstruction regions at $ω_r\approx \ln{b}/b$. Reconstruction has been of considerable interest recently since it appears to be intimately connected to the efficiency of local algorithms on locally tree-like graphs, such as sparse random graphs. In this paper we show that the relaxation time of the Glauber dynamics on regular $b$-ary trees $T_h$ of height $h$ and $n$ vertices, undergoes a phase transition around the reconstruction threshold. In particular, we construct a boundary condition for which the relaxation time slows down at the reconstruction threshold. More precisely, for any $ω\le \ln{b}/b$, for $T_h$ with any boundary condition, the relaxation time is $Ω(n)$ and $O(n^{1+o_b(1)})$. In contrast, above the reconstruction threshold we show that for every $δ>0$, for $ω=(1+δ)\ln{b}/b$, the relaxation time on $T_h$ with any boundary condition is $O(n^{1+δ+ o_b(1)})$, and we construct a boundary condition where the relaxation time is $Ω(n^{1+δ/2 - o_b(1)})$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Complexity of Counting Eulerian Tours in 4-Regular Graphs

We investigate the complexity of counting Eulerian tours ({\sc #ET}) and its variations from two perspectives---the complexity of exact counting and the complexity w.r.t. approximation-preserving reductions (AP-reductions \cite{MR2044886}). We prove that {\sc #ET} is #P-complete even for planar 4-regular graphs. A closely related problem is that of counting A-trails ({\sc #A-trails}) in graphs with rotational embedding schemes (so called maps). Kotzig \cite{MR0248043} showed that {\sc #A-trails} can be computed in polynomial time for 4-regular plane graphs (embedding in the plane is equivalent to giving a rotational embedding scheme). We show that for 4-regular maps the problem is #P-hard. Moreover, we show that from the approximation viewpoint {\sc #A-trails} in 4-regular maps captures the essence of {\sc #ET}, that is, we give an AP-reduction from {\sc #ET} in general graphs to {\sc #A-trails} in 4-regular maps. The reduction uses a fast mixing result for a card shuffling problem \cite{MR2023023}. In order to understand whether #{\sc A-trails} in 4-regular maps can AP-reduce to #{\sc ET} in 4-regular graphs, we investigate a problem in which transitions in vertices are weighted (this generalizes both #{\sc A-trails} and #{\sc ET}). In the 4-regular case we show that {\sc A-trails} can be used to simulate any vertex weights and provide evidence that {\sc ET} can simulate only a limited set of vertex weights.

0 citations0 reviewsNo code linkedOpen access