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.