
Approximate counting via correlation decay is the core algorithmic technique
used in the sharp delineation of the computational phase transition that arises
in the approximation of the partition function of antiferromagnetic twospin
models.
Previous analyses of correlationdecay algorithms implicitly depended on the
occurrence of strong spatial mixing (SSM). This means that one uses worstcase
analysis of the recursive procedure that creates the subinstances. We develop
a new analysis method that is more refined than the worstcase analysis. We
take the shape of instances in the computation tree into consideration and
amortise against certain "bad" instances that are created as the recursion
proceeds. This enables us to show correlation decay and to obtain an FPTAS even
when SSM fails.
We apply our technique to the problem of approximately counting independent
sets in hypergraphs with degree upperbound Delta and with a lower bound k on
the arity of hyperedges. Liu and Lin gave an FPTAS for k>=2 and Delta<=5 (lack
of SSM was the obstacle preventing this algorithm from being generalised to
Delta=6). Our technique gives a tight result for Delta=6, showing that there is
an FPTAS for k>=3 and Delta<=6. The best previouslyknown approximation scheme
for Delta=6 is the Markovchain simulation based FPRAS of Bordewich, Dyer and
Karpinski, which only works for k>=8.
Our technique also applies for larger values of k, giving an FPTAS for
k>=Delta. This bound is not substantially stronger than existing randomised
results in the literature. Nevertheless, it gives the first deterministic
approximation scheme in this regime. Moreover, unlike existing results, it
leads to an FPTAS for counting dominating sets in regular graphs with
sufficiently large degree.
We further demonstrate that approximately counting independent sets in
hypergraphs is NPhard even within the uniqueness regime.

We study the structure learning problem for $H$colorings, an important class
of Markov random fields that capture key combinatorial structures on graphs,
including proper colorings and independent sets, as well as spin systems from
statistical physics. The learning problem is as follows: for a fixed (and
known) constraint graph $H$ with $q$ colors and an unknown graph $G=(V,E)$ with
$n$ vertices, given uniformly random $H$colorings of $G$, how many samples are
required to learn the edges of the unknown graph $G$? We give a
characterization of $H$ for which the problem is identifiable for every $G$,
i.e., we can learn $G$ with an infinite number of samples. We also show that
there are identifiable constraint graphs for which one cannot hope to learn
every graph $G$ efficiently.
We focus particular attention on the case of proper vertex $q$colorings of
graphs of maximum degree $d$ where intriguing connections to statistical
physics phase transitions appear. We prove that in the tree uniqueness region
(when $q>d$) the problem is identifiable and we can learn $G$ in ${\rm
poly}(d,q) \times O(n^2\log{n})$ time. In contrast for softconstraint systems,
such as the Ising model, the best possible running time is exponential in $d$.
In the tree nonuniqueness region (when $q\leq d$) we prove that the problem is
not identifiable and thus $G$ cannot be learned. Moreover, when $q<d\sqrt{d} +
\Theta(1)$ we prove that even learning an equivalent graph (any graph with the
same set of $H$colorings) is computationally hardsample complexity is
exponential in $n$ in the worst case. We further explore the connection between
the efficiency/hardness of the structure learning problem and the
uniqueness/nonuniqueness phase transition for general $H$colorings and prove
that under the wellknown Dobrushin uniqueness condition, we can learn $G$ in
${\rm poly}(d,q)\times O(n^2\log{n})$ time.

We consider the problem of sampling from the Potts model on random regular
graphs. It is conjectured that sampling is possible when the temperature of the
model is in the uniqueness regime of the regular tree, but positive algorithmic
results have been for the most part elusive. In this paper, for all integers
$q\geq 3$ and $\Delta\geq 3$, we develop algorithms that produce samples within
error $o(1)$ from the $q$state Potts model on random $\Delta$regular graphs,
whenever the temperature is in uniqueness, for both the ferromagnetic and
antiferromagnetic cases.
The algorithm for the antiferromagnetic Potts model is based on iteratively
adding the edges of the graph and resampling a bichromatic class that contains
the endpoints of the newly added edge. Key to the algorithm is how to perform
the resampling step efficiently since bichromatic classes may induce
linearsized components. To this end, we exploit the tree uniqueness to show
that the average growth of bichromatic components is typically small, which
allows us to use correlation decay algorithms for the resampling step. While
the precise uniqueness threshold on the tree is not known for general values of
$q$ and $\Delta$ in the antiferromagnetic case, our algorithm works throughout
uniqueness regardless of its value.
In the case of the ferromagnetic Potts model, we simplify the algorithm
significantly by utilising the randomcluster representation of the model. In
particular, we show that a percolationtype algorithm succeeds in sampling from
the randomcluster model with parameters $p,q$ on random $\Delta$regular
graphs for all values of $q\geq 1$ and $p<p_c(q,\Delta)$, where $p_c(q,\Delta)$
corresponds to a uniqueness threshold for the model on the $\Delta$regular
tree. When restricted to integer values of $q$, this yields a simplified
algorithm for the ferromagnetic Potts model on random $\Delta$regular graphs.

