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

Eric Vigoda

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

ResearcherUnclaimed source record
math.PRDiscrete Mathematicsmath-phmath.MPComputational Complexitymath.COData Structures and AlgorithmsMachine Learningmath.STPopulations and EvolutionStatistics Theory

Catalog footprint

What is connected

19works
11topics
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

19 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
preprint2020arXiv

Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models

We study identity testing for restricted Boltzmann machines (RBMs), and more generally for undirected graphical models. Given sample access to the Gibbs distribution corresponding to an unknown or hidden model $M^*$ and given an explicit model $M$, can we distinguish if either $M = M^*$ or if they are (statistically) far apart? Daskalakis et al. (2018) presented a polynomial-time algorithm for identity testing for the ferromagnetic (attractive) Ising model. In contrast, for the antiferromagnetic (repulsive) Ising model, Bezáková et al. (2019) proved that unless $RP=NP$ there is no identity testing algorithm when $βd=ω(\log{n})$, where $d$ is the maximum degree of the visible graph and $β$ is the largest edge weight in absolute value. We prove analogous hardness results for RBMs (i.e., mixed Ising models on bipartite graphs), even when there are no latent variables or an external field. Specifically, we show that if $RP \neq NP$, then when $βd=ω(\log{n})$ there is no polynomial-time algorithm for identity testing for RBMs; when $βd =O(\log{n})$ there is an efficient identity testing algorithm that utilizes the structure learning algorithm of Klivans and Meka (2017). In addition, we prove similar lower bounds for purely ferromagnetic RBMs with inconsistent external fields, and for the ferromagnetic Potts model. Previous hardness results for identity testing of Bezáková et al. (2019) utilized the hardness of finding the maximum cuts, which corresponds to the ground states of the antiferromagnetic Ising model. Since RBMs are on bipartite graphs such an approach is not feasible. We instead introduce a general methodology to reduce from the corresponding approximate counting problem and utilize the phase transition that is exhibited by RBMs and the mean-field Potts model.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Random Walks on Small World Networks

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

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rapid Mixing for Colorings via Spectral Independence

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

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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

Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions

For the hard-core lattice gas model defined on independent sets weighted by an activity $λ$, we study the critical activity $λ_c(\mathbb{Z}^2)$ for the uniqueness/non-uniqueness threshold on the 2-dimensional integer lattice $\mathbb{Z}^2$. The conjectured value of the critical activity is approximately $3.796$. Until recently, the best lower bound followed from algorithmic results of Weitz (2006). Weitz presented an FPTAS for approximating the partition function for graphs of constant maximum degree $Δ$ when $λ<λ_c(\mathbb{T}_Δ)$ where $\mathbb{T}_Δ$ is the infinite, regular tree of degree $Δ$. His result established a certain decay of correlations property called strong spatial mixing (SSM) on $\mathbb{Z}^2$ by proving that SSM holds on its self-avoiding walk tree $T_{\mathrm{saw}}^σ(\mathbb{Z}^2)$ where $σ=(σ_v)_{v\in \mathbb{Z}^2}$ and $σ_v$ is an ordering on the neighbors of vertex $v$. As a consequence he obtained that $λ_c(\mathbb{Z}^2)\geqλ_c( \mathbb{T}_4) = 1.675$. Restrepo et al. (2011) improved Weitz's approach for the particular case of $\mathbb{Z}^2$ and obtained that $λ_c(\mathbb{Z}^2)>2.388$. In this paper, we establish an upper bound for this approach, by showing that, for all $σ$, SSM does not hold on $T_{\mathrm{saw}}^σ(\mathbb{Z}^2)$ when $λ>3.4$. We also present a refinement of the approach of Restrepo et al. which improves the lower bound to $λ_c(\mathbb{Z}^2)>2.48$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

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

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

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

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

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

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Phase transition for the mixing time of the Glauber dynamics for coloring regular trees

