So this is a joint work which I have
a scanner and Cynthia Evans and.
This stock is very interactive so
please feel free to ask questions like.
OK so what's the what's the main problem
we are trying to address here so
the simplest form you can describe
it in is this you have some field
you have some vector space over this
field this doesn't have to be R.
It can be like a fine if you.
And you want to count the number of linear
basis you can form of these victors.
A bunch of actors in this space and
you want to counter the near bases or.
More generally you want to count the in
yourself that the subsets of size
which are the Near the end event so
why why do we care about this
problem it has a bunch of groups.
So the reason we care about this problem
is that it has a bunch of applications I'm
giving you a couple of them so for
example including theory if you have
a linear code over some fields.
There are many ways to describe it
using a pair the check matrix or
a jury there are many three X.
So let's say you have this pair
the check matrix defining your code.
Then if your if a bunch of bits in
your code get a raised you can recover
from those errors if and only if
the corresponding columns in the pair of
the check matrix are legally independent
so if you're able to count the sets you
can talk about probability of recovery
from readers I think that's one way to be
motivating application graph through graph
theory you can compute the reliability
of a graph or you can count forests
depending on what you're interested in.
And it has a bunch of other
applications to OK So
this stock is actually
slightly more general.
It's not only about victory spaces but
it's about many troika so many trades
are this concept of point to generalize
linear independence in directory spaces.
So you can there are many many ways of the
finding a mate Roy I'm going to give you
one definition in terms of independent
sets so you have this ground search of M.
elements one through M..
And then you can see there are a family
of subsets of one through.
These are called independent sets they
have to be down more closed so for
any any independent set any subset of it
is also an independent sets I think of
independent sets in the vectorial case and
also you have this property which
is that if you have a larger independent
third if you have two independent sets one
is larger than the other there is an
element from the larger set you can add to
the smaller one so
that you are still leaning in different.
So if you have a bunch of independent
sets if you look at the maximal ones
amongst them these are called the bases.
And it's not very hard to show that these
two axioms show that all of the bases must
have the same cardinality so that's also
often called the rank of them a choice.
You can you can translate these axioms
into axioms in terms of bases and
you would still get than
the equivalent definition
there are other sets like flats and
circuits.
Again you can define your major and
in terms of them I'm not
going to go over them so
so the problem in terms of me
Troy becomes the following so for
many of them a choice that we can't
that we care about we have such a thing
we have this thing called
the independence Oracle OK so
what is a new kind of circle do you
give it a bunch of you give it a subset
of the ground third it tells you
whether it's in the Independent or not.
So for example in The New York
case you can do it by gosh
an elimination for example.
So it's well known that having this
Oracle is equivalent to being able to
optimize linear functions over
the bases OK up to par mealtime
reductions so so
you can you quote you think of
having an Oracle which optimizes linear
functions for you and then the question is
can you approximately count the number
of bases using these sort of OK.
So you can you can slightly generalize
this to a very good problem where
to each element in the basis you
are basically a sign of A to Z.
right and then the basis
becomes the product of Z's and
now you want to compute the partition
function of this dissuading OK so
the sum of all of the bits or at least.
So all of the things I'm going to say
generalize to computing this at arbitrary
positives East but I'm only going
to be talking about the uniform
case where these are one nevertheless
I'm going to use this Pongal OK so
it's important that you
understand the definition.
So so if you have such an oracle there
are some natural things that you can
do with it for example you might
assigned random weights and
then choose the basis that
maximizes this weight so
so so these ideas have been explored and
there is this paper.
Which basically explores this for not just
made choice but for basically any family
for which you can optimize and
they also get nearly optimal balance.
So saying the worst case their brands are
worse than what I'm going to show you but
I just wanted to mention that
that idea has been explored OK.
Yes.
Yes yes from some parts you have to
design how you sample the weights but
you have to design a distribution from
which you are sampling the weights.
So they found that basically the optimal
distribution from which you can sample and
this gives you an estimate or for this.
It's a little hard to explain what
the quality of approximation is
it's not really for example it doesn't
give you any constant factor approximation
sort of gives you some approximation of
the log of this partition function of
it's not an additive anyway so
let me not get into it.
OK so here are a bunch of examples of may
throw it I'm sure many of you have seen
a lot of these so
the linear case is really the most
intuitive case so I just described.
The laminar case if you have if you if
you look at all subsets of one through M.
and you put a bunch of cardinality
constraints on them so the cardinality
constraint is that your search must
have at most K.L. events from a set S.
if if these cardinality constraints
do not cross each other if the sets
defining them are lambing are meaning
I don't nested inside each other or
this joint from each other
then this gives you a way to.
So for graphs.
If you fix a number K.
and look at the collection of all.
Subsets of edges that form a connected
graph these are the bases of I'm a droid.
So for cake was and
minus one desire all the spank trees.
But for larger K.
This is also me Tory and.
Already in this case the exact
counting base is the heart.
So try to transfer saw an algebraic or
two other families I'm not going to go
over them so let's let's think about
the most intuitive case of may try
expanding trees OK so here is a graph K.
for the complete graph and
for a very disease.
Does anybody remember how many
spending freeze this guy has sixteen.
Here's all sixteen of them.
OK now let's fix it.
Yet labeled.
Yeah we're not trying to count things so
now let's fix an agency how many of
these spending trees contain the I.G..
In this particular example.
Half of them yet so this guy has six edges
every spanning tree has half of the edges
and everything is very symmetric so
half of them have this right so
this fraction fraction
of spending three is
that contain an edgy I'm going to
call it the marginal of edgy OK.
It's also equivalent to
the effective resistance of that and
I don't know depending on how you
define things leverage score so on.
OK.
Everything is symmetric right.
OK so
so now let's do this thing so
assume that some graph is given to you
I'm going to write down the marginals of
all of the edges and then the razor graph
Now I want to see what information I
can extract from these marginal for
example this original graph I showed
you it becomes six one house.
So let's do a simple example let's say
that the marginals are all once OK so
this already shows you that this
map is not one to one OK so
so any guesses as to what graph
skin can get give you this.
Trees spending trees and
any spanning tree gives you this right.
Any site any tree gives you this so
it's not a one to one map.
The top right thing is
a graph I haven't shown you
gives you the marginals one one one.
Or the graph only has
four edges exactly sorry.
For me yet.
So what's the number of everything is.
Right.
But in general you can't you can always
recover the number of vertices given these
margins because if you sum up these
marginals you get the number of edges in
a spanning tree which is one minus which
is one less than the number of ways so
you can always add one to get the number
so what's the number of spanning trees.
In this case it's one right because
this is a tree OK but what about
this case so this is similar to before
six one half six at either two one to it.
Any guesses as to what this
could be the number threes.
Yeah if you add two dangling
edges to your graph.
You still get these marginals and the
number of spending trees could be sixteen
but there is another graph which
gives you these marginals and
this graph has only eight senators so
you can't recover the number of spanning
three uniquely from the original.
Even if you don't I'll pile edges or
more complicated examples.
But what if I wanted to get
an upper bound or a lower bound for
the number of spanning tree is there
is an easy way to get an opera bow
using some added to beauty
of the entrepreneur.
So let's say that you pick a uniform
the random spanning treaty OK.
So I assume everybody here is
familiar with what the entropy is but
just within the definition here for
a discrete distribution you just sum
over the support of that distribution P.
log one of our people.
OK so
if you have a uniform distribution of
a bunch of elements the entropy is
log of the size of the support.
OK so if you want to compute exactly this
entre peaches log of the number spent
right now you can look at the projections
of this random variable on two edges so
what I mean by that is think of
an indicator around them are able X E
which is one of a never a G.'s
in your spanning tree and
zero whenever it's not right so
it's a new year on the variable right.
Now if you look at the collection of X.
years it has the same
joint distribution as T.
right because if I give you which
edges are in the spanking or
not you can define the tree uniquely so
the entropy of T.
is really the entropy of
the joint random Abel's X.
one through X.
and then you can use the sub additivity
of the own trape to show that this
is less than the sum of the entropy of
the individual exercise right now each X.
i is really just a Bernoulli random area
of all I can I have the probability of
it being one which is exactly
the margin margin of the.
So I can compute these and
I get an operable right.
Now what's surprising is that for
us finding trees this upper bound
is quite up to a factor of two.
So it's also gives you a lower bound so
before before going
to the proof of this fact let's say what
this lore of on this for example we had.
So the UN trophy if you
write it in the log in.
A thumb in base two.
This inequality tells you
that it's between three and
six each of these one house is giving you
one bit of entropy you have six of them so
you get six as an upper bound and
three as a lower bound right so if you
explain initiated you get that the number
of spending trees is between eight and
sixty four and I already saw that it could
be a tight example sixty four is not.
For spanning trees I think
this is never tired.
But for me to read.
So so so let me give you a proof of this
fact Mind you though a basic assumption
get to that assumption in a minute.
But this is what we want to show that
the twice entre of the spanning tree is
bigger than the sum of the entropy
of the individual edges right so
the sum of the entropy is of these very
new on the way it was you can be composite
into two parts right you get people
like one of R.P. first one minus speed
log one of one minus right so instead show
that the entropy is bigger than each part
so here is the basic assumption we need.
To remember this generating power in the
other they defined a couple of slates ago
so this is just to go over it again this
is a dating problem this is a power.
Defined over variables
there is one variable.
For you spanning two you multiply
the variables and then use some of this
overall spanked the property you are going
to use is that is the fact that this
generating power wheel is locked concave
as a function over the positive working.
OK I'll get to why this is.
Later in the talk but for
now let's just assume this.
So once you have a contact with
your convexity results what can you
do with it you can write inequalities for
example the instance inequality OK so
we're going to appliances inequality.
So for us is inequality I have
to define a random point Y.
and then use the fact that.
My function a value that at the
expectation is bigger than the expectation
of my function it's a log log
of Despond really is a function.
So what's the natural way of defining
around the point well you have
random spanning trees so why not look at
the random indicators of spanning trees.
Those do not have an expectation
that you can work with OK so
if you look at the expectation of
the indicator of around them spanning tree
gives you the vector of marginals but
I don't want to evaluate my palm wheel
at the margin Also I want to value my
palm you know that all the ones right so
there is a so what you do is basically
you just scale the indicator of
a spanning tree so
that the expectation becomes one.
So I divide each of the X.
I's by its expectations so
now the expectation of my random
point is just the old ones right.
So in particular the left hand side
I mean sensing quality becomes log of
the Pongal I want to evaluate which is
the log of the number of strategies.
So what about the right hand side.
So if and why is a scale version of
the indicator of a spanning three right.
All of the terms in this formula disappear
except that spanning tree right and
I get the product of one over a piece for
that spanning tree right log of this
I have to averages over all spanning
trees because I have a lot of product it
decomposes and I can look at the number of
times each year appears here so I get P.
E.
times log want to repeat so
that's the whole proof of this inequality
from just the fact that I was lucky.
I don't know P.C.'s I'll get to
that much later in the talk.
For now this is just
a mathematical result so
you can you can actually
generalize the proof.
To basically arbitrary distributions
on hyper Q OK The proof is almost
the same exactly almost exactly
the same way so what this tells you
is that if you have any of this tradition
on the vertices of the hypercube.
If the jury think of it is lucky if so
here for
each term you just multiply
by the probability of that.
Then you have this
inequality that the under P.
of your distribution is
at least the sum of P.
I like want to repeat I forgot to say
something I showed you only one side
of this right I only showed you that the
entropy of Spanish is bigger than this for
the other side you have to look at
the complement of spanning trees so
the do all of the spanning three Matrix.
I promise you that that part you get for
the door later it is also like concave and
you get the other side
of inequalities right.
So yeah so this is this is just basically
the natural generalization of it OK.
So.
So I have this inequality for
any distribution with.
The additive gap between the two sides.
Is the terms is that most the number
of terms that you're missing
from the sum of the Bernoulli entreprise
right recharger just the one minus P.
log one over one minus B.
right.
So Tara my term if you look at this
you can operate this by just P.-I OK
this is a this is an inequality value for
each guy so
the additive gap between the two sides
is at most the sum of the piece right.
So if your distribution is supported
on that say a slice of the hypercube
very there at most once write
this this is bounded by K..
So the additive gap would be bounded by Q.
OK so that's why this this
basically approximates your entrepreneur
the entropy of your distribution.
If you're approximation is good whenever
your distribution is supported on
a slice of day now you
know we get to dangerous thing part of
the journey that a promise to you is like.
So in general there are there are multiple
ways you can prove that certain policy has
a lock on cave here a couple of them in
particular for spending trees you can use
this fact if you have a bunch of P.S.T.
matrices A one two am.
Sort of the mix you can get from them so
determinant of the sum of the I
this is always like I gave.
The real positive worth and it's lucky.
It's really not that hard to show it and
you can even generalize this to any real
slave upon the US If you know what that
means OK if you have any real civil Pommy
of it negative call fish and it's going
to be like concave over the positive or
there is another way using mix volumes.
So if you have a bunch of convex sets if
you look at the volume of a mixture of
them so here scaling each K.-I by and then
taking them in Kafka's some of them and
then taking the volume first of all it's
going to be the Palm Island as the eyes
and second of all it's going
to be a lock on keep on.
So you could ask so yeah so
I already told you that spending trees you
can get it from this so AI's would be
sort of the law plus eons of ages.
You can also get some interesting
distribution such as the timing on top
processes and things like that by
this way but you can ask can you get.
Any may trade using these methods and
the answer is no.
So first of all for any anyway when you
can get from this would basically be
a linear meter reader where are so
that doesn't cover all NATO it's so
really the question is.
Can you get a real simple Pongal for
anyway joy and the answer is no.
In a strong sense so
Brandon in two thousand and
seven showed that there is a specific
me Troy the phantom a Troy and
any distribution of it for support
on the basis of this phantom a Troy
with would have a jury the problem
you are that is not real stable.
So forget about even
the uniform distribution or
distribution is going to give
you a real civil one OK.
So you have to you have to if you
want to prove lock on cavity of
the generating power you have to use
some other way and that's what we did.
We proved that the four anyway
Troy generating part of the bases
is locked concave as a function
over the positive or.
Not so
if you have a real civil power
mule it's going to be balanced
it's going to give you a bias meter but
I don't know of any.
Proof of the reverse direction.
Most of the known examples of balance
matrix give us that while in the US.
I don't know if there is any counter so.
It's linear over F.
to the fundamental it is a linear way
to it but over a finite field that
are so so that's what we proved.
So the proof relies on this.
Series of breakthrough is by.
The procedure and cats and we specifically
use a follow up result by hand bank.
So they they lie in this thing that they
call the highest theory for me Troy.
So one thing I should mention is that so
harsh theory you can think of it as a I
guess framework that they can appear
in any area of math you like.
So there are high series that also
prove these two things so there is
a high security for these there is a high
story for these and from the High series.
For these objects and these objects
you can also get some things.
But before so I'll give you a sketch of
this proof before before going through
that let me also just mention that
there is also a converse of this OK so
if you have any distribution
that is home organist so
it supported elements that
they have on the cave once.
And who is generating
part meal is LA concave.
OK then it's going to give you.
Yet it's going to give you
the basis of a matrix right so
this is really a characterization of made
toys in terms of our country following its
Yeah caves that are there so
there are ways to generalize
this to beyond homogeneous and beyond
multilinear pong but I'm not going to.
Talk about that in the sense of no
coefficients can be arbitrarily
negative numbers all.
The non-zero there so what I mean by
support is the nonzero set of course which
case will give you a sketch of this.
So OK so.
Because this is not such a long
talk I've extracted the black box
theorem from the theory of evil by Jr and
others.
So here is the black box
theorem that they have proved.
So if you have.
Remember this was the generating
colony of your mate Roy.
What they proved was that
this particular me tricks so
this is I'm going to define what it is in
a second but this particular matrix has at
most one positive like about SO B.
I J So this is my shorthand notation so
I use B.
to note the number of bases B.
I to that to denote the number
of bases containing I and B.
I J to you know the number of
bases containing both i and j OK.
So this matrix has zero
as on the diagonal and
on the after are going to as it has B.I.G.
OK And
this end Miami cheeks you
can you can easily see that
this matrix is just ahead of
the Pommy all at the point
because when you differentiate with to
speak to X I X J All of the terms that
don't contain I N G disappear and then
you get exactly the number of bases that
contain and yes.
OK So this is what they give me.
And I get I'm not going to go
into the details of that this is
this is the most heart.
Yeah but so
they prove this is by HI Story.
We can talk later about it but yeah.
OK.
So OK so what is our goal our goal is
to show that the history of the log of
Pete is that you Gene is
negative sign a definite
right at all points I'm going to
show you the proof or the Point One.
I want to show cave which is according
to this being true at all positive
points I'm going to show you this for
the point of one's OK
it's not very hard to go
from one to Joe It's so
so if you if you take
the whole scene of R.P. G.
you get this expression.
Divided by G.
squared.
Trust me OK So do you square this is
just a scalar it's a positive scalar so
you can just get rid of it so it's a go
into showing that this is negative.
OK now this looks awfully similar to this
thing right you have the history and
here you are multiplying
it by a scalar and
subtracting the rank one
thing from it right.
But I tried many ways and I couldn't show
that this rank one thing is enough to
just directly you tenth at this I
think directly working with just this
family of there is no way of showing that
the strength one thing kills the positive
eigenvector here is here is another
perhaps more clever way so.
Think of your matrix and
take a copy of it.
OK so I define new elements
one prime through and
prime I take a copy of my may
try it on one prime through M.
prime and then I look at
the union of these two matrix so
this is a very the bases are one you you
select one basis from one through M.
and you select one basis from
one prime through prime.
And take the union that's the basis so
this is sort of like a direct
some of the two a tree.
If you if you apply the theorem
of bank two to this mean Troy.
You get M H You get a matrix which is
in a block forming a two by two block for
right.
So so what are the blocks so
I'm writing basically one two M.
here and then one prime through M.
prime here.
So if you want to so that if you select
two elements from the original Matrix
the number of bases that contain
them in the direct sum is just B.
I.J.A. times the number of bases you can
take from the other matrix so you get B.
times B.
A J.
Here if you select on
elements I an element G.
prime or today.
The number of bases containing
them would be basically B.
i times B J prime rate
which is the same as B.G..
So you get this you get this form and
you can you can define that in terms
of the hair C.N. and gradient of G..
You get this for now the expression
we wanted to show was negative so
we definite You can get it as linear
expression over here OK so you just
multiply I minus I and I my and both sides
of this matrix and you exactly get this.
I'll give you one second
where you find this.
I mean just just to block
like matrix multiplication so
you get this plus this
minus this minus this and
then you divide by two Now the thing is
that we know this matrix has only one
positive I again value I get back there
corresponding to that has to be symmetric
because this matrix is very symmetric.
If you swap the two blocks both in the row
and column you get the same a chick's So
the positive I can make three must
also have the same symmetry so
in particular if you write the two blocks
of the eigenvector they must be equal
right because when you swap them you go
also get an eigenvector and then you can
sum them up to get a symmetric thing and
because it's unique that must be it.
So but the thing is that if we want is
equal to be two this is in the kernel of
this thing that we are multiplying
on both sides so it gets killed.
Right and what you are left with is
basically the negative seven definite part
of this major So any questions
you know.
So.
So as long as you have the high
surely they prove using the.
So they prove this hard theory which is.
Which is something about the.
So maybe you are talking about
the different paper of finding but so
as as long as you have the ring which
is defined in terms of the flats
the variables assigned to the flats you
can you can basically go through all of
the steps of their proof and
everything works out so
yeah so OK Let me let me say
something about this so.
This theorem in its current form appears
in the latest paper by Ha invariant
as just a theorem without a proof.
They promised that the proof
appears in a later paper but
you can reconstruct the proof from the
stuff they already have in their paper.
So maybe that's.
So yeah I promise you that they
have a proof of this based on
the early results by.
The procedure who gets
heart gets all right so
now back to counting so I've shown
you that the other lock on cave.
But it's going back to the fact that
we don't have the margin else OK so
what I've shown you is that if
somebody gives you the marginals you
can count the number of bases up
to that additive factor of rank or
a multiple good factor
of two to your prick.
OK The problem is that computing
marginals is just as hard as counting.
In a precise owns but
there is a solution to this which doesn't
lose anything in the approximation factor.
So the solution is this so we know
that the vector of marginals we know
some feasible search for it we know some
constraints that we can put on it OK
what is a constraint so the so
I think of this polytope
very divergent these are the indicator
vectors of the bases.
Then the marginals are exactly
the average of all of the words right.
So in particular the marginals lies in
the comics whole of these points right.
Now I have an upper bound which was
the sum of the entropy of marginals
if I maximize this upper bound
over the entire polytope
I still get an operable OK
maybe a larger upper bound.
But what I'm going to show you is
that that's still good enough.
One thing before going and
if you have this pilot or.
Optimization over those follow it up is
basically equivalent to having access to
the independent Oracle for The Matrix or
being able to optimize over linear
functions over the base so
you can do optimization over this and
this this this function that we
are considering is just concave so
it's concave up optimisation
everything is going.
So what I want to show
you now is that this
result of this comics program
is still a good approximation.
So without any assumption on
various that it's coming from this
this thing is always an opera bound.
But what I want to show you is that for
me towards this is also up
to some additive term lore
therefore you can get an approximation
right so so fix some P.
in the comics All right the definition
of the comics whole is that
you get a point in the comics Califano if
there is some distribution on the basis
who's marginals R.P. that's just
the definition of a comics all.
Now other all distributions
that can have the marginal P.
There is a particular one
I'm interested in it.
And that's that's the one that has
a maximum possible entropy OK so.
So that maximum entropy distribution you
can always write it in this special form
this is a fact used in many places by
many people that the maximum want to
produce to reach always has this for
a very US sign a positive or
negative number to each element and
then the probability of choosing
a basis would just be proportional
to the product of the Lamb dice
OK So so yes so there is for any given P.
You can find Islam dice you have
to be slightly careful that P.
is not on the border and so
on but those things you can easily
take care of by taking limits.
But OK if I have this distribution
new which is like this
that this Russian new is still has
a lock on Cave generating power meal.
Because the joining palm you have new
is basically the generating power
of the uniform distribution
where you replace the i by land.
Right and this is an operation
that preserves lock on cavity OK.
So now we are done because for
distribution new I know that the entropy
of new is that this the sum of your log
one of R.P.I. right but other of all
distributions on the set of base is the
uniform as the maximum entropy right so
the entropy of the uniform is still
bigger than the sum of one of the P.R. So
I still get whatever I had for.
So what this tells you is that if
you have a choice given to you using
an independence or a call there's
a deterministic on your time algorithm so
optimization is just a terminus tick
which off with a number which is
the of rank multiplicative approximation
also an approximation of this
form because remember we had the two
factor approximation to the entre piece
of that translates to a square root
up like summation you're right so
sometimes the this this one is better than
this but usually you care about the state.
OK.
And then there is an old result of US
Arbor they're free is stated in a slightly
different language but what it tells you
is that there is actually no the terminus
to Calgary from that can do much better
than this OK so any deterministic
algorithm can only offer the factor
an approximation which is worse than this.
So after the log terms the terms
this is almost optimal
this is an information theoretical orbán
so there is no hard and assumption or
anything as long as you only have access
to your way through an independent
Oracle you can't do better than this but.
But.
One other surprising thing is that
the same complex program we had.
Not only does it work for me Tories but
it also works for the intersection of two
matrix OK So this is you you have to meet
with defined on the same ground search and
you're only looking at the common
basis of the two way trees so
you get things like perfect matchings in
bipartite graphs and things like that by
taking the intersection so
in the remaining time let
me tell you a little bit about how such
a result is proved for a day intersection.
So given to me a choice of it bases B.
one and B.
two you can define sort of like a mixture
of Palme your for them.
OK so I'm defining two sets of
variables why one through Y.
and Z.
one through Z.
and.
So the turn is in my palm
y'all are a basis from.
The complement of a basis from B.
two to the terms that don't appear in B.
in a basis in B.
to multiply them and then I sum this
over all choices of the one basis.
So in a compact form you can write it
like this you some where all bases Y.
to be white or to be one Z.
to that one might expect.
So this far what I was ovation is
that this fall I'm going to still
offer him a choice OK What
is that May Troy you take
your second mate to eat and two you
take the do all which is whose whose
base is are basically the complements
of the original made to a species and
then you take the direct some
of these two so this is still
the generating problem in all the way
to it in particular it's lucky.
The first observation you can have
about this standing Carville is that
the quantity of your after the number of
column basis you can extract it from this
problem will by applying some
differential operators OK So
let me let me parse this for you so.
I'm just applying partial
why I plus partial Z.
I.
For for all eyes from one through M.
to my major to my drinking
problem you know.
I guess you don't need
to set these to zero.
So why is this number of column bases so
so when you're applying this.
This differential operator what you
have to do is from each parenthesis
you have to either select partial Y.
or partials the eye.
And then you get the Manami
of it the partials and
then you apply it to the j to
this mixture to this mixture.
So look at the look at the terms for
which you selected partial why I.
Do or sounds have to be the subset
of a basis of and one other voice
your you get zero write the complement
terms from which you selected parts
of the I have to be the subset of
the the complement of a basis in them too.
Otherwise you would get zero right and
these two conditions basically
tell you that you only get things.
You want to be two are equal OK So
any any term you want is not equal to
me to just get killed by this operator
the terms that are common between
the two interests for me.
If you've But
if you've seen cat isn't saying
things like that this is sort of
a it's related to that line of work.
Just a pointer.
OK So because we're applying
differential operators and.
Locking cavity is no longer enough for
us so we had to prove something
slightly stronger you can still prove
it using the results of who had all.
Tell what we proved was that this family
all the journey popular made Troy
is not only large concave but
completely locked concave that's a term be
made up I don't know if it's
appeared anywhere else but
the property is that if you take
a bunch of positive or negative
directions you take a partial derivative
or direction of the spectra do those
directions any number of times you want
and the resulting Parmelee still lucky.
So so this property is not implied by
locking cavity this is really stronger.
No case not of the major a number I mean
if case bigger than the rank of
the major you get zero but no.
Need for everything so
there isn't we need it for for
all is because we are going to apply
induction to this and then you need it for
you so OK so
you have you have the stronger
completely lock on Kav property.
And then once you have this
result you can you can prove.
Something which you can call a capacity
and quality so there is this line of work.
Was the first person to prove such an
inequality but there is this line of work.
And.
Prove the jury's ation
of words as a result and
then there are two follow up results.
Working and real sleep on meals.
So in it's in the same line of work but
what it says is that if you have
completely laconic a fall meal.
The quantity of your after.
It's exactly the same quantity
as before as in the last light
you can find out more about in terms of
the values that this particular can take.
So this so the left hand side is really
some quantity in terms of the coefficients
of the power and you're relating it to
the values that the Pongo can take.
So I don't want to go through go into the
proof of this because it's going to take
a long time but
let me just Smith mention a few things so.
So OK so we're on the right
hand side the are dividing our
policy all by someone in terms of voice
and sees it's not a exactly a monarchy or
because we're raising two fractional
powers OK fractional power P.
and one minus P..
But nevertheless this is
a quantity that has appeared in
in most of these works it's known as
a capacity that's why this thing is called
the capacity of quality OK so
this quantity is very later to
give you give you the connection
in a couple of minutes.
This thing is what the term means you
are the heir of your approximation Now
if you want to prove such an inequality
obviously of doing this is by induction.
OK Because here you have something which
decomposes into different coordinate and
then if you apply a bunch of these but
not for
all I you still get
the completely lock on to fall.
So the entire proof is just induction and
then the whole thing reduces to the case
of any cause one OK even the induction
step reduces to the case of any calls one
now in the case of any cause one you have
let's say multilinear Palami
all in just two variables Y.
and Z.
it has just for corporations possibly the
constant coefficient the coefficient of Y.
the quality of the and
the coefficient of Y.
easy so complete so
Law concavity basically just defines a.
And inequality in terms of those.
So if your power millions are say a plus.
C.Z. Plus the vice.
The law can't have any basically tells
you that he must be less than twice B.C.
and this is enough to prove that for
him because one.
Aimee's so so
those are some ideas used in the proof why
there's such a thing implied what we want.
What you want was to prove that the comics
program gives you a good approximation for
the common basis up to a tree right so
let's let's take this inequality apply it
to this farm for me to eat and why don't
you take the drinking problem you live and
wine you for
me to you take the dual nature.
Of that you multiply them you get the same
as a as we defined in the previous light.
OK So this is the this is the problem
you love and one direct some M.
to do all.
So if you if you apply this result to this
family all under left hand side you get
a lot of the number of can be a C.S. What
are the terms of you get on the right hand
side you get well log of this
this error term which is just P.
i log P.R.I. minus.
And then this poem you all is.
Is the compose into a product right so
when you're taking the in
from all over of Y.
and Z.
you can do this separately for each.
For each of these terms that
appear in the product so
you get kept passing the end one.
For the powers one by one through P.
of Y.
to P.
you get the capacity of and to do all
four for four The power is one minus OK.
Now these things are related
to the entropy and
in particular I'll show
you in a second VI D.
This thing is bigger than the sum of P.
i log one of our P.R.I. and this thing
is also bigger than the sum of P I so
once you have this inequality one
of these basically cancels the P.I.
log P.-I terror and you get the sum
of your log one of our P.R.I. minus.
Which basically is the same as some
of the entropy minus some more break
now why why is this trip true
so it's an observation that you
see in a lot of places but.
This capacity is basically it has
an interpreted interpretation in terms of
the entrepreneur OK so once you fix
the vector once you fix your powers P.
look at all of the distribution
that can under set of one of
the meals defined by this pond we'll.
Look at all this review
shows that have marginal spi
the entropy of the maximum the maximum
one trapeze of such a distribution
would be equal to this capacity thing.
So it's exactly the entropy
of that defined.
And previous slide the one
VERY the distribution was for
proportional to the product
of land ice yet.
Yes there is you can get this
from the duality exactly
the proof of this is just using
the duality of the maxim to be so so
you get the entropy of the distribution
was marginal as R.P. right because
you proved are the four major ways that
the entropy is bigger than the sum of P.
I want to repeat I you get that you get
the first term you're right for the other
side you still get a distribution
on the do all of them a treat.
But form a choice if you have both
inequalities straight it's also
bigger than the sum of the again one minus
log one of of one minus the I and P.
I like want to repeat.
And it's also important that you
have both two two these terms
so that's how you get the result for
the intersection of two way traits.
So let me conclude.
So so what I showed you was that you
have a deterministic to say the of rank
approximation for counting basis of a
major oil and also a common basis of to me
towards the approximation algorithm is
the same the analysis is different.
One needs feature of this is that you
can boost it to using very well known
techniques to one person approximation
if you are able if you're willing to pay
the two to the of ranking time OK So
if your rank is that say look or if make
this gives you upon your time algorithm
to to do one person approximation.
The obvious open question is whether you
can get a one person approximation using
perhaps Markov chain methods.
So there is a candidate for
getting this for a single night Roy There
is this thing called the basis exchange
Markov chain it's known to work for
certain classes of many droids
balance spanning trees are an example.
But not only trees around.
The same basis exchange Markov chain.
Told me that he knows that it also
makes is in time to do the of rank for
any major oil.
So.
You get OK has to take but probably works.
OK And then the other in
that in the other direction
we have a comics program why not
apply it to more general families.
We know it works for me Troy and
intersections of choice.
Maybe it also gives you a good
approximation for other coming into your
family's concrete conjecture is
not by party perfect matchings.
So take your.
Indicators of a perfect match in
a graph does this give it to the OR
of an approximation to the number of
perfect matchings OK this is probably.
A very hard question because it's
related to this kind of the wires and
plumb there if you know what that is.
Which hasn't been resolved and thanks.
I mean deterministic algorithms can't
because there is this lower bound of.
Yeah.
Yeah those lower bounds don't work for
explicitly trade such as I don't
know linear made trades or
or things like that but.
I don't know I think I think the hope
of proving that the market chain
mixes fast I still
believe that is true but.
Yeah yeah so far I think
the structure is also show you here
as have some connections to to this
work offer there on the high would show
that this market chain mixes fast for
bounce me droids so
they use this thing called the negative
correlation and it doesn't hold for
all my toit's but using La Concha I
mean you can show that some approximate
negative correlation is true back ups
like here if you want to read it but.
You know.
Right here.
Yes.
Yes.
Yes yes yes yes.
Yes but you know Dr Bonnie Hughes
there is not brakeman's theorem is it.
So you're talking about the brakeman mink.
Idea.
OK.
I see OK.
Then.
I don't exactly know what
there is also earth but.
You have to use you have to also
assume some connectivity or
something right yeah yeah yeah
if you have a take a connected graph I
think you can prove a Laura bond of.
And to do a little of Katie sorry.
Kate Kate to the my God And
on the number of spending trees.
I don't know if it's in the same line but
yeah OK.
So OK so if you if you're
directly apply this approach.
You can sort of get a proximate sampler
was approximation qualities like two to D.
or of rank square or something like that.
I mean if you want to get like a sampler
which is good really one person
approximating.
Then you have to also be able to
count which we currently don't.