We study the complexity of approximating the independent set polynomial
$Z_G(\lambda)$ of a graph $G$ with maximum degree $\Delta$ when the activity
$\lambda$ is a complex number.
This problem is already well understood when $\lambda$ is real using
connections to the $\Delta$regular tree $T$. The key concept in that case is
the "occupation ratio" of the tree $T$. This ratio is the contribution to
$Z_T(\lambda)$ from independent sets containing the root of the tree, divided
by $Z_T(\lambda)$ itself. If $\lambda$ is such that the occupation ratio
converges to a limit, as the height of $T$ grows, then there is an FPTAS for
approximating $Z_G(\lambda)$ on a graph $G$ with maximum degree $\Delta$.
Otherwise, the approximation problem is NPhard.
Unsurprisingly, the case where $\lambda$ is complex is more challenging.
Peters and Regts identified the complex values of $\lambda$ for which the
occupation ratio of the $\Delta$regular tree converges. These values carve a
cardioidshaped region $\Lambda_\Delta$ in the complex plane. Motivated by the
picture in the real case, they asked whether $\Lambda_\Delta$ marks the true
approximability threshold for general complex values $\lambda$.
Our main result shows that for every $\lambda$ outside of $\Lambda_\Delta$,
the problem of approximating $Z_G(\lambda)$ on graphs $G$ with maximum degree
at most $\Delta$ is indeed NPhard. In fact, when $\lambda$ is outside of
$\Lambda_\Delta$ and is not a positive real number, we give the stronger result
that approximating $Z_G(\lambda)$ is actually #Phard. If $\lambda$ is a
negative real number outside of $\Lambda_\Delta$, we show that it is #Phard to
even decide whether $Z_G(\lambda)>0$, resolving in the affirmative a conjecture
of Harvey, Srivastava and Vondrak.
Our proof techniques are based around tools from complex analysis 
specifically the study of iterative multivariate rational maps.

We study the mixing properties of the singlesite Markov chain known as the
Glauber dynamics for sampling $k$colorings of a sparse random graph $G(n,d/n)$
for constant $d$. The best known rapid mixing results for general graphs are in
terms of the maximum degree $\Delta$ of the input graph $G$ and hold when
$k>11\Delta/6$ for all $G$. Improved results hold when $k>\alpha\Delta$ for
graphs with girth $\geq 5$ and $\Delta$ sufficiently large where $\alpha\approx
1.7632\ldots$ is the root of $\alpha=\exp(1/\alpha)$; further improvements on
the constant $\alpha$ hold with stronger girth and maximum degree assumptions.
For sparse random graphs the maximum degree is a function of $n$ and the goal
is to obtain results in terms of the expected degree $d$. The following rapid
mixing results for $G(n,d/n)$ hold with high probability over the choice of the
random graph for sufficiently large constant~$d$. Mossel and Sly (2009) proved
rapid mixing for constant $k$, and Efthymiou (2014) improved this to $k$ linear
in~$d$. The condition was improved to $k>3d$ by Yin and Zhang (2016) using
nonMCMC methods. Here we prove rapid mixing when $k>\alpha d$ where
$\alpha\approx 1.7632\ldots$ is the same constant as above. Moreover we obtain
$O(n^{3})$ mixing time of the Glauber dynamics, while in previous rapid mixing
results the exponent was an increasing function in $d$. As in previous results
for random graphs our proof analyzes an appropriately defined block dynamics to
"hide" highdegree vertices. One new aspect in our improved approach is
utilizing socalled local uniformity properties for the analysis of block
dynamics. To analyze the "burnin" phase we prove a concentration inequality
for the number of disagreements propagating in large blocks.