We prove that the mixing time of the Glauber dynamics for random k-colorings of the complete tree with branching factor b undergoes a phase transition at $k=b(1+o_b(1))/\ln{b}$. Our main result shows nearly sharp bounds on the mixing time of the dynamics on the complete tree with n vertices for $k=Cb/\ln{b}$ colors with constant C. For $C\geq1$ we prove the mixing time is $O(n^{1+o_b(1)}\ln{n})$. On the other side, for $C<1$ the mixing time experiences a slowing down; in particular, we prove it is $O(n^{1/C+o_b(1)}\ln{n})$ and $Ω(n^{1/C-o_b(1)})$. The critical point C=1 is interesting since it coincides (at least up to first order) with the so-called reconstruction threshold which was recently established by Sly. The reconstruction threshold has been of considerable interest recently since it appears to have close connections to the efficiency of certain local algorithms, and this work was inspired by our attempt to understand these connections in this particular setting.

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

Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets

We study the hard-core model defined on independent sets, where each independent set I in a graph G is weighted proportionally to $λ^{|I|}$, for a positive real parameter $λ$. For large $λ$, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree $D\ge 3$, is a well known computationally challenging problem. More concretely, let $λ_c(T_D)$ denote the critical value for the so-called uniqueness threshold of the hard-core model on the infinite D-regular tree; recent breakthrough results of Dror Weitz (2006) and Allan Sly (2010) have identified $λ_c(T_D)$ as a threshold where the hardness of estimating the above partition function undergoes a computational transition. We focus on the well-studied particular case of the square lattice $\integers^2$, and provide a new lower bound for the uniqueness threshold, in particular taking it well above $λ_c(T_4)$. Our technique refines and builds on the tree of self-avoiding walks approach of Weitz, resulting in a new technical sufficient criterion (of wider applicability) for establishing strong spatial mixing (and hence uniqueness) for the hard-core model. Our new criterion achieves better bounds on strong spatial mixing when the graph has extra structure, improving upon what can be achieved by just using the maximum degree. Applying our technique to $\integers^2$ we prove that strong spatial mixing holds for all $λ<2.3882$, improving upon the work of Weitz that held for $λ<27/16=1.6875$. Our results imply a fully-polynomial deterministic approximation algorithm for estimating the partition function, as well as rapid mixing of the associated Glauber dynamics to sample from the hard-core 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
preprint2011arXiv

Randomly coloring planar graphs with fewer colors than the maximum degree

We study Markov chains for randomly sampling $k$-colorings of a graph with maximum degree $Δ$. Our main result is a polynomial upper bound on the mixing time of the single-site update chain known as the Glauber dynamics for planar graphs when $k=Ω(Δ/\logΔ)$. Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graph is at most $Δ^{1-\eps}$, for fixed $\eps > 0$. The main challenge when $k \le Δ+ 1$ is the possibility of "frozen" vertices, that is, vertices for which only one color is possible, conditioned on the colors of its neighbors. Indeed, when $Δ= O(1)$, even a typical coloring can have a constant fraction of the vertices frozen. Our proofs rely on recent advances in techniques for bounding mixing time using "local uniformity" properties.

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

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
preprint2009arXiv

Reconstruction for Colorings on Trees

Consider $k$-colorings of the complete tree of depth $\ell$ and branching factor $Δ$. If we fix the coloring of the leaves, as $\ell$ tends to $\infty$, for what range of $k$ is the root uniformly distributed over all $k$ colors? This corresponds to the threshold for uniqueness of the infinite-volume Gibbs measure. It is straightforward to show the existence of colorings of the leaves which ``freeze'' the entire tree when $k\leΔ+1$. For $k\geqΔ+2$, Jonasson proved the root is ``unbiased'' for any fixed coloring of the leaves and thus the Gibbs measure is unique. What happens for a {\em typical} coloring of the leaves? When the leaves have a non-vanishing influence on the root in expectation, over random colorings of the leaves, reconstruction is said to hold. Non-reconstruction is equivalent to extremality of the free-boundary Gibbs measure. When $k<Δ/\lnΔ$, it is straightforward to show that reconstruction is possible and hence the measure is not extremal. We prove that for $C>1$ and $k =CΔ/\lnΔ$, that the Gibbs measure is extremal in a strong sense: with high probability over the colorings of the leaves the influence at the root decays exponentially fast with the depth of the tree. Closely related results were also proven recently by Sly. The above strong form of extremality implies that a local Markov chain that updates constant sized blocks has inverse linear entropy constant and hence $O(N\log N)$ mixing time where $N$ is the number of vertices of the tree.

0 citations0 reviewsNo code linkedOpen access