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.