We study the problem of approximately evaluating the independent set
polynomial of boundeddegree graphs at a point lambda or, equivalently, the
problem of approximating the partition function of the hardcore model with
activity lambda on graphs G of max degree D. For lambda>0, breakthrough results
of Weitz and Sly established a computational transition from easy to hard at
lambda_c(D)=(D1)^(D1)/(D2)^D, which coincides with the tree uniqueness phase
transition from statistical physics.
For lambda<0, the evaluation of the independent set polynomial is connected
to the conditions of the Lovasz Local Lemma. Shearer identified the threshold
lambda*(D)=(D1)^(D1)/D^D as the maximum value p such that every family of
events with failure probability at most p and whose dependency graph has max
degree D has nonempty intersection. Very recently, Patel and Regts, and Harvey
et al. have independently designed FPTASes for approximating the partition
function whenever lambda<lambda*(D).
Our main result establishes for the first time a computational transition at
the Shearer threshold. We show that for all D>=3, for all lambda<lambda*(D),
it is NPhard to approximate the partition function on bipartite graphs of
maximum degree D, even within an exponential factor. Thus, our result, combined
with the FPTASes for lambda>lambda*(D), establishes a phase transition for
negative activities. In fact, we now have the following picture for the problem
of approximating the partition function with activity lambda on graphs G of max
degree D.
(i) For lambda*(D)<lambda<lambda_c(D), the problem admits an FPTAS.
(ii) For lambda<lambda*(D) or lambda>lambda_c(D), the problem is NPhard.
Rather than the tree uniqueness threshold of the positive case, the phase
transition for negative activities corresponds to the existence of zeros for
the partition function of the tree below lambda*(D).

The cardinality constraint is an intrinsic way to restrict the solution
structure in many domains, for example, sparse learning, feature selection, and
compressed sensing. To solve a cardinality constrained problem, the key
challenge is to solve the projection onto the cardinality constraint set, which
is NPhard in general when there exist multiple overlapped cardinality
constraints. In this paper, we consider the scenario where the overlapped
cardinality constraints satisfy a Threeview Cardinality Structure (TVCS),
which reflects the natural restriction in many applications, such as
identification of gene regulatory networks and taskworker assignment problem.
We cast the projection into a linear programming, and show that for TVCS, the
vertex solution of this linear programming is the solution for the original
projection problem. We further prove that such solution can be found with the
complexity proportional to the number of variables and constraints. We finally
use synthetic experiments and two interesting applications in bioinformatics
and crowdsourcing to validate the proposed TVCS model and method.

The Gibbs sampler is a particularly popular Markov chain used for learning
and inference problems in Graphical Models (GMs). These tasks are
computationally intractable in general, and the Gibbs sampler often suffers
from slow mixing. In this paper, we study the SwendsenWang dynamics which is a
more sophisticated Markov chain designed to overcome bottlenecks that impede
the Gibbs sampler. We prove O(\log n) mixing time for attractive binary
pairwise GMs (i.e., ferromagnetic Ising models) on stochastic partitioned
graphs having n vertices, under some mild conditions, including low temperature
regions where the Gibbs sampler provably mixes exponentially slow. Our
experiments also confirm that the SwendsenWang sampler significantly
outperforms the Gibbs sampler when they are used for learning parameters of
attractive GMs.

We show that determining the rank of a tensor over a field has the same
complexity as deciding the existential theory of that field. This implies
earlier NPhardness results by H{\aa}stad~\cite{H90}. The hardness proof also
implies an algebraic universality result.

