first day so the next talk is going to be by your time diction is going to talk about reverse hyperconductivity and sampling in high dimensional expanders so take it away with them thank you thank you for coming so yeah first of all all I'm going to say in the stock is joint work with Max Hopkins from UCSD so hi Max um yeah so as though said I'm going to tell you about reverse hyper constructivity and sampling in high dimensional expanders so this is sort of the Boolean function analysis part an
d this is like the beyond the hypercube part uh before I start though I like prepared this like cheat sheet on high dimensional expanders do everybody see this part of the word yeah so just so that we'll like converge to the right definitions and establish some notation so maybe I'll go through this for a minute uh yeah so we're going to talk about simplication complexes basically these are just um hyper graphs with the downward containment property namely if you have uh set inside the hypergrap
h and a subset of it then the subset is also part of the hypergraph um one non-standard notation that I'm going to use um uh x k like this will be all the sex x inside X of size exactly K so I know that the convention is to put here A K plus one but it will be somehow more convenient to use this uh convention um two other uh notations one is quite standard uh the link of a face s inside X will just be taking all the T minus s for T that contains s and X so probably at least some of you have seen
these things already and I also think that you maybe have gone over this in the boot camp but still it will be nice to give an example um so if this is sort of our simplicial complex like these three triangles and all edges and vertices and we look at this like s here in the middle its link will actually be a graph right it will have like these two edges A and B and CNB because like uh the vertex a here corresponds to the edge sa and so on and so on um another thing that I want to rotate here i
s the star of s or the K star of s which will be all K faces that contain s so for example here if we look at like the one star of F this will be like all these four edges and you can see maybe why I like the color the start um so one last thing um I should Define now like high dimensional expanders basically High dimensional expanders are these simplicial complexes where uh the underlying graph in every link should be an expanded graph so this is like a non-example because this is not even conn
ected um however um I'm only writing this down here so that those of you who like know that this definition already will know what I'm talking about essentially uh for the pack today I won't actually need this link definition all we really need to remember is that high dimensional expanders sort of approximate behaviors in the complete complex in the complex that has like all possible sets Okay so this is like really the the essence of high dimensional expanders and we'll be more precise so yeah
so I want to tell you about reverse hyper constructivity and essentially this is a property of graphs that talk about a sort of small set mixing inside graphs so first let's define the graphs that we will be looking at so X will be some simplicial complex and for the first graph that we talk about we need two integers k and l and this first graph is sort of the what's called down up walk graph but let me Define this this is a graph whose vertices are spaces of sides K inside X and whose edges a
re just pairs that intersect with at least L elements okay so these are all the t1s and t2s intersection size at least L I like to think of this as some like specified version of the Johnson graph because when X is the complete complex this is roughly the Johnson graph maybe with equality here um and this graph also comes with a natural distribution that one can think of as like generalizing the noise distribution in the Boolean hypercube so this distribution of choosing a pair T1 and T2 goes as
follows well first we sample one endpoint in XK and I should say this right away um think of X as being like very very regular so when I say we're sampling something out of X carry think of the uniform distribution it doesn't have to be like this but it will make things simpler um so first we sample one endpoint then we sample a intersection inside it so this will be an L subset of a t that's uniformly sampled and finally we sample T2 also in XK but conditioned on containing this intersection s
so why do I think of this as like a noise on T1 because again this is T1 and you know when we choose T2 we're saying you know we're keeping some of the vertices so there is some correlation however for the rest of the vertices which will give us back T2 we're sort of like re-randomizing uh over the remainder of the set um so this is like the first graph that I want to talk about and the second graph is even more resembling the noise distribution because in the second graph we won't just choose
a simple fix size XL we will actually like flip coins for every vertex to decide whether or not we are re-randomizing it so for the second graph we have some parameter row between zero and one and that's denote by J okay row and don't worry we will always be able to make the distinction to be a the graph whose vertices are also x k but this time technically the edge set will be like all possible pairs however the distribution will be very non-uniform in the way that I just described so what we d
o we sampled one endpoint out of x k next we will flip coins for like robust coins for every vertex such that with probability row we keep the vertex inside the intersection and with probability one minus rho we remove it and then we randomize on T2 so one way to formalize this is to say that we are sampling L from some binomial distribution with success probability row and then we sample s inside T uniformly at random let's have this size L um finally we output T2 the same way we've done for th
e previous graphs okay so these are both graphs I think that maybe Maxwell also covered this in the boot camp that this is really sort of a generalization of the noisy graph and before I State formally what I want to tell you today I want to maybe just do this in a picture so these are you know one of these graphs and essentially today I want to tell you about a mixing theorem that says that if you have here two small sets A and B still edges in this graph will be quite well distributed namely w
e will always find like a noticeable fraction of edges uh going from A to B so this is quite a nice property especially because these graphs are not very good say expanded graphs they're not very good spectral expanders so like the right regime of parameters to think about uh is maybe like rho equals 0.9 so in this case you can find like very small sets here where like 90 of the addresses actually stay inside the set so like very bad expanders and yet you still have this like small set mixing Le
mma that says that even if this is true the remainder of the edges are quite well spread among the graphs you can't like achieve like non-trivial Independence that say due to this like correlation between uh substance so let me write the theorem down formally or at least somewhat formally uh the theorem in as follows um let's take row to be some parameter and let's take L to be rho K whenever I multiply an integer with a fraction it will always be an integer okay so I'm not going to do integral
value but let's just assume it um and let X be a sufficiently good high dimensional expander where like the Lambda parameter goes like exponentially down with k um so we have two parts one for each graph for the first graph we have that for every two subsets of the vertices A and B um if the relative size which I'll denote just the probabilities of A and B are at least this like exponentially small sets then the probability of sampling an edge in this jkl graph such that one endpoint is an A and
the other endpoint is in b will be at least some small polynomial in the probabilities of A and B so of course if this was just a complete graph or something I could just maybe written this here I need to put some o of one um this like Omega constant and this o constant both depend on row but for a fixed row I can just write this down uh yeah for the second graph like this is sort of a smoothed version uh of of this graph we get even something smaller we actually get the same theorem without uh
or for any in b even without this requirement and sizes so sort of in in this graph you have like some small probability of just sampling T1 and T2 independently like if you fail to keep any of the intersections so somehow this takes care of like sets that are smaller than this and really um even though I'm stating this for these two graphs this is really the graph that we're going to focus on and this is like where the heart of the proof is um yeah so this is called small foot mixing and befor
e I tell you about sort of how this goes and why this is connected to sampling I would like to maybe uh mention a couple of words on the history of such inequalities and why I I like to call it a reverse hypercontractive inequality so let's uh think back on the Boolean hypercube uh I want to maybe keep this uh what should I erase I'm going to erase this cheat sheet okay so back maybe to the Boolean hypercube um so let's denote by 0 the row correlated noise operator namely tiro Opera operates on
a function X gives us another function that's an input X where X is In N bit string it outputs the average of f overwise that our row correlated with x and when I say row correlated again like we uh um the randomness here is by taking a x for every coordinate flipping a coin with probability row we keep the value of x with probability one minus rho we randomize so this is the expectation here um the well-known hyper-contractive theorem by I think bonami and also Beckner and goth and Nelson um it
is the following so suppose we have p and Q where Q is greater than p and suppose we take a correlation that is small enough with respect to these p's and q's then it turns out that for every function if the Q form of the noise operator of f is less or equal to the peace Norm okay and here just so we recall the peace Norm of a function f is of course the expectation of f in absolute value to the p and then we take a piece root and what's important about these Norms is that they're monotone so t
hat if I take Q to be larger and larger the norm should increase and increase or at least it should be greater or equal to the piece Norm but here what this ethereum is saying is that this noise operator shrinks F so much that even if I measure it in the Q Norm which should make it bigger it's still less or equal to F in like the original Peak Norm um so this is like the standard hyper-contractive theorem and it also has apparently a reverse hypercontractive ethereum where I can actually like re
verse this inequality this sounds like nonsense uh but let me let me state it for you um and this I think is due to Morel in the 80s and now something weird is going to happen here now we're going to take p and Q less than one and we're going to say that if rho still small enough then it turns out that the I'll call it Q Norm of T row f is actually bigger than the peace Norm of f so you know let's let's process this for a minute first of all when P or Q is are less than one this is not a norm an
ymore okay so this is not convex you don't have like a triangle inequality still I mean you can Define you you can Define this let's for convenience ask F to be a non-negative function uh this is of course necessary uh here um okay so you can still Define this and it still makes sense to maybe compare these things and it turns out that you know you can you can actually get an analogous result if you sort of reverse the arrows here and you reverse the arrows here uh however I mean this seems quit
e abstract and it actually has an equivalent two function version that is like much easier to understand and to actually find out like how this theorem came from so actually the two function version here will say that for every f and g if we look at the expectation of f x and g y where X is uniform um over the Boolean hypercube and Y is noised up and this expectation is greater or equal to the pth norm of f times the Helder conjugate a norm Q Prime of G so here Q Prime like formally it's Q over
Q minus one and I really encourage you to think about this theorem in the parameter regime where like uh p and Q Prime are some like uh positive constant of course less than one Okay so why do I like this two function version the reason is it actually makes sense when you put your indicators of functions so when I will put your indicators of functions what we actually get is is what so suppose f is the indicator of some subset A and G is the indicator of subset B the left hand side of this inequ
ality well it just simplifies to the probability of sampling X and Y as an easy copy such that one endpoint is an A and the other endpoint is in b and whereas this right hand side uh this will be well it's not too hard to follow this expression if this is an indicator function this P power or absolute value doesn't matter so this really is like the probability of a to b 1 over P the probability of B to the 1 over Q Prime so if you believe me that this is equivalent if you instantiate this to ind
icator functions then you you will get that this thing is actually also like the probability of a times the probability of B to be all of one so I should say that like this observation was first done by Mossel O'Donnell is regabs and they actually prove this very useful like small set mixing inequality in the Boolean hypercube um and and they used it for like a application then some communication problem with many parties uh later this also found applications in like uh in agreement testing and
uh um like in robust social Choice theorems and it's really quite a nice theorem for the Boolean hypercube uh from that's this version Oh that's actually a good question uh the answer is sort of yes for if you have this for uh if you have this for all sets and you're willing to satisfy to be satisfied with slightly worse fees in Q primes here and maybe also maybe like a fixed constant here you you can do it actually um we also do it in the paper just because we didn't find anywhere that this was
done but uh that may be a better answer to your question is that well yes but really when people use this reverse hyperconstructivity all they really care about is this I mean like I think that in every single application or at least the ones that I read this is what's interesting uh but formerly mathematically you can get back good uh yeah so I'll continue here um okay so this is maybe the history or why we call it reverse hyperconductivity and now that we know this I want to tell you somethin
g about the proof here and the first thing I want to do is to convince you that this question of mixing is actually a question of sampling okay um and the reason is as follows um yeah so look at this look at this distribution over here which is the Distribution on edges actually it can be equivalently viewed as a distribution where we first sample this intersection so we treat it like a first class Citizen and then we will just sample T1 and T2 sort of independent from one another so like the eq
uivalent distribution here is really first sampling s which is the intersection and then sampling uh P1 and T2 that contain s independency from one another so this probability that T1 is in a and T2 is in b we can of course write it as the expectation over this intersection in the first step of the probability given that T1 and T2 contain s but because these things are independent this is just really this expectation over s of the probability that over like the relative size of a and the relativ
e sizes of B inside the star of s so like the picture should be or maybe I will just like decrypt this notation PA given s is just like a intersect the K star of s divided by the K star of s and you know notorially one side XL on the other side and we sort of look at like these containment neighborhood or the spontainment graph and you know we have like two sets here A and B and this like expectation is really asking the question how many s's see in their like containment neighborhood or like in
their star they see a and b with at least some like noticeable or non and negligible probability uh because this is all that's going on here so this sort of motivates us to ask how well do high dimensional uh expanding like how well do these containment graphs in high dimensional expanders actually uh sample small sets uh of Dimension higher so that with this intuition in mind uh I'd like to uh I'd like to define a very useful primitive in computer science which is called sampler graphs there a
re some definitions out there not all of them are exactly equivalent but they are very similar essentially a sampler graph is a graph where one side really samples sets on the other side quite well so maybe we'll draw another picture suppose we have a bipartite graph with left or left and right sides and suppose we have some set a on the left who has some relative size which will denote ypa um so we can say maybe that the vertex samples a well on the right if when viewing its neighborhood on the
left the relative size of a inside this neighborhood is roughly the relative size of like the global a inside all uh on the left side so we really want that like the inside the neighborhood would be approximately the probability of a so this vertex is good but I don't know maybe like this vertex U Prime is bad because it almost doesn't see anything inside a or maybe the C prime prime is also bad because I don't know maybe it's like completely contained or almost completely contained in a and a
sampler graph is really a graph where like most of the vertices on the right will be like with vertex U and not these so uh I think this is a nice uh this is a nice definition it has many uses in like uh error correcting codes and and saving Randomness uh so the definition goes as follows so for a fixed graph G and some subset a in the left let's denote by T of a to be like the bad vertices in the right so these will be all the use on the right side so that inside their neighborhood either we se
e a with more than three halves its original a relative size or we see it less than a half so these are like the vertices that Temple a atypically and for some parameters uh Alpha and beta we say that g is a alphabeta sampler if for every set a of probability at least Alpha this will be the set size bound we have that at most beta a better fraction of the vertices sample a battery okay so for every a most of the vertices will sample a quite well um so I I want to give some examples for this defi
nition so it will maybe be less mysterious foreign be the complete complex example so uh let's take our graph to be left side is some universe and sized right side I'll denote it by this notation namely all possible subsets a random size exactly K and the edges will be containment Edge so like V is adjacent to us if V contains s um so by like standard chain of bounds one can show that for every set a the probability of the vertices on the right sample a badly is at most some exponent uh to the m
inus K times the probability of a squared and why is this true well roughly let's think of K as some constant and N is much larger than k here like sampling uh a node in the right this is roughly just like sampling K vertices on the left independently I mean of course there is some probability when we sample independently that there will be a collision but like ignoring that we're in K is like very small this is roughly the same thing so this is just a churn of bound um and in fact one can show
that for a graph with right side degree K this is essentially optimal this is a theorem by I think kanathy Evan and or the Gold Reef um so really this is like the most that we can expect and we indeed get it of course uh if you like if you like to save in Randomness and things like that this is like very inefficient there are a whole bunch of vertices uh here which like people have tried to take down [Music] the second example that will be more modest and parameters is just that if G is a Lambda
spectral expander okay so it's a bipartite graph but it can be a one-sided Lambda expander um you will still get for every Alpha greater or equal to zero that g is sort of an alpha uh roughly Lambda squared over Alpha just to compare because I don't think I wrote it here on the board oh here G is like an alpha e to the minus Alpha squared over three a k example so here you can get something that's like polynomial in the degree whereas here you get something exponential still sometimes you know
what you have to work with is only a spectral expander and this bound could still be useful and in fact like in previous works of high dimensional expansion like you know when carphone's work on agreement expanders or the neuro livni Kaufman hausa and tashman's work on constructing locally list decodable codes like this was mainly what was used spectral map does achieve like good enough sampling for some applications um the main technical tool that Max and I needed to show this reverse hyper con
structivity is actually stronger sampling than what you can get from a spectral Bound in these containment graphs of high dimensional expanders yeah here well G is a graph so it must be along one-sided the spectral expander because you always have like this minus one this is not the spectral expansion of the complexes no this is just like for playing graphs this is not this is just an example one um I'll comment on that in a minute okay um [Music] so dilemma that the following so let X be a 297k
remember here you can either take a two-sided High dimensional expander you can take some multi-part type one-sided high-directed expanders but they need to be like a cut of like a polynomial polynomial in the dimension this is like a technical property but this can could be extended slightly then the following graph is a very good sampler so what will be the graph so the scrap would have a uh so let's Maybe parameters i j and k and that's maybe fix the things are PSI the left side of this grap
h will be the r star okay the right side of this graph will be the r star of 11j engine will be of course edge of the containment and the sampling property that we uh achieved is that if you have a set size bound which is exponential inters K minus I divided by J minus I you will get a confidence that's a small constant this is roughly the technical tool that I want to tell you about um but let's talk about this a little first of all um like the like the first use case that you maybe want to con
sider is like what happens when I equals 0 and R is just the empty set in this case this is just x k this is just x j and we get this like a containment graph um the rest actually follows from like the general case that I wrote here sort of actually follows just from the fact that like the star is sort of isomorphic to the link and the link is also a good high dimensional expander so like this is not only like the first case you think about this is like almost a general uh case so I like to thin
k about it like this but it will be useful later to also consider like these local components these Stars um another couple of things I want to say about Islam I I don't think I'll have time to prove it uh to you um first of all I should say that um there is a work by impalazo cabinets and digital Zone from 2008 that showed roughly the same Lemma for the complete complex foreign you know whenever you see such a statement on the complete complex it sort of challenges you to say ah you know you do
n't really need a complete complex you can do this in high dimensional expanders so like it turns out that you can and uh the proof it mainly goes through like a previous sort of pseudo-random result in high dimensional expanders by already know and myself which is called like the high dimensional expander mixing Lemma and I will just say that sort of you can also like generalize this and we like try to slightly generalize this to also other uh interesting hypergraphs so you can get somewhat of
a similar theorem also if you look at like Works in an expander or like other what's called like splitable trees for those who know this for those who don't this is not such an important comment um yeah finally uh the last thing I want to say about this Lemma is that um in fact this maybe parameter regime is not what people usually like to look at usually people like that like the set size bound is constant and the confidence is like really really uh high or really really low if we we look at be
ta like as the bad like the probability of the bad set and it turns out that sort of if you flip sides here namely you take like the small side to be the side that sampled and the large side to be the side that that samples like clay sets versus gay sets you can also like reverse the parameters here so you can get like a small constant of your set size bound and a large constant sorry not a large constant and an inverse exponent here in the confidence and like this is this also found application
s in like in paliato cabinet and victorians work so I don't know maybe this generalization to like sparse or synchristial complexes um could also still be interesting yeah any questions here Michael J is that kill where two you're not getting yeah so for J and K to be constant this is uh this is quite uh weak right because this is only a constant here um you need to think about this as when J is like really small like I don't know like a square root of K or even a constant well in this parameter
regime then the what you're about faster from the spectral Gap is something that we have like one over Alpha to one over Alpha k or something whereas here this is like an exponent in an exponent in a minus k minus square root K so really the power here is when J is like incomparable to K but then you don't have a like you don't have like a polynomials exponential expected to get better like yeah you also assume that very rich um so what do you mean by we expected expansion right it's like inver
se exponential in UK okay yeah okay I'll say something okay I think of like I have zero so this is just x k versus XJ When J is one then this roughly achieved the parameters you get through the complete complex so you can't expect and I think or even J equals two or I don't know square root k or something like that well uh I don't know how much better this can get I mean we haven't tried or we haven't tried very hard you need to try also in the complete complex because better things are not know
n even there so uh I mean it could be true I'm not sure definitely for that case you don't have like some optimality uh lower bound or something it could potentially be better so now that we have like all the players in the proof I like to give you a rough sketch of how one showed this reverse hyper-contractive inequality so let me remind what the setup is to this is theorem so recall that we have some good enough High dimensional expander uh and when I say good enough I mean high dimension or e
xpander such at the previous Lemma holes that's like really all we need uh we have two sets A and B which are vertices in this like jkl subset of vertices in the jkm graph and all we know about them is that they are no smaller than some what exponent in k um and for Simplicity let's fix like row to be one over four L to be K over four uh I should say this is like a minor technicality when like row gets closer to one you need to introduce some more complexity to this proof but still most of the i
deas will suffice here and this is like still linear in K and what we want is to show that if I sample T1 and T2 in this [Music] it's like sparsified Johnson graph j k l k over four this would be greater or equal to the probability of a times the probability of B the old one so this is what we want to show um and now I want to draw this like containment graph and it will have soon multiple layers so I will draw it like horizontally so here's XK here we have two sets that could be like inverse ex
ponentially small but I'll draw them slightly larger just because uh just for the picture and you know here's x k over 4. and a fan pointed out I mean if these sets had like some I don't know like a small constant size we could have just you know said that like for at least like maybe half the s's over here they would sample A and B well enough like up to like losing a factor of half but of course this is not true right because we don't know that they're constant instead we know that they uh the
y have said that the most like inverse exponential in k however note that what we need to prove is not that this thing this probability is lower bounded by a constant times these two probabilities we need to prove something much weaker when a and b gets smaller we need to prove that this is only greater or equal to this product of probabilities to I don't know to the seventh power so like the smaller A and B gets like the more room for error that we have we don't need such a strong sampling theo
rem so what we're going to do is sort of try to like accumulate more errors along the way and and and yet still use the sampling theorem where it will actually apply for a and b so with this in hand the trick will actually be that when we sample s in x k over 4 we won't sample it in one shot we will sample it in batches so okay so we think of s is like a k over four sets but we will sample it like J vertices at a time so R1 R2 R3 and so on up to I don't know RB which will be the number of times
we need to do this so Jay I think of it as the best size and for the moment let's think of Js just being like 100 vertices or something later on we should optimize this okay but let's think about it like that and B will be the number of veterans we need which is of course k over 4G and the point is that when this J is indeed a constant then even if a and b were actually this small we will still be able to use this sampling property okay because when J is a constant and you should think of I also
as a constant here then this will be like e to the minus k okay so the trick is again think of explains like way down below here and we will sample things in XJ and then we will gradually go up until we get to x k over 4. so so what can we say actually about uh what can we say about XJ well for the first R for the first r that we sample for the first J vertices there we actually know that our sampling is our sampling graph will be small will be strong enough because these are bounded by this qu
antity and J is a constant so like for the first K vertices we can actually sample A and B quite well so towards this maybe we Define like this good set G1 which will be all the vertices such that A or B in their star is off by at most a half and because we know that this graph is the e to the Omega K 0.25 sampler and because we know that A and B are large enough we know that if our is not in G1 this means that R is either in the bad set of a or the bad set of B which means that G1 as relative s
ize at least to have so like for the first R vertices half of them are good uh let's do one what about the next server diffuse so now I've sampled like one subset the vertices I still haven't gone to uh gone all the way but now I'm only worried about sampling the next our vertices so I like to think about it like this now we're looking at 2J we've already sampled our one hopefully it wasn't this like good set and now sampling another R2 is actually sampling you know is sampling R1 Union R2 or th
is joint Union from the J star of R so this is the uh uh sorry the 2D star of r okay so we have a two-day vertices J of which are inside R and of course provided that R landed inside this good set we know that if we look at the star versus star graph so if we look all the way up onto the hey Star Bar we know that over here A and B well if I was good they may have been smaller but they're only smaller by a factor of half so still a factor of half we can still use this bound so again there is some
deterioration in parameters that you need to carefully like Chase but this star graph will also be e to the minus Omega K 0.25 Center and so if you define the fit G2 which are on the things in with 2J vertices so that in the star we are off by a factor but most a quarter so it's like half squared okay then I claim that the probability of this G2 is itself greater or equal to a quarter and why is this simple we're sampling this set G2 so you know first we sampled R1 if it's in the bad set okay w
e lose but it's in the good set with probability half so you know so like with probability half R1 is in G1 what about R2 well here are you sampling given that R1 was in G1 we know that half of the R1 r2s inside here sample A and B really well with respect to their size inside the R1 star which is at least half their original probability so probability another half um R1 and R2 samples A and B so this is roughly it so now you know we will Define also G3 for 3j4 and so on and up until you maybe a
rrive at sort of GB where B is the batch size and these will be all sets of size K over four such that in their star we are off binomial of a factor of 2 to the minus B foreign this is like a very typical inductive proof in high dimensional expanders you sort of start with something Global and then you like condition on a link of a star or something and then you may be condition on something else and you go up up all the way until you get like this recursive or induction uh or inductive argument
and I claim that this suffices because uh because of course the probability that a good event happens which is this expectation well this is just greater or equal to the probability of GB times the smallest value this thing can get given that this is in GB which is equal to the minus 2B PA P capital B I am now noticing that I used Little B and capital B so I'm saying b a lot I I apologize foreign so of course here the correct analog of what we are proving here like half a quarter and so on will
also be that this GB set will have a size that's also like inverse exponential in b and if you can actually prove this which we do this is at most sorry at least through to the sum exponential in b e oh you know this will maybe a bit technical but all we really need to understand here is that if you use if you analyze using this technique the error that you incur is really exponential in the number of batches that we take so like the name of the game here is to like carefully balance these para
meters so on the one hand you want to take as many vertices per batch as you can so you will incur less error on the other hand if you take too many uh too many vertices then you won't be able to use like the sampling Lemma um but it turns out uh that if you use a large enough constant say 100 foreign this argument will actually work so you can lower bound this bye paapv to some small power yeah uh maybe I'll just give some concluding remarks and I'll finish here um so this was sort of a combina
torial proof to like a reverse hyper hyper constructive inequality that I felt that maybe had like a different flavor than like the more analytic proofs that you see for like uh you know for the Boolean hypercube or other places where you can sort of do something in like a two-point space and tensorize or maybe use like uh log several of inequalities um so I was wondering whether there was like a more analytic way to also view this proof or also view these proofs in high dimensional expanders so
this is like one question that I maybe want to post to the audience if somebody wants to think about it uh another thing that I sort of view is like someone that caveat in this work um which is also a caveat like in a lot of Works in high dimension on expanders that this is really requiring a lot I mean you know High dimensional expanders are very uh they're very rare objects you can't just like sample one like from a natural random distribution and here not only you need a high dimensional exp
ander you need like an extremely good high dimension of expander like the expansion parameter is like uh inverse exponential in k and you know like in nature sometimes you can prove High dimensional expansion but maybe it's not like uniform in all levels and maybe it's not exponential in K and I mean these like mixing inequality seem quite useful so I mean what can we say for other structures or even for high dimensional expenditures that are like weaker than this like very strong guarantee this
is a good place to end thank you for listening any questions for your thumb uh yeah that's a good question I don't think it extends technology complexive uh I mean maybe you can try and tailor like the proof details to Metroid complexes as well but but uh no I I mean I wouldn't be surprised if you could extend this this like they're very structured right they're like almost apartheid knows the complete complexity [Music] so if you want yeah foreign [Music] I admit I'm not sure what what's known
in the like prior dance case I imagine that these techniques will be weaker in wherever like uh I mean this is not this is also probably not Optimum in the parameters and like really the advantage here is only that you can work over like sparser sets I don't know if well I think I'm very interesting to me because your set is loud because in many external problems it looks like diversity is no a way of walking because it somehow holds for all sets to understand yeah and somehow the fact that you
manage to put some photos thank you yeah maybe I'll just mentioned just for the last minute that this this requirement is actually also necessary so you can like so not a very complicated example where this like and we have times 2 to the minus K and and they have no uh okay we'll respect to that is the inspector expansion parameter and then get something for [Music] in this context [Music] yeah uh I guess that for uh nice gamma is due to the mind of something and make the noise okay like what
is hiding here like the theorem that I stated in a simplified way sort of tells you that you are a you're a sampler with like uh with error probability that's like e to the I don't know okay something plus an error which is of the form like two to the K or three to the care something times Lambda and sort of there so like if you are a small exponential then this is roughly like this then once you're a large exponential you get something that could be much larger than I mean even for exponentiall
y small number this could be much harder than one so you did nothing um um so so again this really only comes up like in the proof of development you know it's from some other source you can you can do this any other questions you can't push the confidence level yeah one two five oh uh you I just simplified you there's a parameterized version where this is that fine this is maybe like e to the minus Alpha squared times what I wrote and I just didn't want to [Music] okay so let's thank you again
[Applause] will return after lunch at 2PM foreign
Comments