okay thanks Santosh it's really great to
be back here I spent some really nice
years during my postdoc here also I
couldn't think of a better place to give
this talk than here so this will talk
about problems that lots of people here
have worked on and you know it took me I
heard about these problems for three
years and didn't do anything about it
but I guess it finally sunk in after I
left because and now I've now I've
turned to some of these problems okay so
I'll start with a couple questions that
I'm interested in and so one question is
we often hear about phase transitions
and algorithms how phase transitions are
related to barriers for algorithms but I
want to be a bit more specific is it
true that all phase transitions are
algorithmic barriers or certain types of
phase transitions barriers and others
not related to this is if we think of a
statistical physics model at low
temperature so after the phase
transition is there a way to find an
efficient algorithm here and I'll define
what these counting and sampling
problems are what low-temperature means
and maybe a provocative way to describe
this talk is the following the
techniques you can use to prove slow
mixing can actually be turned into
efficient algorithms okay so hopefully
this if you're familiar with slow mixing
hopefully this sounds a bit strange but
I'll try to convince you that this is
the case okay and so this is based on
two papers one joint work with Tyler
Hellmuth and who
Rex Bristol and Amsterdam and the other
with Matthew Jensen and Peter kibosh
both at Oxford okay good
so let's I'll just start by defining
these physics models will will stick to
two physics models today and just review
some of the statistical physics so the
first model I'll talk about is the plots
model and what is this this is a random
assignment of Q colors to the vertices
of some finite graph so here we have a
little grid graph and I guess three
colors and how do you choose such a
coloring so the probability you see a
certain coloring Sigma is proportional
to exponential time of beta times the
number of monochromatic edges so write
the number of monochromatic edges in the
graph under this particular coloring
Sigma okay so to be more precise what is
the probability you see Sigma well it's
e to the beta times number of
monochromatic edges divided by a
normalizing constant to make it a
probability measure this is the
partition function the Potts model
partition function and what do we do we
sum over all possible assignments of Q
colors each of them might bethe number
of monochromatic edges okay so it sounds
innocuous that it's the normalizing
constant but we'll see this as somehow
the key to understanding such a model
okay beta this is a parameter it's the
inverse temperature so when I say low
temperature I mean large beta it's 1
over the temperature and if beta is
positive then the model is ferromagnetic
so we prefer the same color across an
edge and today I'll just talk about
ferromagnetic models one thing you
immediately notice about the
ferromagnetic Potts model is that there
are Q different configurations that
receive the most weight in the
probability distribution and these are
the monochromatic configurations okay
and and so I'll call this a ground state
a configuration that is receives a
maximal weight okay so that's a Potts
model what is the statistical physicists
interested in they're interested in
defining the Potts model on an infinite
graph so say
ZD the integer lattice and how do you do
this while you look at the probably
distribution on a finite graph a
sequence of finite graphs that tend to
ZD okay and look at what kind of
probability distribution you get out and
you have some freedom you have the
freedom to choose boundary conditions so
one thing you could say is you could
make this little grid graph into a torus
by identifying vertices at the top and
bottom or on the sides so we'll think
about this a lot the tourists the
discrete torus
you could have no boundary conditions
you could take the boundary insist that
the boundary vertices all receive red
you can insist the boundary vertices all
receive blue and so on okay so so
there's lots of ways to take this limit
okay an important quantity is the free
energy and here we look at a sequence of
graphs GN has n vertices but n 2zd and
we we look at its partition function
take a logarithm and divide by the
number of vertices okay it turns out
that this limit exists and doesn't
depend on the boundary conditions on Z D
and we call this the free energy so it's
sum is some function of beta it depends
on D and the number of colors okay so
what is a phase transition I'll give you
two definitions of a phase transition so
the first is there's a phase transition
at inverse temperature beta star if
maybe I reversed the inequality so it
should be if beta is less than beta star
there's only one possible measure you
get out you're in the uniqueness phase
there's a unique infinite volume limit
and if beta is greater than beta star so
that's in reverse the inequalities
there's at least two possible limits and
so one way to one way to check for this
is imagine you put all red boundary
conditions on your boxes that grow and
then you ask what's the probably the
origin is red does this tend to 1 over Q
or does it tend to something that's
bigger than 1 over Q okay if it tends to
something that's bigger than 1 over Q
then you certainly have at least two
possible limits because you could take
blue instead okay another another nice
definition of a phase transition is
there's a phase transition at beta star
if this funk
this free energy function is non
analytic at beta star so that means
there's a discontinuity in one of its
derivatives okay so at least we see that
in terms of the phase transition this
normalizing constant somehow captures
the interesting behavior so if we could
somehow compute or get some knowledge
about the partition function then we
would know something about the phase
transitions okay so that's that's one
model the second model that I'll talk
about today the hard core model this is
a random independent set from a graph so
independent set a set of vertices that
don't have an edge between them so here
the shaded vertices are an independent
set of this grid graph and the Hardcore
model is a random independent set drawn
with probability proportional to lambda
to the size of the independent set and
here lambdas the fugacity the larger
lambda is the larger typical independent
set you pick is let me note that if your
graph is bipartite so you have like an
even set of vertices an odd set of
vertices for say the grid then again
there's a bounded number of ground
States there's two ground States here
they even vertices and the odd vertices
and so everything I say today when I
talk about the hardcore model I'll be
imagining it's on a bipartite graph
because I really want to be in the
setting where there's a finite bounded
number of ground States okay and you can
also define a phase transition for the
hardcore model in the exactly the same
way the ground state is a configuration
that receives maximum probability under
the distribution okay so here is just a
maximum size independent set but on
bipartite graph you can just take the
two sides okay so what are the
algorithmic problems associated to these
physics models one is approximating the
partition function so if I just
computing the partition function exactly
this is usually sharply hard so a very
hard computational problem one thing you
could ask is week in it and just ask for
an approximation and we can be you know
quite bold with the approximation we ask
for 1 plus epsilon factor so you know
just just to put that in perspective if
you add one edge to
your graph your partition function
changes by a constant factor okay so 1
plus epsilon factor is really a very
accurate approximation that's one
problem can you do this efficiently
another is output a configuration so
output a coloring a Q coloring of your
vertices or an independent set with
distribution that's close to the
distribution of the model the target
distribution okay and what do we mean by
efficient we would like to do both in
time that's running time polynomial the
number of vertices of the graph and one
over epsilon so the you know the finer
the accuracy you want you should pay a
little bit more in the running time but
only a polynomial in one over epsilon
okay and so if we can do this for every
epsilon with a deterministic algorithm
we say there we have a FP toss a
randomized algorithm we say it's an FP
rass fully polynomial time approximation
scheme and I'm not sure this is standard
terminology but if we can do this
sampling problem in time polynomial and
vertices and one of Reps on them we can
call it an efficient sampling scheme
okay so that's what we would like to do
what are some approaches okay so one
very popular approach is to run a Markov
chain whose stationary distribution is
the target distribution
okay so let's give an example the
Glauber dynamics for the Potts model you
just pick a vertex in your graph at
random this is one step pick a vertex at
random and then update the spin at this
vertex according to the model but just
conditioned on the neighbors so you only
see your neighbors and then you say what
you know what's the probability it's
just seeing these neighbors that I would
have spin blue okay good and then the
question is if we want this to be an
algorithm how many steps do we need to
run this for just groups pick the spin
according to the model that conditioned
on the neighbors
no it's probably proportional to e to
the number beta times number of
monochromatic edges I mean it it's a
nice thing about this particular
probability distribution that the
conditional distribution of the spin
only depends on the neighbors so that's
a that's a good point good okay so one
way to measure this is the mixing time
and you know you come to Georgia Tech to
learn about this mixing times
what's the mixing time it's the the
fewest number of steps you need so
that's starting from the worst possible
configuration Sigma the total variation
distance between the output distribution
and the target distribution is less than
say 1/4 in total variation distance and
then okay so one question is for these
problems let's say on lattices or
something like this when when do we have
fast mixing of this Markov chain and one
very general result is for lattices at
least if we have uniqueness of the
infinite volume measure then we have
fast mixing okay so in this whole region
of the parameter space where we have a
single infinite volume limit possible we
have a fish and helga rhythm can just
run this Markov chain ok right so this
gives you and by a process called self
reducibility you can get efficient
counting algorithms as well so so for
let's say subsets of ZD and the torus at
least below the phase transition point
we know how to do this let me actually
show you a Markov chain strong special
oh I see so there's there's a gap
between uniqueness and strong spatial
mixing yeah ok ok interesting ok a good
point
ok I'm going to show you a simulation
here this is so this is glower dynamics
for the hard core model unoccupied
vertices are white and even occupied are
blue and ah docu pider red and here
lambda is 1
and I started all blue but I think
hopefully you see it gets quite jumbled
okay so one so this is two dimensions
and lambda is 1.0 and we think the phase
transition happens like 3.7 or something
so okay so it looks like it it sort it
sort of looks random completely mixed
around let me now change the parameter
let's put lambda to b6 and again start
all even occupied okay it looks
different right there's one there's not
many that's the point okay this is true
but you can see some evidence of this
phase transition in this finite problem
it's hard for the Markov chain to get to
a state where it's mixed or mostly red
if you start mostly mostly blue now when
I when I look at something like this if
you think which which one actually looks
harder to sample from I mean this one
looks pretty easy I would say just blue
it's mostly blue and then put it in a
few pieces of red okay so so that's
that's the question I mean I think for a
couple years I thought that it looks a
lot easier to sample there but but
certainly not using this framework okay
so we actually know provably that Markov
chains like this mix slowly and so
here's some highlights of slow mixing
results on the torus so this is the
torus the ZD torus for hard core again
we're always talking about even side
lengths okay so this first paper with
lots of authors some of some of whom are
here they show slow mixing for the hard
core model if lambda is large enough
glob or dynamics slow mixing for the
glob or dynamics for pots as well and
slow mixing for the Swensen Whang
dynamics this is a different Markov
chain that lets you do some big global
at the critical point for large kill
some improvements to the bound in this
board stay steadily paper and then even
more sophisticated techniques to you
know use contour techniques to give
better balance for where this phase
coexistence point occurs say on
hardcourt on z2 okay so so these on one
hand show that if you're talking about
mixing time of Markov chains something
bad happens with the phase transition
and also I would say the techniques here
the techniques here are actually the
same techniques we'll use to find
algorithms okay so that's slow mixing
there's other algorithms of course so
there's two special cases so one is the
easing model the two color Potts model
actually is easy so on all graphs at all
temperatures there's an efficient
counting algorithm German Sinclair and
adapted to a sampling algorithm randall
and wilson so for the easing model this
is not a hard problem it doesn't matter
if it's a lattice if it's any kind of
graph you can count in sample also for
the the plots model on z2 so two
dimensions in particular we know that
the Swensen Wang and Markov chain mixes
rapidly for all temperatures that aren't
critical okay and the blue well this is
this is pots but Swensen Wang is able to
like switch between mostly red and
mostly blue yeah right so so one open
problem is show that Swensen Wang mix is
rapidly above critical we know that from
the last slide that it mixes slow at
critical but maybe it mixes fast
above critical okay and so so here's
here's the question beyond these two
special cases can we find provably
efficient algorithms in this phase
coexistence regime okay at low
temperatures on say lattices
I'll say one other thing which is you
can also study these on other graphs so
a nice one is like the random regular
graph or the random bipartite regular
graph and again we know something about
mixing times so we know for the hard
core model if you're if lambda is
greater than the tree uniqueness
threshold so the uniqueness threshold of
the infinite Delta regular tree then
Glauber dynamics mix slowly and actually
this slow mixing is used as a gadget to
show hardness of counting in the
hardcore model for general graphs and
conversely we know that below this
lambda C there is an efficient algorithm
okay so we have slow mixing above for
random bipartite graphs and we have an
efficient algorithm below Potts very
recently some Georgia Tech people again
show that there is an efficient sampling
algorithm in the uniqueness phase so in
the tree uniqueness pays for the
ferromagnetic Potts model so so here I
just mean for random bipartite graph so
right so we have slow mixing for only
bipartite random graph and of course we
don't have MP hardness for bipartite
graphs yeah okay and so so in general
for random graphs can we can ask are
there any efficient algorithms in the
phase coexistence regime except besides
like easing model above the critical so
when there's multiple infinite volume
measures so the pots on z2 this Winston
Wang except at the critical point right
so there's so easing yeah so easing you
can always do z2 pots you can do
everywhere but critical but essentially
that's it okay so here are some results
the first theorems about lattices and so
the result says tell me D at least two
and then there's beta large enough and
lambda large enough so that we can get
efficient
counting and sampling algorithms on the
torus let's say with an accuracy any
polynomial and here are the torus if
you're talking about hard core should be
even sideling okay and then as well you
can do just any regions of ZD as long as
the boundary conditions are come from
one ground state so are all even
boundary conditions for hard core or say
all red boundary conditions for pots
you've got these algorithms I'll note
that what's the running time the running
time is something like n over epsilon to
the log D power so if you think of D is
fixed this is a polynomial but this is
not a nice running time so we'll come
back to this at the end when we talk
about open problems but this is the same
type of running time if you know Weitz's
algorithm that you get and so this works
if D is a fixed constant okay so that's
a that's the results for lattices the
result for random graphs is actually a
result for expander graphs so if you
tell me Delta the max degree and alpha
the expansion factor then there is beta
and lambda large enough so that we have
an FPS an efficient skimp sampling
scheme for pots and hard core on any
alpha expanding graphs of max degree
Delta and again for hard core there
should be bipartite graphs just
ferromagnetic pots you can do okay you
can do anti Farrell pots if you're on a
bipartite graph yeah but but this is
important the these algorithms really
depend on the fact that there's a
constant number of ground States okay so
that was for glob or dynamics mix slowly
take exponential time to mix and now we
say for lambda large enough we have an
efficient sampling algorithm no these
these are large enough they're not this
is not lambda critical
No yeah I'm not gonna run the markup
yeah that's kind of the point of the
talk yeah I mean and I mean this it's
deeper it's not just a throwaway line
it's deeper than that the techniques you
use to show slow mixing or the
techniques will show to show this
algorithm so it's actually tightly
connected okay and in particular this
because random graphs expand this result
ik applies to random graphs okay so any
questions about the results or the setup
we'll start to get into some statistical
physics now good so what are the so what
are the ingredients and inspiration for
the algorithms the way I'll present that
algorithms yeah yeah so FP toss so the
best kind of counting algorithm for
expanding of expanders yeah clobbered
means slow means there's another
algorithm okay so so the way I'll
present the the techniques and the
algorithm will not be somehow the way we
came up with it it will be like the
simpler way once we figured things out a
bit more but I want to tell you at least
where we were inspired by so one thing
we do use is pure Gafsa night theory and
subsequent developments Kotetsu key
Borg's Embry's a radnik this was a huge
topic in the 70s and 80s in statistical
physics and the idea here is you want to
understand a spin model at low
temperature by expressing things as
deviations from ground states okay so a
lot like the picture we saw the
simulation we saw but there's a nice
formal way to do this we're also very
inspired by barba knox approached
approximation okay so his approach it's
it's a very nice idea if you want to
approximate a partition function z this
is a polynomial you look at the tailor's
for log Z and just truncate it after a
certain number of terms almost the
simplest thing you could think of and it
turns out if you know something about
the complex zeros so the zeroes of Z in
the complex plane you can actually
deduce something about how good a bound
this is and this is a deterministic
algorithm so we really you know we came
up with these algorithms trying to apply
his method to the problem his algorithm
actually doesn't give you a polynomial
time algorithm it gives you a quasi a
polynomial time algorithm and Patel and
Rex came up with a very cool algorithm
to compute the coefficients of this
Taylor series up to the required number
of terms in polynomial time and so this
is quite a nice argument okay so I
mentioned that because I'll describe it
in a different way and I'll tell you
what the cluster expansion is from
statistical physics and somehow it
unifies this whole algorithm so in a
sense like the physicists had this
algorithm before they just didn't
realize it was an algorithm and arvy
knock and Patel and Rex didn't realize
that the Taylor series and cluster
expansion are closely related and that
you can you can somehow phrase
everything in terms of this okay and so
and the setting for the cluster
expansion is something called an
abstract polymer model or an abstract
contour model and I think these are
final kind of fun things so let's talk
about it so a polymer model and here the
idea is we have some spin model maybe
it's a Potts model or something like
this and we want to map it to some hard
core model okay the hard core model is
nice big because the only interactions
between the particles is just that you
can't neighbor you can't overlap okay so
it's simple in that way and we want to
map a general spin system onto a hard
core type model okay so what's a polymer
model it consists of a set of polymers
and a polymer for us will just be a
connected subgraph of a host graph so
let's say for example a connected
subgraph of ZD okay but it comes with
some stuff it comes with a weight
function so each polymer comes with a
weight function a function of Z and then
how do polymers relate to each other we
say two polymers are compatible if their
distance is at least two in the graph
okay so they don't overlap they don't
share vertices and there
neighbors okay and so this this is the
whole setup you need for abstract
polymer models and you can define a
partition function just just using this
information so let's say you have some
region of ZD lambda or this is some
graph the partition function is defined
as follows you want to sum over all sets
of pairwise compatible contours so it's
a set of contours none of which are
incompatible so they're all pairwise
distance at least two okay so these are
your configurations and what is the
weight of a configuration well you just
multiply the weight functions of the
polymers in the set okay so that's the
polymer model partition function okay so
they're the easiest example is just a
hard core model itself and you'll see
why you know we refer to the polymer
models like this generalized hard core
model take the hard core model and now
say the set of polymers are just
individual vertices okay so every
polymer is an individual vertex the
weight function is just the identity
function w of x equals x so then what is
a set of compatible polymers well you
need polymers that are a pairwise
distance at least two this is exactly an
independent set in the graph and the
polymer mode model partition function
we're summing over these independent
sets and what's the weight well it's the
product of the weight functions so this
is X 2 the size of the independent set
so the the Hardcore model really is a
very simple polymer model okay here's a
bit more complicated one let's look at
the easing model so this to spend model
with an external field so we're drawing
configurations proportional to e to the
beta number of monochromatic edges times
lambda to the number of say minus 1
spends or or plus one spends okay so
here maybe blue or plus 1 vertices what
are the polymers they're connected sub
graphs of plus 1 spins and so here we
have five polymers
well well the the weight function is
defined by lambda tune the number of
blue times e to the beta a number of
monochromatic edges but I want to
somehow make this simple so imagine
lambda is less than one right so you
have some bad bias against blue vertices
if you think of a big configuration
you'll see mostly red and some scattered
blues and that's where really what we
want we want to capture that picture and
so yep yeah yeah there's different ways
to define it I want to find a way to
define the polymers that give me back my
partition function yep
so here the weight function what is it
well it's lambda - the nut size of the
polymer that's the number of blue
vertices that accounts for your lambda
term in the configuration weight and
then you have to look at the number of
edges in the edge boundary of your
polymer and these are all by chromatic
edges and so you need eetu the minus
beta times that and then up to a scaling
of like e to the beta total number of
edges of the graph this gives you
exactly the partition function but you
see now things are a bit more
interesting right these polymers
actually are geometric objects they're
not just single vertices and then but
the the easing partition function now is
the sum over all pairwise compatible
sets of polymers so you turned it into a
hard core model with these interesting
weight functions ok good yep
you mean you mean join this whole thing
there's multiple ways so yeah so one
thing you could do is you could say it's
all yeah exactly
so we'll actually do that and the
algorithm but you could yeah you can
always say well the polymer is like the
to neighborhood of the blue vertices
right I mean this will affect like your
bounds or whatever but you can there's
lots of ways to do it okay so now now in
the setting of this abstract polymer
model we can define the cluster
expansion and what is it it's it's a
power series for log Z if you think of
the variables being the weight functions
in fact it's not just a power series
it's the Taylor series for log Z but the
multivariate Taylor series where the
variables are all these weight functions
okay that's fine and if you if you
calculate what the Taylor series is you
find some actually a really cool formula
with a combinatorial interpretation and
so what is it as a formal power series
log Z is the sum over all clusters so
now cluster is something different
before we had pairwise compatible
collections of polymers a cluster is
kind of the opposite it's a collection
of polymers whose incompatibility graph
is connected so you have to have like
some overlapping polymers so that the
whole thing is a connected object okay
so that's a cluster we sum over all
clusters we have some coefficient Phi of
gamma I'll tell you what that is in a
second and then again you multiply the
wave functions okay so this is the
cluster expansion
what is this coefficient this
coefficient is the earth cell function
and it only depends on this
incompatibility graph so you have a
cluster it has a certain number of
polymers these polymers are the vertices
of some graph and you're you have an
edge if you overlap if you're
incompatible and then this or cell
function is sum over all spanning edge
sets of this graph minus 1/2 the size
the edge set so this is this is related
to parking functions I think Prasad told
me this is an evaluation of the top
polynomial
it's like T of one zero depending on how
you like to define the top polynomial
but it's very common tutorial object
okay this is great now we have a power
series when as a power series useful its
power series is useful if it converges
so we need to know does the power series
converge and there's there's a lot of
Papers written in statistical physics
about sufficient conditions for the
cluster expansion to converge one very
nice one is Kotetsu key price condition
and so here's the condition if you look
at all polymers gamma and you sum over
all the polymers that overlap with it so
that are incompatible absolute value of
the weight function of this overlapping
polymer x exponential in the size of the
overlapping polymer this should be at
most the size of the original polymer
gamma okay so just to parse this a
little bit what's it saying is somehow
you better have the weight functions
decay exponentially in the size of gamma
prime if you have any hook take kill off
this okay so you need some exponential
decay of the weight function in the size
you can oh that's just the variable so
we have show you in a second gamma is a
polymer the weight functions are
functions of some variable well if it
could be a I mean it's a it's a number
it could be a complex number a real
number so this is I'm thinking about
fixes e here yeah yeah
so fixes II and in the complex
if this condition holds then the
conclusion is that the cluster expansion
I mean I change Z to X so think of Z
being X then the cluster expansion
converges absolutely at this particular
value
okay and and moreover okay so this this
is key
TM of lambda this is if you if you do
the cluster expansion but stop after
you've done all the clusters of total
size at most M so it's a truncation of
the cluster expansion then this error is
at most the volume of lambda times some
exponential in m so that's the
conclusion that if you have this
condition this power series converges
and you have some nice balance on the
error term so X and Z in the end what
Allah set is X will be 1 over lambda
because we're thinking about very large
lambda or X is e to the minus beta okay
let's just do one like concrete example
just the hard core model on a graph of
max degree Delta okay so remember the
hard core model is this polymer model
with every vertex a polymer so a given
polymer is incompatible with it most
Delta plus one polymers itself and its
neighbors right so what do we need to
check we need to sum over Delta plus one
polymers the absolute value of the
weight function is just absolute value
of x the wave function was x e to the
size of the polymer the size of polymer
is 1 and we want this less than the size
of the polymer that's 1 and so this
tells you that it suffices to have the
absolute value of x less than 1 over e
times delta plus 1 okay this is not so
bad actually like as as Delta gets large
this matches the you know the correct
bound the shear bound for the zeroes X
is the same as Z yeah yeah there's
capital Z that's different okay so does
everyone see this is a short little
example of checking the condition so if
you if you're fugacities your lambda is
a complex number but it satisfies this
bound then the cluster expansion for any
max degree Delta graph converges
absolutely
well here here lambdas X right
this is just hardcore model the usual
hardcore model not low-temperature
anything like that we want the partition
function to be the sum of our
independence that's lambda to the size
so the part the weight function of each
polymer is just lambda and so we need
the the absolute value of lambda is at
most okay so that's an example of
checking this condition and now under a
couple of conditions I'll give you an
algorithm accounting algorithm for
polymer models and there they're not so
such bad conditions the first is
polymers are connected objects in some
bounded degree graph okay second
condition of course is this Kotetsu key
price condition holds and the third
condition is that the weight functions
aren't too bad to compute okay so we can
compute these weight functions for a
given polymer exactly and when I say
somewhat easy I just mean let's say
exponential time in the size of the
polymer okay so quite mild
and then then we have a efficient
approximation algorithm for the polymer
model partition function and it's quite
easy what we're gonna do is enumerate
all the possible clusters of size at
most log in now clusters are connected
objects right they they have this
connected structure and the graph they
live in is bound to degree so there's a
most like Delta there's a log n possible
clusters so this is a polynomial number
of clusters you have to enumerate next
we have to compute this earth cell
function this little combinatorial
quantity and each graph since that the
total size of the cluster is at most log
n it has a most log n vertices and so we
use this nice cool fact that the Tut
polynomial can be computed in vertex
exponential time so again this is like
Delta to the log N and this is
polynomial and then what do we do we
just compute this truncated cluster
expansion and output the exponential of
this
Emma's gonna be log n yes it's gonna be
like log of n over Epsilon yeah okay and
so then we then we output this and the
context key price bound tells us that
this gives us a good approximation to Z
I haven't I haven't talked about
low-temperature models at all yet so
this is just some some abstract thing we
have an abstract polymer model this
example would work for hard core at low
fugacities on any graph but I haven't
gotten to that point yeah okay so any
questions about this algorithm okay now
you can ask how to sample from a polymer
model and normally you do something like
self reducibility you set one spin and
then you go on and you say what's the
probably this spin would take this you
can't quite do that in our setting
because you know we have very specific
boundary conditions you might ruin these
by setting a spin but what's nice is you
can actually do self reducibility on the
level of polymers and so the algorithm
goes something like this
you pick a vertex in your graph and what
what you want to sample first is just
does a polymer pass through this vertex
and if so which one and once you fix a
polymer that passes through this vertex
a bunch of polymers that would be
incompatible of this you have to throw
out of your set that's all you do throw
them out of your set and repeat okay and
the nice thing is that somehow this
Kotetsu key price condition or absolute
convergence of the cluster expansion
this is monotone on taking subsets so
you can imagine if you have less
polymers this condition is only easier
to satisfy so you get this for free but
that's that's all I'll say about
sampling
okay so we can we can go to expander
graphs now so let's do the Potts model
on expander graphs and here we'll get to
a finite number of ground States so the
first step in approximating the
partition function is just to say that
just by the expansion property the
partition function of the Potts model
for large enough beta on an expander
graph is well approximated by the sum of
Q different partition functions where
each one is just summing over
configurations with like let's say a
majority red
majority blue and this is exactly the
type of thing you would want to prove if
you wanted to show slow mixing okay so
and for an expander we graph this is
quite easy so now what do we need to do
we need to approximate each one of these
partition functions okay so let's let's
take the red partition function now we
have a mostly red model and we want to
express this as a polymer model we just
define a polymer to be a connected
component of non red vertices okay
that's it
and I have to tell you what the weight
function is the weight function will
just be e to the minus beta the number
of by chromatic edges incident to the
polymer in particular the entire
boundary has to be by chromatic because
it's non red vertices and everything
else is red and so you have at least
that many by chromatic edges and because
if expander' graph the edge boundary is
sum as proportional to the size of the
whole polymer and so we do get this
exponential decay of the weight
functions if beta is large in the size
of the polymer and that's that's the
whole algorithm so you just check these
things and you plug it into that that
polymer algorithm I told you about so
here we are using the fact that we have
these ground States because we say we
can express the model as the sum of a
finite number of models where some nice
properties happen okay good so in the
last few minutes I'll tell you about
contour models so the point is on ZT we
can't do this you you know we could have
an all-white state outside and then you
only pay a cost on the boundary but this
the boundary size on Z D is not
proportional to the volume so it's both
plots model but this is on Z D now
instead of expand or graph and all I'm
saying is that the the boundary costs
you pay these by chromatic edges is it's
no longer proportional to the size of
this set so you somehow have to deal
with this
yeah and that's that's not enough yeah
that's this exponential decay it's like
e to the minus beta by chromatic edge
the polymers have to expand ya edge
boundary of the polymers okay so what
are contour models contour models are
polymer models but each polymer comes
with boundary labels and so a polymer
here the polymers are the contours are
the black regions and what do I mean by
boundary labels they have a color
outside so the exterior label of this
contour is white and then it might have
some interior regions so the interior
label of this region is green and blue
here okay so a contour model is a
polymer model but with boundary labels
and each each region that the contour
divides your space into is labeled with
a ground state okay so precisely a
contour on ZD it's a connected component
comes with a weight function
it comes with an exterior label and
labels for each of its into your
components so exterior white interior
blue and green for these two regions you
still have to say which spin is outside
yeah okay and then what is the contour
partition function well it's the same as
the polymer model partition function you
sum over sets of compatible contours
multiply the wave functions but there's
a restriction your your contours have to
have matching labels so if I'm a contour
here this contour this little triangle
it has exterior label Green it better be
the case that the guy it lives inside
has interior label green so this is what
we mean by matching contours and all the
contours on the outside if we have white
boundary conditions they better all have
white exterior label so that's all we
mean it's almost like a polymer model
but this matching condition is a
long-range correlation so it's not nice
and so the idea of pirogov and Sanai is
to rewrite the whole thing in terms of
outer contours so just look at the
contours that are on the outermost level
and forget about everything inside
okay so I've erased all the contours
that appear inside another contour and
you can actually just rewrite the
partition function you still have the
same partition function you multiply
this wave function but now you multiply
also by the partition function inside
these regions okay and now the sum is
over sets of compatible contours that
are mutually external none appears
inside another and this is really a hard
core constraint okay it's like that the
the filled in volumes don't overlap and
so now now we're now we're good to go so
this is a polymer model it just happens
with the wave functions are more
involved it's the weight function you
had before multiplied by the interior
partition functions but now I really
you're in the setting of polymer models
and we can apply that previous algorithm
yeah exactly right so we need to compute
the weight functions and that will be
the recursive step okay so check the
convergence criteria this was all done
for us okay boards and Embree have a
very general criteria if you have a
piles condition you get this convergence
well they were trying to understand the
phase transition so this pure graphs
tonight there is a way to understand the
you know the probabilistic properties of
the model you know do you have
exponential decay of correlations once
you condition on the phase is a
first-order phase transition well the
one thing that was proved using this
technique is the dot Potts model for
large Q has a first-order phase
transition maybe that's the most famous
thing
but also the the slow mixing results I
mentioned were proved using the same
technique and then like you said how do
we do the weight functions we compute
them inductively so you start with thin
contours that have no interior regions
those you just have the wave function
and then once you've done those you can
go up and up and up okay good so just to
show you what the contours are for the
plots model and Z D you call a vertex
correct if it shares like the same color
as all its neighbors everything else is
incorrect and here neighbors like Dana
mentioned you choose something slightly
different this is an L infinity neighbor
this makes some topology easier so
shaded vertices are incorrect there's
some disagreement in the L infinity
neighborhood and and a contour is just a
connected component here okay so we see
like this contour has exterior label red
and interior label green okay so it's
easy to define and then the number of by
chromatic edges it's proportional to the
size of the contour and so this is Pyles
condition that's what we need well
because we're not we don't include the
interior volume in it it's only the the
ones would have a disagreement and you
have a disagreement somewhere in your
neighborhood so like yeah okay so the
last thing I'll say in the last two
minutes this because I think this is a
good open problem for lots of people
here is that the running time of this is
polynomial but far from linear and so
you would want a better algorithm this
somehow is not the algorithm I wanted to
show works
there's a very simple algorithm that I
wanted to show work that I couldn't so
for these models with a finite number of
ground States maybe the graph is
transitive or something but pick a
ground state uniformly at random start
in the ground state start with all red
configuration and run the glabra
dynamics for n log n steps and I claim
that this
the output is close to the stationary
distribution once you include the
randomness of the choice of ground state
as well and perhaps you can actually
prove this if you if you are in the
setting where pure golf Sanai theory
works so you have convergence of cluster
expansion this gives you some
correlation decay properties can you use
this to prove that this algorithm works
this is like a near linear time
algorithm very simple algorithm this
should somehow be the right algorithm
okay so actually with prasad and
jennifer chase and christian Borges we
can now do like Potts model on Z D at
critical even at critical where we know
Spencer Wang mix is slow and all above
critical for large Q so for Luke if Q is
large and you're on Z D then everywhere
very large like exponential and D yeah
yeah I can tell you more about that okay
so let's see the other thing I won't
talk about this just this is related to
this complexity class Sharpe this
bipartite independent set and one
question would be for what classes of
graphs can we define contour models you
can't do it for all graphs like a 1d
align you can't define contour models so
is it true my my very bold guess would
be if you have a transitive graph that
isn't 1d you can do it vertex-transitive
so no vertex is special any lattice
that's two-dimensional we can do so that
actually it's quite easy
yeah so it has to be at least two
dimensions
it can't be 1d but then any lattice is
fine okay so thank you
hmm that's a great question so fixing
magnetization can be very very bad so if
if you have like the hardcore model on
the random bipartite graph that's a very
nice model but if you all of a sudden
fix magnetization so it's 50/50 1/2 1/2
evens 1/2 odds somehow I don't think
this is proof but my physics friends
tell me that this becomes like the
random graph the non bipartite one with
like glassy phase transition on all the
horrible stuff so so you can go from a
really nice bounded number of ground
States model to a the worst possible
situation by fixing magnetization well
maybe I mean I think that's roughly the
intuition if you can describe it really
well probabilistic aliy there probably
is some simple decomposition that you
can use something like this ah because
all those proofs of slow mixing that I
showed you there they're using pure
graphs in eye theory they're using piles
condition yeah and they're they're
counting contours and it's exactly the
same techniques so we actually there are
a lot of this stuff that needed to be
proved was already proved for us in the
paper showing slow mixing so it's not
that slow mixing implies a good
algorithm is that the techniques people
have used to prove slow mixing we can
use for the algorithm
yeah no but I mean like the general
result here for ZD would say if you're
on a lattice and the piles condition
holds then there's low enough
temperature so that there's a algorithm
so all we need is piles condition and
boundary gram sense