Recent results establish for 2spin 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 Dregular 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 (#BIShardness). 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
Dregular tree, giving a refined picture of its firstorder 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 #BIShard to approximate the partition function on
bipartite graphs of maximum degree D. As a corollary, it is #BIShard to
approximate the number of kcolorings on bipartite graphs of maximum degree D
when k <= D/(2 ln D).
The #BIShardness 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 SwendsenWang algorithm
is torpidly mixing on random Dregular graphs at the critical temperature for
large q.

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
hardcore model. Let $\lambda_c(T_\Delta)$ denote the critical activity for the
hardmodel on the infinite $\Delta$regular tree. Weitz presented an FPTAS for
the partition function when $\lambda<\lambda_c(T_\Delta)$ for graphs with
constant maximum degree $\Delta$. In contrast, Sly showed that for all
$\Delta\geq 3$, there exists $\epsilon_\Delta>0$ such that (unless RP=NP) there
is no FPRAS for approximating the partition function on graphs of maximum
degree $\Delta$ for activities $\lambda$ satisfying
$\lambda_c(T_\Delta)<\lambda<\lambda_c(T_\Delta)+\epsilon_\Delta$.
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 2spin model, which includes the antiferromagnetic Ising model, to yield
an FPTAS for the partition function for all graphs of constant maximum degree
$\Delta$ when the parameters of the model lie in the uniqueness regime of the
infinite tree $T_\Delta$. We prove the complementary result that for the
antiferrogmanetic Ising model without external field that, unless RP=NP, for
all $\Delta\geq 3$, there is no FPRAS for approximating the partition function
on graphs of maximum degree $\Delta$ when the inverse temperature lies in the
nonuniqueness regime of the infinite tree $T_\Delta$. Our results extend to a
region of the parameter space for general 2spin models. Our proof works by
relating certain second moment calculations for random $\Delta$regular
bipartite graphs to the tree recursions used to establish the critical points
on the infinite tree.

We study the hardcore model defined on independent sets of an input graph
where the independent sets are weighted by a parameter $\lambda>0$. For
constant $\Delta$, previous work of Weitz (2006) established an FPTAS for the
partition function for graphs of maximum degree $\Delta$ when $\lambda<
\lambda_c(\Delta)$. The threshold $\lambda_c(\Delta)$ is the critical point for
the phase transition for uniqueness/nonuniqueness on the infinite
$\Delta$regular trees. Sly (2010) showed that there is no FPRAS, unless NP=RP,
when $\lambda>\lambda_c(\Delta)$. The running time of Weitz's algorithm is
exponential in $\log(\Delta)$. Here we present an FPRAS for the partition
function whose running time is $O^*(n^2)$. We analyze the simple singlesite
Glauber dynamics for sampling from the associated Gibbs distribution. We prove
there exists a constant $\Delta_0$ such that for all graphs with maximum degree
$\Delta\geq\Delta_0$ and girth $\geq 7$, the mixing time of the Glauber
dynamics is $O(n\log(n))$ when $\lambda<\lambda_c(\Delta)$. Our work
complements that of Weitz which applies for constant $\Delta$ whereas our work
applies for all $\Delta \geq \Delta_0$.
We utilize loopy BP (belief propagation), a widelyused 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 burnin 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 $\lambda<\lambda_c(\Delta)$.

We study the $q$state ferromagnetic Potts model on the $n$vertex complete
graph known as the meanfield (CurieWeiss) model. We analyze the SwendsenWang
algorithm which is a Markov chain that utilizes the random cluster
representation for the ferromagnetic Potts model to recolor large sets of
vertices in one step and potentially overcomes obstacles that inhibit
singlesite Glauber dynamics. The case $q=2$ (the SwendsenWang algorithm for
the ferromagnetic Ising model) undergoes a slowdown at the
uniqueness/nonuniqueness critical temperature for the infinite
$\Delta$regular tree (Long et al., 2014) but yet still has polynomial mixing
time at all (inverse) temperatures $\beta>0$ (Cooper et al., 2000). In contrast
for $q\geq 3$ there are two critical temperatures
$0<\beta_{\mathrm{u}}<\beta_{\mathrm{rc}}$ that are relevant, these two
critical points relate to phase transitions in the infinite tree. We prove that
the mixing time of the SwendsenWang algorithm for the ferromagnetic Potts
model on the $n$vertex complete graph satisfies: (i) $O(1)$ for
$\beta<\beta_{\mathrm{u}}$, (ii) $\Theta(n^{1/3})$ for
$\beta=\beta_{\mathrm{u}}$, (iii) $\exp(n^{\Omega(1)})$ for
$\beta_{\mathrm{u}}<\beta<\beta_{\mathrm{rc}}$, and (iv) $\Theta(\log{n})$ for
$\beta\geq\beta_{\mathrm{rc}}$. These results complement refined results of
Cuff et al. (2012) on the mixing time of the Glauber dynamics for the
ferromagnetic Potts model. The most interesting aspect of our analysis is at
the critical temperature $\beta=\beta_{\mathrm{u}}$, which requires a delicate
choice of a potential function to balance the conflating factors for the slow
drift away from a fixed point (which is repulsive but not Jacobian repulsive):
close to the fixed point the variance from the percolation step dominates and
sufficiently far from the fixed point the dynamics of the size of the dominant
color class takes over.

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 twostate spin systems
on bipartite graphs. We define two notions, nearlyindependent phasecorrelated
spins and unary symmetry breaking. We prove that it is #BIShard to approximate
the partition function of any 2spin system on bipartite graphs supporting
these two notions. As a consequence, we classify the complexity of
approximating the partition function of antiferromagnetic 2spin systems on
boundeddegree bipartite graphs.

A remarkable connection has been established for antiferromagnetic 2spin
systems, including the Ising and hardcore 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/nonuniqueness phase transition on the infinite
Dregular tree. Despite this clear picture for 2spin systems, there is little
known for multispin systems. We present the first analog of the above
inapproximability results for multispin systems.
The main difficulty in previous inapproximability results was analyzing the
behavior of the model on random Dregular 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 Dregular 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 kcolorings we prove that for even k, in the tree nonuniqueness region
(which corresponds to k<D) it is NPhard, unless NP=RP, to approximate the
number of colorings for trianglefree Dregular graphs. Our proof extends to
the antiferromagnetic Potts model, and, in fact, to every antiferromagnetic
model under a mild condition.

We study the problem of deterministic approximate counting of matchings and
independent sets in graphs of bounded connective constant. More generally, we
consider the problem of evaluating the partition functions of the monomerdimer
model (which is defined as a weighted sum over all matchings where each
matching is given a weight $\gamma^{V  2 M}$ in terms of a fixed parameter
gamma called the monomer activity) and the hard core model (which is defined as
a weighted sum over all independent sets where an independent set I is given a
weight $\lambda^{I}$ in terms of a fixed parameter lambda called the vertex
activity). The connective constant is a natural measure of the average degree
of a graph which has been studied extensively in combinatorics and mathematical
physics, and can be bounded by a constant even for certain unbounded degree
graphs such as those sampled from the sparse Erd\H{o}sR\'enyi model $G(n,
d/n)$.
Our main technical contribution is to prove the best possible rates of decay
of correlations in the natural probability distributions induced by both the
hard core model and the monomerdimer model in graphs with a given bound on the
connective constant. These results on decay of correlations are obtained using
a new framework based on the socalled message approach that has been
extensively used recently to prove such results for bounded degree graphs. We
then use these optimal decay of correlations results to obtain FPTASs for the
two problems on graphs of bounded connective constant.
Our techniques also allow us to improve upon known bounds for decay of
correlations for the hard core model on various regular lattices, including
those obtained by Restrepo, Shin, Vigoda and Tetali (2011) for the special case
of Z^2 using sophisticated numerically intensive methods tailored to that
special case.

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

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 hardcore model, which is an idealized model of a gas where the particles
have nonnegibile 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):=(Delta1)^(Delta1)/(Delta2)^Delta.
The quantity lambda_c(Tree_Delta) is the critical point for the socalled
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 secondmoment 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.

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 NPhard even for a restricted class of Gaussian Markov random
fields, called Gaussian free fields, which arise in semisupervised 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 treewidth
graphs.

We investigate the problem of strong spatial mixing of $q$colorings on Bethe
lattices. By analyzing the sumproduct algorithm we establish the strong
spatial mixing of $q$colorings on $(b+1)$regular Bethe lattices, for $q \geq
1+\lceil 1.764b \rceil$. We also establish the strong spatial mixing of
$q$colorings on binary trees, for $q=4$.

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.

This paper studies a Markov chain for phylogenetic reconstruction which uses
a popular transition between tree topologies known as subtree
pruningandregrafting (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.

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

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.

We study the effect of boundary conditions on the relaxation time of the
Glauber dynamics for the hardcore model on the tree. The hardcore model is
defined on the set of independent sets weighted by a parameter $\lambda$,
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 hardcore model can be equivalently defined as a broadcasting process
with a parameter $\omega$ which is the positive solution to
$\lambda=\omega(1+\omega)^b$, and vertices are occupied with probability
$\omega/(1+\omega)$ when their parent is unoccupied. This broadcasting process
undergoes a phase transition between the socalled reconstruction and
nonreconstruction regions at $\omega_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 treelike 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 $\omega \le
\ln{b}/b$, for $T_h$ with any boundary condition, the relaxation time is
$\Omega(n)$ and $O(n^{1+o_b(1)})$. In contrast, above the reconstruction
threshold we show that for every $\delta>0$, for $\omega=(1+\delta)\ln{b}/b$,
the relaxation time on $T_h$ with any boundary condition is $O(n^{1+\delta +
o_b(1)})$, and we construct a boundary condition where the relaxation time is
$\Omega(n^{1+\delta/2  o_b(1)})$.