Stefan Krastanov: And if you don't mind introducing yourself, and
Stefan Krastanov: so hello, everyone, I hope people and someone can hear me.
Stefan Krastanov: If you cannot let me know they
Stefan Krastanov: i'm one of the Laura and I'm a master student here in us, and David i'm talking about it's kind of so
Stefan Krastanov: just so there's a warning. There's gonna be some theoretical content happening here. So in case you're not familiar with drop theory or like, you have a week background. If we do interrupt and ask as many questions as you would like, because Ashley Sha's presentation kind of relies on what we were talking about.
Stefan Krastanov: So I think
Stefan Krastanov: right. So
Stefan Krastanov: what really are we talking about here? So expanded graphs are basically definitely a kind of graph. But we are specifically looking for 2 properties. We want sparsity in the graph, and you are from connectivity.
Stefan Krastanov: and one of the mayor. You know thing that you'll see throughout this presentation is the fact that you're trying to quantify what it really means to be strongly connected.
Stefan Krastanov: Now this 3 interpretations of how you can, you know, talk about expansion in the graph like, or what does it mean for you to be expanding? And that put in terms of vertex or vertices, edges and spectral expansion?
Stefan Krastanov: We've been talking about expansion, and or, you know, spectral expansion. What is it? Expansion is in Section 5 of the reading that I have used, but that's not a part of what we are covering. So in case someone is interested, please be free. Check out the reading Chapter 5.
Stefan Krastanov: Now, the interesting part with expanding graphs is that though you know the community right now. The Academia is kind of deliberating that this something very natural to graph itself. So there's different ways. You can approach this whole concept, and this 3 perspectives that people have put forward so far
Stefan Krastanov: the combinatorial perspective which kind of relates to, you know algebra, and counting the probabilistic perspective which relates to the Markov chain perspective and random random walk perspective, and you also have a third spectral perspective from, you know, linear algebra.
Stefan Krastanov: So if you look at the combination of what an expand your graph is. It's essentially a highly connected graph, such that if you want to disconnect the connected components, you'll have to actually remove a lot of pages. So it's very primitive definition. We very soon see how to make it more and more. You know, detail
Stefan Krastanov: in terms of the probabilistic definition.
Stefan Krastanov: What we're really saying is, you have this graph over which you can do a random walk. Right? So a random walk attention that you start with a vertex, and you just keep going to a random vertex with you know it's like a unique. What do you call? I? Id kind of situation
Stefan Krastanov: and autograph they can expand. To grab.
Stefan Krastanov: This kind of random work will converge to its limited distribution as quickly as as you can get to it. That's the probabilistic definition. It's very useful in Markov chains, because there is like an entire chapter on how you know you can implement that using its photograph.
Stefan Krastanov: and the algebra definition, which I think is what we are most concerned about today
Stefan Krastanov: really connects. You know, the the eigenvalue or the second eigenvalue more specifically second largest second value, or or through the Laplacian. And the definition that is, you know, provided is basically the fact that
Stefan Krastanov: if you give to the first positive eigenvalue of the largest operator, and it's bounded away from 0. Then this crowd is specifically an expanded route. We will talk about the algebra definition later on in this presentation
Stefan Krastanov: is the base. Okay, with everyone. I'm going to alright. So as for motivation, you're going to talk about 3 motivating problems there. That kind of led to the foundation of this whole theory of like expanders.
Stefan Krastanov: the first one being completely unrelated to anything you've seen, so far. So as soon as you have a matrix a which is n plus in. I just mute this as a find over a field there.
Stefan Krastanov: So the the question there is what is the least number of gates in a circuit that can compute the your transformation from X to E. Times, x.
Stefan Krastanov: and
Stefan Krastanov: each gate that you're trying to build here can only specify about 2 kilometers, a and B, with only 2 operations additional monitoring over the field.
Stefan Krastanov: So
Stefan Krastanov: this problem has, historically, you know, been very significant, because under certain circumstances, this reduces to the discrete fast Fourier transform, which is a very important principle for this, and, like you know a few signal processing, engineering, and so on.
Stefan Krastanov: So
Stefan Krastanov: from that we have this perspective that we know by now that it exist a circuit that relies with the transformation from X to a X
Stefan Krastanov: with only open login needs. So we do have, you know, a kind of an upper bound.
Stefan Krastanov: but the problem is, we haven't been able to demonstrate it property. So we only have an estimate that the upper bound lies somewhere between open login and order of N, which is the most natural way of you know, just the worst possible algorithm you can design for this
Stefan Krastanov: dating every you know element. So
Stefan Krastanov: the research question here is like, Can we have a lower bound?
Stefan Krastanov: Can they actually show that, you know? Can we change this order of you know, to let's say we will make up, maybe give a lower bound.
Stefan Krastanov: or can we actually rule out the existence of order in, you know? Yes.
Stefan Krastanov: and there has been, you know, some deliberation about this.
Stefan Krastanov: and some resources have actually established that if you have a field there
Stefan Krastanov: for most of the enclos and matrices.
Stefan Krastanov: you have added this to inspire by login gates. I didn't get that. Did you try? Yeah. So yeah, so we do have a kind of a lower bound. But as you might see it does not really fit in anywhere between a log in an end.
Stefan Krastanov: And again, part of the problem here is this was demonstrated to it. Nobody actually made like an actual. You know, gate that has this kind of account. So
Stefan Krastanov: we have someone who has been working, you know, who had been working in this field quite for quite some time, and actually has led to a lot of development in the field itself.
Stefan Krastanov: And before I actually talk about what William was doing. I read it to a definition that we'll be finding very useful here. So we have something called a super eigen matrix. So you start with a matrix, a, and you look at every square sub matrix of this matrix.
Stefan Krastanov: If it has a full rank, each of these sub matrices, then the matrix. A itself is super regular.
Stefan Krastanov: and
Stefan Krastanov: why is it useful? It's useful in conjunction with another. You know kind of the way it would be called the super concentrator. So you start with the graph G, which has a vertex.
Stefan Krastanov: and you have 2 partitions of we, I and O. So this I know, is coming from input and output. I think a good way to see this is the child, and they have by his nose.
Stefan Krastanov: Both have end number with each. So what's going to happen is you select some number, individual K. Let's say.
Stefan Krastanov: and you start with a subset of I and the subset of
Stefan Krastanov: so such that the size of the subsets is always equal to this integer selected K.
Stefan Krastanov: Now this graph is going to be a super concentrator.
Stefan Krastanov: If you can actually drop
Stefan Krastanov: disjoint packs in G from S. To D. So you have one subset in I, so that in this case you can see the red, you know dots, and here you have the other subset the again the same number of Dots case 3. This example.
Stefan Krastanov: and you have 3 disjoint pads
Stefan Krastanov: that go from S to D.
Stefan Krastanov: And this driver is a. So why this useful is an interesting question, and
Stefan Krastanov: the reason it's useful is because we
Stefan Krastanov: clean. This is not be interesting. Actually. So. There's one, probably, that we, you know.
Stefan Krastanov: have established already. It's a mathematical used to have the freeze out of that. If you have a circuit.
Stefan Krastanov: the underlying graph of the circuit
Stefan Krastanov: for the super regular matrix. It will always be a super constant figure. So what is the ongoing route of the
Stefan Krastanov: So if you have a circuit, let's say a a gate, right, a circuit gate. You use a graph to represent that, and assuming that that has a super regular matrix representation.
Stefan Krastanov: It is also a super concentrated, the graphics that when we zoom a call and but what does it mean to represent
Stefan Krastanov: circuit as a graph.
Stefan Krastanov: Yeah. So so you have, like, you know, I don't have a
Stefan Krastanov: yeah. I should have mentioned that.
Stefan Krastanov: Yeah, that like, what's the So the range of K is bounded by the size of the graph itself. So I and all right. I know our both ends. Okay. All this has to be less than equal to 10.
Stefan Krastanov: So we the one that's because there are some. So we haven't we haven't got you to expense. So is this graph: the super connector graph
Stefan Krastanov: this. It doesn't seem like, that is the case. Yeah, that's true. It's not a super connector. It's just an example that I want to show you.
Stefan Krastanov: So just to make sure that I understand it. We have some input now, some output notes. Yep. And as long as for any fixed size
Stefan Krastanov: subset of inputs and outputs. We can find. you know, overlapping paths from one into the other and better one to one.
Stefan Krastanov: I can call that
Stefan Krastanov: super concentrator perfect, and the
Stefan Krastanov: people were expecting that this is difficult to do that. This requires really dense graphs.
Stefan Krastanov: So so is there
Stefan Krastanov: a super concentrator?
Stefan Krastanov: Yeah. So I am not sure, because I haven't. Yeah. This. You know the the chapter like the first chapter. Hasn't really talked much more for them. They just talked about the 2 weeks ago, but I think that's a good question I would like to explore.
Stefan Krastanov: and you mentioned fast for your
Stefan Krastanov: oh, oh! So the circuits for the fast, for a and for the quantum for a transformer. One is inspired by the other.
Stefan Krastanov: The you say direct you're sending the right over to the Exactly. So matrix, right? Right? Like a full rank of well, you can have the. You can have a matrix. But you can look at the right.
Stefan Krastanov: Yeah, you can take it over the speed. That's what I'm saying. You're using specific fuel for Yup, because we, the we'll start with the assumption that you know the matrix a is then crossing over a field, right?
Stefan Krastanov: Any other questions.
Stefan Krastanov: Alright, so yeah, so the cache, the claim that we are really using here is the fact that you know the underlying graph of a circuit for a super regular matrix is a super concentrator.
Stefan Krastanov: and based on this, we didn't claim that any super concentrator must have
Stefan Krastanov: a significantly large number of edges in it.
Stefan Krastanov: Now.
Stefan Krastanov: unfortunately, this is not a like he himself. He himself, this proved it, and how he did that was that he gave an order of end, You know, a single concentrator. So that's an interesting development. But this clearly does not still answer. You know the question that we really started with.
Stefan Krastanov: which was, you know, we try to give a lower back right? We just show the existence of that. But we still Haven't really found the lower ball
Stefan Krastanov: Like as to what is the least we can have.
Stefan Krastanov: and that is the problem that continues to be a problem, and we'll see one possible solution to expanded rafts. Once we go into expanded graphs or the underlying one to detail.
Stefan Krastanov: then we have a second problem.
Stefan Krastanov: and this is more resonant to what we've been doing. We've seen variations of this problem since the beginning of the semester. We're trying to communicate over a noisy channel, and we know a fraction of its speed will probably be ordered right.
Stefan Krastanov: So the question is, what is the smallest number of bits you will need to transfer, assuming to communicate with message assuming the of them will, you know, probably get lost during
Stefan Krastanov: transmission. so
Stefan Krastanov: I don't spend a lot of time on this, because we already have done this several times. But
Stefan Krastanov: here's where Shannon's contribution coming comes in. We've again talked about this several times, but the capability is what challenge basically told us is that let's create a dictionary right? Which we call a code today and let's have a mapping a projective mapping call in coding, which you know takes this Ma Max, into the code word
Stefan Krastanov: your your code, and to send this message over a channel you just have to transmit an end with code.
Stefan Krastanov: Our design coding, which is like paradox in this example in this description, and whoever receives a string
Stefan Krastanov: possibly conducted, we'll probably find the code word Z, which is the closest to the you know Graph the string, and it's some analysis. We've already seen in the fact that this is actually the same thing as by emergency, so that when you decoded you will always get with a certain view of editor bound.
Stefan Krastanov: So
Stefan Krastanov: this is what we've seen already, right.
Stefan Krastanov: and this relies very heavy in the assumption that if you have a quote, let's say, when you talked about the handing distance you talked about. You know the rates of a code.
Stefan Krastanov: If you have every 2, if the distance between every 2 words is greater than 2 Pn. Then be a guaranteed that we'll be able to recover it right? So this is something in a different tone. Is this the same claim, but in a different flavor. I guess
Stefan Krastanov: so.
Stefan Krastanov: What the the chapter proposed is that this problem of finding this goal
Stefan Krastanov: is actually
Stefan Krastanov: more generalizable to, or reducible to, another problem
Stefan Krastanov: which is more relevant from an optimization perspective.
Stefan Krastanov: So we talk about a dictionary, right? Talking about a code. So the question really is, do we know such a code exist, or how do you actually come up with such a
Stefan Krastanov: And
Stefan Krastanov: that's exactly what you know. This problem reduces to. So can you any design? Are my to really large dictionaries, Cp. A.
Stefan Krastanov: With the size, cardinality to the game, such that you know, for some absolute constants or not.
Stefan Krastanov: they are not which are working in 0. We want to have, you know.
Stefan Krastanov: this code. Obey these inequalities, which is just the same as what we've been doing again.
Stefan Krastanov: We've just been applying it. Not, you know.
Stefan Krastanov: considering it.
Stefan Krastanov: I'm: sorry.
Stefan Krastanov: Yes, the function are. I did. I skip for? I think I skipped our Y. So our is, basically you have like the
Stefan Krastanov: what do you call it? It's. R Not is the lower, you know. Well, on it is a constant right. So our of Ck is the rate of, like, you know, a given rate, right? And delta is the end of bound. How much tolerance you have in that?
Stefan Krastanov: Yeah, the rate of the goals. Are they to seek right? So everyone is right. So
Stefan Krastanov: the solution as you'll see to this problem, we didn't make a make. You know
Stefan Krastanov: decision. When you talk about it, we'll replace this with one by 4, so we'll actually have at least one by 4 to have a reasonable error directing code by
Stefan Krastanov: No. Wait, wait, wait. Rate and distance are 2 different things.
Stefan Krastanov: So
Stefan Krastanov: yeah, I was this for
Stefan Krastanov: that. You can enroll distances for how much you can correct. Correct is this for the so I assume R is for the rate, and they will. This something related to
Stefan Krastanov: correctional capabilities that might or might not be expressible in terms of the
Stefan Krastanov: I think, the textbook, the example they give. They use that as like the having distance I have, I mean they're having, but they say they say that it is any metric there. They have to be some metric that quantifies the tolerance as to how far you can go and correct it. Okay.
Stefan Krastanov: Lesson the question about your plan.
Stefan Krastanov: Yeah. But it's I will. There's always some small.
Stefan Krastanov: I'll confuse.
Stefan Krastanov: You might make it sense that the type of
Stefan Krastanov: so this claim actually relies on the construction of what we just talked about.
Stefan Krastanov: Z is the nearest, you know. If you go back to like the previous slide. Z is basically what it's a code. But that's close to the you know
Stefan Krastanov: Why, right? Which is the string that was received, or which is the encoded more modified. So
Stefan Krastanov: yeah, ideal situations like this is a framework. This is not a a specific example. Right?
Stefan Krastanov: You get a string, and based on what you would happen.
Stefan Krastanov: You know the small call with small, or if you would change the wall. But there.
Stefan Krastanov: that I do see what you're trying to say. But the problem is when you when like, if you read the textbook itself, you're doing this in a very idealized situation, You're assuming that even then you will be making that idea wise. The point of that. So
Stefan Krastanov: probably what you're trying to say is that okay? If you
Stefan Krastanov: the 2. Pm.
Stefan Krastanov: Hmm. That's all Your average number of errors
Stefan Krastanov: and a need of a need.
Stefan Krastanov: It? You have less errors than that. But you're going to need to.
Stefan Krastanov: There is a
Stefan Krastanov: yeah, I
Stefan Krastanov: That's a good point, I think. Yeah, maybe it is too strong over here.
Stefan Krastanov: Maybe with with a high probability kind of an argument. We can put that for that. That's a good to catch. I don't know if you do. If you read the chapter, they actually need the same very strongly, as if, like, you know, then they're probably making a slightly different kind.
Stefan Krastanov: saying there is some fixed number of
Stefan Krastanov: the flips that they're applying, or something like that.
Stefan Krastanov: When you send your initial string. Pn. Is the maximum deviation it can have from its original thing, like if i'm thinking about it in terms of this. If you think about in 2 in Cartesian, and each coin
Stefan Krastanov: is mapping to some code word. If the deviation from that code word
Stefan Krastanov: is pn right the probably didn't each bid, and then n times that happening. And if any 2 code words are
Stefan Krastanov: greater than
Stefan Krastanov: that distance, you cannot deviate from that enough to If P. Is some fixed trash for ability. Yeah, then, that sounds true. Yeah, it's a probability of like each. It's not the
Stefan Krastanov: okay, which is also the assumption. If we start now, we like, we're resuming you, that we use the fraction of the bits, that the same that may be altered. So I think it really comes back in right on the top right? So it really comes back to what? Because I just mentioned that, you know, If you have like a fixed fee, then this assumption may be true.
Stefan Krastanov: So
Stefan Krastanov: that is what you know, was the second problem, which, and you see a solution using standard graphs. Once we go into that
Stefan Krastanov: and a large problem, probably the most complex one, probably 3, I guess.
Stefan Krastanov: Does anyone have a background in randomized algorithms.
Stefan Krastanov: Rp: plus. We're gonna talk about the Rp class of algorithms here
Stefan Krastanov: and
Stefan Krastanov: There's a very big description, I think, because they talk in terms of languages and strings itself. But what this problem is really coming down to is saying that let's say you have. You know, a randomized algorithm right? If you have an algorithm you're running again and again reduce the error. Probability.
Stefan Krastanov: How many random bits do you actually need to reduce probability
Stefan Krastanov: and bounded by some?
Stefan Krastanov: And the way the famous is by saying that you know, you can assume that every you know, this randomized algorithm basically goes through another algorithm that converts it into an encoded string over 0 1,
Stefan Krastanov: and then it outputs like yes or no kind of situation.
Stefan Krastanov: We will go to detail about that. Once I won't go to that. But the reason why this kind of an approach works is because we know if you have an algorithm which has a given failure probability, then, if you repeated d times.
Stefan Krastanov: the probability of pay, you will actually keep it. You reduce the 2 to the one negatively.
Stefan Krastanov: and the downside Here, of course is that you are running it again and again, which also means that you will boost up and running time, and a number of random bits you will need to do. This will also go up by the factor of the which is the number of times you're trying to run it.
Stefan Krastanov: So the major question then, is.
Stefan Krastanov: can we really, you know, reduce this error without going without using more random bits in this? You know what does, using around a little bit.
Stefan Krastanov: So every so if you look at the language representation right? What's going to happen is L. Is a language over it. It it represents a one-sided error.
Stefan Krastanov: So every time you run the algorithm the outputs, whether you know you have like whether this something belongs to or does not belong to there. Okay. So you have to store that. Okay, so that's what the extra random bits are going into, because every time you store it you will keep boosting up your random version
Stefan Krastanov: Questions.
Yeah.
Stefan Krastanov: you can. You can automatically see we are trying to minimize that in a way. Yeah, we do. We want to have the possible length of the encoded. I'm. Not in quoted string. Let's just say a string and help is this sort of with the string and L, or a string of output results.
Stefan Krastanov: So at the end of the day we are. What we are trying to answer is whether it's it X is a string right Doesn't belong to it or not, because if it belongs to it, and it's in the class of Rp: okay, which means that now you know that you can have a random polynomial for that.
Stefan Krastanov: And that's the kind of a room that we're trying to design designing. We use an algorithm for this which basically out works better of given, you know. String can be sorted. They can be sold in full on the time or not.
Stefan Krastanov: and back to what does it mean to
Stefan Krastanov: how many random bits are needed. But this means you need to around a bit. Is that about the able to train? Is that about how many times you've done that over time. Yeah. So it we'd eventually see that the the factor D: it actually depends on the
Stefan Krastanov: so the number of times you on the algorithm will kind of affect both. How much error you can bound.
Stefan Krastanov: and also the fact that how many more bits do you need? So we? What we try to do is we try to minimize the and by not compromising. Yes.
Stefan Krastanov: sorry. I still don't understand what it means to you around a bit. Here it's. Dynamic itself is going to. Every time you run the on right you could keep a track of whether the out like this, like a majority board situation. Right?
Stefan Krastanov: You keep running the algorithm and you have to store what happened when you run this algorithm through. You know the which tries to say that, you know. Is it going to be sort or not? So I think there's a question in chat.
Stefan Krastanov: Does this mean.
Yeah.
Stefan Krastanov: we'll come back to. I think it will be more intuitive when we start talking about the solution of the problem itself. But for now the set up of the problem really is that we are trying to, you know. Reduce the we write a bound the error by reducing the number of extra that you're trying to store here.
Stefan Krastanov: Yeah. So the language, one element of the language. Is it
Stefan Krastanov: a class of errors, or is it a specific?
Stefan Krastanov: So if you're deciding on this line that you're deciding whether or not this has.
Stefan Krastanov: and this.
and
Stefan Krastanov: talking about this. So I don't think you vp. Some like.
Stefan Krastanov: And I remember reading somewhere that there is a class of problem that exist that if you provide some random key to it, it can solve. It
Stefan Krastanov: is this random key sort of like that situation or
Stefan Krastanov: so be. You know.
Stefan Krastanov: we this is a different class about what we're talking about.
Stefan Krastanov: I'm not so sure.
Stefan Krastanov: but
Stefan Krastanov: from my understanding I don't think like you know, like that is what they are trying to do here.
Stefan Krastanov: Yeah, because randomized algorithms are like, you know, they're more probabilistic than you know, like how we we we are poaching a from probabilistic perspective, not the descriptor complexity perspective. I'm. Pretty sure Rp. Falls somewhere in the same scheme near Vp, because the characteristics are not very different. But
Stefan Krastanov: yeah, I thought I should check that out. That's a really good question, I think. next door.
Stefan Krastanov: So
Stefan Krastanov: what we're gonna do now is actually talk about a graph which are very happy. You can call a magical graph
Stefan Krastanov: because of you know, it's expansion capabilities.
Stefan Krastanov: and that is itself sounds very quick, but
Stefan Krastanov: I try to read it. This is like a more simpler, you know, kind of approach.
Stefan Krastanov: You have grabbed Chi, and you know there's no restrictions on what this graph could be. It doesn't have to be regular or something. We will have some, but the only restriction is that it needs to be a bipartite. So for someone doesn't know a bipartite. That is, basically be partitioned in 2 subsets, right? You have L. And R, which are the new subsets of all the vertices.
Stefan Krastanov: and he is just the edge of the script. So
Stefan Krastanov: what we really want is that
Stefan Krastanov: if G. If this graph. G. Let's say the size of L or the left subset of the vertices is n our decided to have the right subset is M
Stefan Krastanov: Doesn't. Have to be equal, it could be equal, but it doesn't have to be.
Stefan Krastanov: and if every left vertex, or what I mean by left vertex is that if you have the set. L.
Stefan Krastanov: Every vertex in l have the
Stefan Krastanov: so. This is this is the weaker requirement in the regularity where every vertex needs to have the you know, edges or new neighbors. But here we can. We just are concerned with the left subset on the
Stefan Krastanov: and we're. We're mostly interested in seeing these 2 properties, one and 2,
Stefan Krastanov: which.
Stefan Krastanov: just to clarify this
Stefan Krastanov: function that you see is kind of just denoting the set of the neighbors.
Stefan Krastanov: So let's say you have a subset, as N. G. You select is up there, and then.
Stefan Krastanov: when you pass as to the function, you get the set of the neighbors of that set, as in G. So all the neighbors engine.
Stefan Krastanov: What we're trying to do is we're trying to. You know. Again, you're trying to find bulbs for these numbers.
Stefan Krastanov: The first one kind of is very intuitive. It just says that you have the as a number of neighbors for the left set.
Stefan Krastanov: If you take any subset this, then the number of neighbors in the in the graph of this subset should be greater than, or equal to 5 D. Over 8
Stefan Krastanov: and times the size of the set itself, as
Stefan Krastanov: hi
Stefan Krastanov: as the side of S should be bounded by and over, namely.
Stefan Krastanov: it's
Stefan Krastanov: and the other situation. Actually, the second case mainly is the case that happens when you have S. So right now we have s learning size of s less than n o D. The other case is what would happen if you have a size of the subset between this quantity and the Nd. And N. Over 2, which is like the how
point.
Stefan Krastanov: and in that case we just want the number of neighbors.
Stefan Krastanov: you know, offset F and G. To be greater than equal to the
Stefan Krastanov: that's difficult to visualize how this might be helpful. So actually have a picture here which
Stefan Krastanov: is not necessarily a magical graph. This isn't a magical drop, but it still represents what we are trying to delay. So
Stefan Krastanov: you start with this. You know what you got. 2 sets right to this time. Set.
Stefan Krastanov: and you select
Stefan Krastanov: some s it could be any, and it's a for all the statements so it could be a. Yes.
Stefan Krastanov: every vertex here is going to have the connections or the edges out connected to the
Stefan Krastanov: and
Stefan Krastanov: what we just seen in the very specific case of the way you we are, we bound it. But a more general claim could be. We are trying to bound the number of neighbors by some thing times as itself right, so sometimes the set itself
Stefan Krastanov: where a could be any.
Stefan Krastanov: The only thing we have done in the previous slide is
Stefan Krastanov: we have just used, you know, a very specific. We divide this to 2 cases on the basis of how many you know
Stefan Krastanov: what's the size of the set is. and turns out these constants are actually not, you know, very
Stefan Krastanov: static. You can actually
Stefan Krastanov: change a bit like, you know. This is this is the reason why it's for a medical graph, because somebody came up with this, and like they provided justifications for this. But this does not mean that this won't work. If you change and over time you can do it. This is probably one of the most effective approaches we have seen so far.
Stefan Krastanov: So just to try to get the intuition about this, I
Stefan Krastanov: see that the neighbor, the the
Stefan Krastanov: the outgoing ages, basically or the most that are connected to
Stefan Krastanov: true outgoing edges.
Stefan Krastanov: We have some guarantee that those would be bigger than the subset. We
Stefan Krastanov: we don't have any other
Stefan Krastanov: interesting constraints like. There is nothing about that. All regular graphics, or or anything like that. Yup. So yeah, there's no regular condition for, like you, being regular as far as you have a bipartite graph, it's completely okay for like this.
Stefan Krastanov: Do you have graphs which
Stefan Krastanov: the
Stefan Krastanov: neighborhood is basically bigger than the subset for any arbitrary subset. That is true.
Stefan Krastanov: Yeah, I I think you know just a context, this image that you are seeing this kind of like the your general bound.
Stefan Krastanov: This is actually coming from what we you know this is.
Stefan Krastanov: Yeah, if if we have some, you know terrible
Stefan Krastanov: constraints, you Don't: yeah, we do. The constraints on B are going to be down there. I'm going to talk about it in a second, but they they they are on frames on the 2, which will actually tell you about the size of the graph itself. But yeah, just so it not. This picture is basically what we. This kind of graph is what we call a bipartite standard row.
Stefan Krastanov: which is more like a more big, a generalization of what we just saw. So that's where this whole idea is coming from. But we are only concerned with logical draft, because that's what you know. The solutions we are going to build are based on.
Stefan Krastanov: And as professor of you like, you said that there needs to be some boundary right? You have to have some limitations on me.
Stefan Krastanov: You can show probably this technique using a randomized approach
Stefan Krastanov: to see that you know there exists a constant and not such that for every decade and equal to 32,
Stefan Krastanov: which means that the graph is very big, because when you say these 3 do without more to do neighbors.
Stefan Krastanov: and the guarantee we have is for d greater than 30 to equal 32, and for every number n greater than not, because the minimum number you can have, and m greater than 3, N. By 4,
Stefan Krastanov: this number 3, and that will become very handy. You don't, when you start working with this that exist in it, and be magically row.
Stefan Krastanov: So we are there. I need a graph, but we are only going to this kind of graph, and we have it is 32 outgoing
Stefan Krastanov: so
Stefan Krastanov: very quickly. What I want to talk about is how we how does this relate to what we've talked so far? We started the first problem. Maybe we were talking about. You know the super concentrators right?
Stefan Krastanov: Using a management. Wr: You can actually make a super concentrator in order of any
Stefan Krastanov: which kind of resolves the problem that we were thinking about. So
Stefan Krastanov: let's say you start with the end 3 and by 4 d graph. Right, you know, this is like a magical graph.
Stefan Krastanov: and we just saw that, you know we just saw about the number sign that set right for any of the sets. S. You'll always have the signs written in the for us.
Stefan Krastanov: and
Stefan Krastanov: for this
Stefan Krastanov: it is also it needs to be noted that the size, as itself is bounded by N. Because you cannot have this upset bigger than the set itself.
Stefan Krastanov: and then we are not going to go beginning to overall as much as it is saying here. But what we really need to use here is the fact that
Stefan Krastanov: because we have this subset, as you know, like because we bounded buying by to when we actually talked about. You know. What do you call right there you were talking about. We had the invite in term here right
Stefan Krastanov: because they bounded by by 2.
Stefan Krastanov: We can actually use the hostage to say that there is a perfect bijective mapping from this to the subset as the neighborhood. Right so.
Stefan Krastanov: And this matching is what leads to the you know bipartite graph nature of what we're observing, because there's a If there's a you can All this get a by a.
Stefan Krastanov: And the way you received this is that
Stefan Krastanov: we started with this N. 3 and that 4 d magical graph. Now we make 2. We make 2 copies of it, and you call them team in the G 2, which we just like, you know, have right up here. Do you enter that
Stefan Krastanov: where L. One and I I basically like for everyone in their 2 are both in then any number of like nodes and Ri is 3, and by 4, which is in the actual. Follow up from here, because that's the configuration right.
Stefan Krastanov: Then you could start the super concentrator and and the superintendent call it c.
Stefan Krastanov: Which connects the set R: one with R. 2,
Stefan Krastanov: which
Stefan Krastanov: is very non-intuitive from this image. But yeah, just to see is is super concentrated right here, which we're trying to build, but because we know there's a matching. There's a perfect match in that exist right? Question anyone.
It's just like.
Stefan Krastanov: how are
Stefan Krastanov: one to one. This is a perfect match, right?
Stefan Krastanov: And yeah, construct finally a perfect match, and to be able to. So
Stefan Krastanov: what you're seeing essentially is a subcommittee, and I don't think there's any doubt that this is on your end, because we get sort of, and there's no justification for that right. I mean, there is justification for that. If we start doing some pro argument here.
Stefan Krastanov: any questions.
Stefan Krastanov: The second problem we start talked about was really about, I mean a good code, right? So what we're gonna show now is that you can actually build something like an early PC code using this kind of for graph.
Stefan Krastanov: And you're going to use one simple fact that
Stefan Krastanov: again you started the same construction and left we' to see 3 and 4 right words. These and 3 by and 3, and that 4.
Stefan Krastanov: Aye.
Stefan Krastanov: you can actually show this, using a contradiction proof that if you have a non-p subset s such that the size of S is bounded by N. Over 10 D.
Stefan Krastanov: Then they will always be awarded to you in the right set.
Stefan Krastanov: which has exactly one that you would it?
Stefan Krastanov: So
Stefan Krastanov: yeah, the the Pope is by contradiction. It's just a counting argument. You can actually show that your accounting and why does that help us?
Stefan Krastanov: Is because
Stefan Krastanov: this basically tells us that if you start with the magic graph orle like as usual. and this time you represent this graph as a matrix. Let's have it agency matrix. Right
Stefan Krastanov: then. You know that eig has to be either one or 0.
Stefan Krastanov: How do you decide? But it's one of those, you know. You just check in the I word x in our it's gave us into the Gs. Vertex in
Stefan Krastanov: and but by this fact we know there will always be one case where every you know what you call you. There will always be one vertex, you in the right set, which will be the neighbor set up as right.
Stefan Krastanov: and
Stefan Krastanov: the team here is that this graph that you started with or you got it? Could you start with the graph? Maybe it doesn't see matrix right?
Stefan Krastanov: What we're more interested in this graph, is it's kernel? So the kernel of like the If you take an abstract, either you would know it's like all the elements that map to the identity in the
Stefan Krastanov: So this is like. If you have a, then in case of like the speed, you will have a X to 0, because you don't do that in Youdi the 0 matrix.
Stefan Krastanov: So all the elements that are mapping to the X equals 0 will be the kernel of C, which we just talk, or just see it as a good nose.
Stefan Krastanov: and, as you can see, since X belongs to all, or one to the end. This is a subspace of one to the end. And we have already seen that before that
Stefan Krastanov: if we can actually claim that this is a linear code, right? Because it's a subspace. It's a leader subscribe.
You zoom.
Stefan Krastanov: You have the class, and so a is the and so
Stefan Krastanov: sees the quarter of.
Stefan Krastanov: and that graph, that magical graph is just the panor graph.
No.
Stefan Krastanov: and
Stefan Krastanov: the dimension. You can again. You can show this, you know. You can use a company, or even to see that it is getting in by 4.
Stefan Krastanov: So in in my 4 right. So we have an over 4 degrees of freedom.
Stefan Krastanov: and
Stefan Krastanov: I think it's. It's natural to follow from this claim. You can already see that you can actually see that he's not only a core, but it does a coordinate at least one by 4 great. and the distance is at least one by 10 d. This is basically St. In from here, because we started with the function of N over 10. B. You can actually show this mathematically. Why you're
Stefan Krastanov: the proof. Is there in the book itself.
Stefan Krastanov: In the
each
Stefan Krastanov: bit was connected to a constraint.
Stefan Krastanov: Let's go with the Ch: yeah. But the constraint check is okay. And these like sort of the connections that we're going to
Stefan Krastanov: is that it's the direction or these, the big green of one input to our, or rather not our one to watch. Yeah, could you? So the like when we started with D right.
Stefan Krastanov: we we really started with like this slide right where we were talking about
Stefan Krastanov: the number of neighbors of this, you know, like in the left set.
Stefan Krastanov: So the L. Which is your said
Stefan Krastanov: every like, if you select every vertex in the second.
Stefan Krastanov: Okay, yeah, okay.
Stefan Krastanov: And the last problem. That's you know, trying degree of discounting. I'll also you have out of the left Sa: to the right. Yeah.
Stefan Krastanov: And the third problem that we were talking about about Rp.
Stefan Krastanov: So yeah, the
Stefan Krastanov: So what is what is the what does it mean for an algorithm? To really be in the Rp class which just brings us back to the we started from.
Stefan Krastanov: and the catch is that, you know. Let's say that we need to check whether they exist. The polynomial algorithm that receives a string X,
Stefan Krastanov: and it's so that it receives an input X and an item cab it string are as the screen itself that you were talking about, right? So there's an input X in the string to say, and our average string.
Stefan Krastanov: and this
Stefan Krastanov: you can manu it some function over X and R, which is one whenever X is in the language. This the input, I received.
Stefan Krastanov: but it's one with the probability at most 161 by 16. You can change this constant with the probabilities that it's not in there.
Stefan Krastanov: So this is again the idea. You take X and a random string the cables, and you have an algorithm which is outputting whether it is in this Rp. Class or not. Yes or no, the problem itself. And then that's a or something. It is in the language or not not the Rp class.
Stefan Krastanov: If such an algorithm may exist, then it belongs to the Rb. Class. That's the exact definition of what the Rp. Classes.
Stefan Krastanov: And how do we do this? It's actually again very simple. We start with the same. You know, similar construction to what we've been doing. The only difference is this time we start with the magic, the graph, but in which the number of vertices is actually to the Bar K,
Stefan Krastanov: which is exponential.
Stefan Krastanov: which just very quickly tells you that this is not going to be an easy instruction. This is very tricky to implement in practice.
Stefan Krastanov: And
Stefan Krastanov: how you do this is you have R and L. You set. Each vertex is basically representing a unique cable string.
Stefan Krastanov: So every vertex is a string itself
Stefan Krastanov: gibbets, and then we are randomly sampling our, you know, strings or random strings.
Stefan Krastanov: which are basically
Stefan Krastanov: So let's call them R one to Rd. Because we have something, it being that right.
Stefan Krastanov: and let all through our email strings associated with the D neighbors of our.
Stefan Krastanov: Because now our we are saying, Our is okay with string from L. Right? It has. It has some neighbors in the our set.
Stefan Krastanov: We want to be the string associated with these.
Stefan Krastanov: and we just check. So what we're trying to do is we will output one.
Stefan Krastanov: If the function that we are evaluating which we don't know what the function is, but you evaluate it for X and r, one x and r 2 till X and R. D.
Stefan Krastanov: And if all of these are equal to one
Stefan Krastanov: then only, if you were to do one or you don't. Yes, otherwise it's automatically
Stefan Krastanov: any questions here.
Stefan Krastanov: So is this all the time but the exponential in space because you need to to save my special large graph. Yup. You have to see an exponential, large graph which limits its you know usability.
Stefan Krastanov: And again. You can do something that you're not going. That's what they do. You can actually show that, given the integer B,
Stefan Krastanov: you will evaluate F. Only D. Times, because our one through R is the cap on the number of neighbors right, because the left set itself has at most our neighbors of them.
Stefan Krastanov: and it will pay the probability of Epsilon, which will always be founded by one over 10. This is a picture of our application, if you know what the Channel found. Is
Oh.
Stefan Krastanov: any questions
Stefan Krastanov: so
Stefan Krastanov: to summarize what we've been talking about, and to, you know, give some pre-ex for us to as presentation. We will be starting very soon. I have one of my disappointed. So
Stefan Krastanov: we went back to the 3 perspectives we started from. We had a combinatorial view of expansion. We had an algebraic view, or we we also had a probabilistic view.
Stefan Krastanov: So what is this? What do you really mean by expansion now? And how do you quantify it. We start with the edge boundary of the set.
Stefan Krastanov: which basically is, let's say you have a graph. You have. You take a stop search. S. And you all the anything that's not in the set is the complement right? So what we're trying to do is map these. You know, edges out of S into this complement.
Stefan Krastanov: That's the edge boundary of us, which is noted by accommodation. and
Stefan Krastanov: the quantity we are interested in is the expansion ratio which tells you how, which quantifies the expansion itself. But now
Stefan Krastanov: we very careful we are talking about a d regular under the
Stefan Krastanov: We are shifting into completely dedicated graphs now for the next for the remaining presentation, and probably
Stefan Krastanov: this does not have to be bipartite. But what we're trying to say is.
Stefan Krastanov: we take a set, as let's say. And now, when you want to find out the expansion ratio.
Stefan Krastanov: we want to find the our minimizer right. Go to find this.
Stefan Krastanov: which is always bounded by half the size of this graph, so it's the size of 109 by 2 you want to find. and as that minimizes. You know the what do you call it? It's just emanating from S
Stefan Krastanov: over the total size of it.
Stefan Krastanov: And
Stefan Krastanov: to actually visualize. This is a good image, and you have s and everything that's prime actually is complement right? So you you you want to have this kind of you want to find a set. Yes, that's the question here which is bound by by 2 which is minimizing this region. The one that you know has this ratio is your expansion ratio.
Stefan Krastanov: And
Stefan Krastanov: you can actually make multiple like, you know, graphs out of this right? Because when you try to find like S, you have sequence of graphs coming up.
Stefan Krastanov: and the sequence of these graphs will be increasing size. Yeah, be careful. Here you have a in.
Stefan Krastanov: and for their graph you do. You find the expansion ratio as this by trying to look at some graphs. And that's the expansion ratio for the undergrad
Stefan Krastanov: that has got this.
Stefan Krastanov: When they were looking about at families of wraps, and for every single one of those graphs of that family. every single one.
Stefan Krastanov: Yeah. So well, you going back to this? That's a good regulation. But yeah.
Stefan Krastanov: the catch is that we we just. We have this
Stefan Krastanov: sequence of the regular graphs. which
Stefan Krastanov: i'm an increasing size as I've been breathing, but over the natural numbers. And it's a family that's kind of graph. If we can find an Epsilon
Stefan Krastanov: which is basically giving us a a lower bound for edge of G, which is an expansion ratio
Stefan Krastanov: for all I
Stefan Krastanov: There's a lot of other definitions, something like a mighty, you know my family, and like a strong family. You can actually check that out in the book in case you're Christian
Stefan Krastanov: in terms of the spectral view of this point. Right? So where does that go? So just some context, like, what is spectrum like if you have a matrix right? Every matrix has I in that
Stefan Krastanov: the
Stefan Krastanov: So
Stefan Krastanov: this the graph we're talking about now, the regular.
Stefan Krastanov: and we know from spectrograph theory that the largest I in value a pretty regular graph will always be
Stefan Krastanov: if you make the graph. So the lambda one is the largest eigenvalue which we are not really interested in, because that's the that we know. Lambda 2 is what we're interested in second largest eigenvalue, because that pointifies a lot of you know expansion.
Stefan Krastanov: and that's what a stereotype is trying to say that you know. Let's start with the grab. She just d regular, and Has Eigenvalues Lambda, one number 2, all the way up to Lambda n.
Stefan Krastanov: then
Stefan Krastanov: d minus lambda 2 or the difference of like the d, like the d from here, or the
Stefan Krastanov: minus lambda to over 2, is a lower bound for the expansion ratio, and the upper, bound for the expansion ratio is square root of 2 times V. D. Minus lambda.
Stefan Krastanov: and this be my plan. By it's called the expansion radio. It's calling spectrum cap.
Stefan Krastanov: It's a very important quantity in like. I I started like I took a spectral. Actually. So. It kind of is very important, even in randomized algorithms.
Stefan Krastanov: Because, yeah.
Stefan Krastanov: So what's the verdict out of this like, what is this bound really trying to tell us? It's just right. There is that if you have this d minus Lambda to the spectral graph which is away from 0, it's not to wait, or it's increasing. More likely, then.
Stefan Krastanov: this this basic details you. The expansion ratio itself will always be because this bound bounded away from 0
Stefan Krastanov: so we can. It's all this possible to have an expansion issue, that's all. And I think I should have put this picture here. This is just a way of how you calculate to the blast you. And so with this graph, you know you just take the diagonal matrix there, the and then you can take the it's the degree with present or dime dig reading, so that 1 3 2, and so on.
Stefan Krastanov: And you create Asd matrix the supply. Then you get in the blast in all the eigenvalues show up as that in the
Stefan Krastanov: Yeah.
Stefan Krastanov: I Not that I'm aware of it.
Stefan Krastanov: This is, yeah. This is still like an area that is, you know, under extensive research. So not a lot of people have actually proposed things beyond the
Stefan Krastanov: I mean. People have come up with.
Stefan Krastanov: So they're bound for like You're got a screen.
Stefan Krastanov: But it was, too.
It was there. There are.
Stefan Krastanov: so as as long as you have sort of well defined clients
good support
Stefan Krastanov: I
Stefan Krastanov: the last. Probably I need to be a time. So yeah.
Stefan Krastanov: an important consequence of this is what we call the expanded mixing lemma, which basically talks about. You know. Again, we start with G, which is the regular graph having in vertices. And we now define Lambda
Stefan Krastanov: as land of G. Now, what is the slam dog Computing is Basically the
Stefan Krastanov: I saw you value apart from me. So that's the second large signing back right, the the maximum of number of so it's again. Second, it's a large standard value other than that one which is D.
Stefan Krastanov: So
Stefan Krastanov: this Lemma is trying to tell you that if the E. St. Is basically the set of the edges within the phone. S 2D
Stefan Krastanov: right.
Stefan Krastanov: What we're trying to do is we're trying to bound this. You know these 2 already.
Stefan Krastanov: By the second you have side value. Times the square root of the size of.
Stefan Krastanov: But the problem is, what are these 2 warnings? So the first quantity, as you might expect is just simply the number of edges between the 2. Snp, right?
Stefan Krastanov: The second quantity
Stefan Krastanov: is from a probabilistic perspective which
Stefan Krastanov: we which I have actually written it out for you very quickly is that it's just the expected number of edges between S. And D.
Stefan Krastanov: Assuming that the graph is random within Http. Over here.
Stefan Krastanov: So this is like an ideal, you know. Situation that we are trying to imagine, and we're trying to modify. How far is you know our edge set from that. And you can actually bound that by
Stefan Krastanov: this deviation that you are seeing is basically trying to. It's kind of conveying the fact that the closer. Es T. And the those of these 2 quantities are
Stefan Krastanov: the more random your graph is right, the more nearly land in your
Stefan Krastanov: and that is kind of helpful for us, because no problem is to perspective. It's standard graphs as to random, so it kind of reinforces the same idea, but from a different don't need
Stefan Krastanov: get a question. Yeah, the do you require us? And to be this joined? Yep, Smt: are just joined.
Stefan Krastanov: We should probably
Stefan Krastanov: this. Yeah, that's fine.
Stefan Krastanov: So yeah, first, thank you.
Stefan Krastanov: I would suggest we let the go next and then do Q. And a. After that, just to make sure that we have enough time.
Stefan Krastanov: The
Stefan Krastanov: basically the the idea of the coming up to here is describing interesting properties of these graphs describing these sequences between
Stefan Krastanov: properties of the adjacency matrix, and this much more difficult to
Stefan Krastanov: conceptualize, difficult to estimate properties about expansion. The fact that you're very well connected, even if you're sparse, which was the concentrator point you or
Stefan Krastanov: you have very.
Stefan Krastanov: You have to 12 big neighborhood, you for any arbitrary subset which was the expansion of good vision. And now we'll be.
Stefan Krastanov: We'll review some of this, and we'll go into how you can construct some of those
Stefan Krastanov: which is again very interesting, for only the
Stefan Krastanov: those graphs capital of the property soprano algorithms, but you get to construct them explicitly. So you you can use them to do randomize algorithms.
Stefan Krastanov: and we'll talk a little bit about the air correction with the base of these graphs again, because
Stefan Krastanov: it's a very good way to create good spar stanographs.
Stefan Krastanov: A Schleisher, if you can introduce yourself and think stage.
Ashlesha Patil: Yep. X.
Ashlesha Patil: Hi. Everyone. I'm Ashlisha Patel. I'm from University of Arizona, and I am, i'm 50 or Phd. Student.
Ashlesha Patil: So
Ashlesha Patil: man uncovered a lot of the things I
Ashlesha Patil: We'll talk in the first few slides.
Ashlesha Patil: but i'll still go through them. and this talk is more like
Ashlesha Patil: an example-based uproot to understanding expander graphs and their interaction properties
Ashlesha Patil: Sorry about. So the slides are mixed of mix of type slides and handwritten notes. So sorry about that.
Ashlesha Patil: Also I found a couple of very good Youtube videos. and some of the slides, like a couple of slides, are taken from those. So one of them is Youtube channel called Visual Mac
Ashlesha Patil: and I, i'll post the link of the other Europe Channel.
Ashlesha Patil: Okay. So now, let's say you have
Ashlesha Patil: you have to design the metal lines of your setting. Then what parameters do you consider?
Ashlesha Patil: So first, we want to avoid bottlenecks, meaning we don't want
Ashlesha Patil: single line disconnecting to completely disconnecting 2 parts of the city.
Ashlesha Patil: or completely disconnecting
Ashlesha Patil: 2 sets of Metro stations.
Ashlesha Patil: And then we also want our connections to be efficient meaning. You don't want to connect every station with every other station using a line.
Ashlesha Patil: And that's where expander graphs come in. So expander graphs are used in designing these traffic connections. Also in
Ashlesha Patil: data centers, computer networks, and so on.
Ashlesha Patil: So the first condition on expander graphs is that they need to be sparse.
Ashlesha Patil: What do I mean by that? That the ratio of
Ashlesha Patil: the number of edges to the number of notes needs to be small. So if we consider a d regular graph, then we would have
Ashlesha Patil: d by 2 it is.
Ashlesha Patil: and if you take the ratio it
Ashlesha Patil: just grows linearly with the degree of the graph. The second thing is. Oh.
Ashlesha Patil: it's expansion coefficient needs to be high, so the expansion, coefficient is also called a tiger constant. which is as a man and described is Hmm. The ratio of
Ashlesha Patil: bill boundary of a set of edges to the number of what is this in the set? So, for example, if you consider this graph here, and
Ashlesha Patil: if the highlighted blue nodes, is our s
Ashlesha Patil: Then. though
Ashlesha Patil: delta of S.
Ashlesha Patil: All these edges here.
Ashlesha Patil: and the cardinality of that set is a
Ashlesha Patil: So we want this ratio to be higher. which implies that the graph is highly connected meaning, if you're
Ashlesha Patil: meaning it, if you can also see it as it being very difficult to cut across this cross section.
Ashlesha Patil: So let's say, if you're one of your metal lines along this boundary.
Ashlesha Patil: then it doesn't affect your overall connectivity that much.
Ashlesha Patil: So we want large it.
Ashlesha Patil: and we want the graph to be sparse.
Ashlesha Patil: Then another thing is.
Ashlesha Patil: we also want a method to deterministically create and expand. Okay, so
Ashlesha Patil: you can say that every connected graph is an expander graph. If it's not connected, then it's not an expander.
Ashlesha Patil: But we need a method to create
Ashlesha Patil: good expander graphs with high expansion coefficient.
Ashlesha Patil: So before we dive into that, let's look at Kelly Graphs.
Ashlesha Patil: So a Kelly graph is a graph that encodes an abstract structure of a group. What do I mean by that? Let's consider an example.
Ashlesha Patil: So let's say we have
Ashlesha Patil: this F in a circle
Ashlesha Patil: as a vertex.
Ashlesha Patil: and we define the group of our graph a and B. So the group a is
Ashlesha Patil: 90 degree clockwise rotation of F and Group B is
Ashlesha Patil: mirror image, taking mirror image of your vertex.
Ashlesha Patil: So this example is derived from the Wikipedia piece. So now let's start building the graph. Let's start with F.
Ashlesha Patil: Then we apply
Ashlesha Patil: the generator a. To it.
Ashlesha Patil: rotate at 90 degrees and keep doing it.
Ashlesha Patil: So we start with E. We apply a: so then we apply a square, a. Q.
Ashlesha Patil: And when I apply a. To the power 4, I come back to F. And in telegraph you need to draw these directed edges to show
Ashlesha Patil: how the generator is progressing.
Ashlesha Patil: Then I
Ashlesha Patil: to F. I would apply B and get a mirror image.
Ashlesha Patil: and to this B. I can then keep applying A and get the outer square. and so on. So
Ashlesha Patil: you also in telegraph. You also have to color the ages differently. So whenever you are applying B, you are drawing a blue edge instead of a red edge.
Ashlesha Patil: And this edge there is no arrow, because it's bi-directional If you take
Ashlesha Patil: a middle image of a mirror image. You get the original image back.
Ashlesha Patil: Okay. So let so sorry. Yeah.
Stefan Krastanov: The
Stefan Krastanov: The group is all 8 objects, all 8 possible orientations in the
Ashlesha Patil: yeah. It should be generative
Stefan Krastanov: of a very small set of generators. So
Stefan Krastanov: it all in the group give you notes, but then
Stefan Krastanov: a small set of operations that you spend the entire group. Give you the edges.
Ashlesha Patil: Yes.
Stefan Krastanov: Now please go ahead. Yeah.
Ashlesha Patil: So let's consider another example. Now
Ashlesha Patil: we have defined our telegraph over Z 4 meaning. We have only up to MoD 4
Ashlesha Patil: notes in the group, and our generator is one.
Ashlesha Patil: So let's say we are at node 0.
Ashlesha Patil: If we add the generator. So let's. We are at Node 0 here.
Ashlesha Patil: If we add the generator, we would go to one.
Ashlesha Patil: from one we would go to 2, from 2 we would go to 3
Ashlesha Patil: and then come back to 0.
Ashlesha Patil: So we will now use this
Ashlesha Patil: Kelly Grab to construct an expander graph.
Ashlesha Patil: so i'll talk about the Margulus
Ashlesha Patil: Gabriel construction which is equivalent to the spectral expansion technique that one and discussed. So we start with
Ashlesha Patil: a graph.
Ashlesha Patil: So these are not in vertices. But you start with graph whose vertices are in Z and cross. Zn.
Ashlesha Patil: So basically we are in the MoD End group.
Ashlesha Patil: And then we choose a vertex vertex xy. In this graph. So this is a Kelly graph.
Ashlesha Patil: and from that
Ashlesha Patil: we in the expander graph its neighbors are
Ashlesha Patil: given by this set here. So there are 8 neighbors. So, for example, here i'm growing this example.
Ashlesha Patil: we have this Xy node in the Kelly Graph.
Ashlesha Patil: and then in the expander graph you would have 8 of these nodes
Ashlesha Patil: fit coordinates given by this location or this set here.
Ashlesha Patil: So the resulting graph is an 8 regular expander graph, because every node would have 8 edges. and Merulus also showed that the expansion, coefficient of this graph is
Ashlesha Patil: greater than point 4, 6, and you can actually derive this number
Ashlesha Patil: from
Ashlesha Patil: this expression here.
Ashlesha Patil: But for that you need to know that the lambda, 2 of this 8 regular graph is
Ashlesha Patil: by root 2 D. Is equal to a 8, so you can write
Ashlesha Patil: B minus by you root. 2 divided by 2
Ashlesha Patil: is point 4, 6, and that's how you get this.
Stefan Krastanov: Just one thing I
Stefan Krastanov: I see the
Stefan Krastanov: I see the nose, the the group we're picking with Z and pro Cn: right?
Ashlesha Patil: Yeah.
Stefan Krastanov: What's the group? Action? The generators were.
Ashlesha Patil: So. Yeah, whenever you write Z, and the generator is one.
Stefan Krastanov: Okay.
Ashlesha Patil: So this essentially becomes like a Torres.
Ashlesha Patil: because
Ashlesha Patil: only Z Cross Z
Ashlesha Patil: is essentially our our square space. but with Z and you from 0 you would come back to N minus one in the opposite way. So it becomes a to.
Ashlesha Patil: So
Ashlesha Patil: now. So this is one of the ways in which you can deterministically create a very good expander graph.
Ashlesha Patil: Now moving on to the error Correction part.
Stefan Krastanov: So that's that's one of the first ways. It was a very big deal that there is a deterministic way to do it.
Stefan Krastanov: but over the last
Stefan Krastanov: 40 years
Stefan Krastanov: there has been a lot of work on the more sophisticated deterministic.
Stefan Krastanov: the waste to generate the
Stefan Krastanov: sorry to generate the A lot of them are based on the Kaylee graph construction simply because we have so much
Stefan Krastanov: machinery already available. You get to really exploit here
Stefan Krastanov: back to your decision.
Ashlesha Patil: So for the
Ashlesha Patil: and a collection part. Let's consider
Ashlesha Patil: and expanded growth.
Ashlesha Patil: but now we divide it's
Ashlesha Patil: vertices into 2 brooks
Ashlesha Patil: on the left and the and on the right, so on your left you have the variable notes, and on the right you have the check notes. So
Ashlesha Patil: think of it as a tanner graph, but we have not drawn the square it no one we have just drawn the circle.
Ashlesha Patil: So
Ashlesha Patil: now for this graph, let's define the first property or the first concept call a unique neighbor. So let's say we have
Ashlesha Patil: a set S. In Vl.
Ashlesha Patil: Then we say that
Ashlesha Patil: a vertex V in VR. Is a unique neighbor of S.
Ashlesha Patil: If there is exactly one edge going from
Ashlesha Patil: S 3.
Ashlesha Patil: Okay. Now. the next thing we define is the left with vertex expansion tissue. So we saw expansion ratio to be just
Ashlesha Patil: the ratio of
Ashlesha Patil: the boundary of S over S. But now we'll define it only for the left vertices.
Ashlesha Patil: and we add an additional constraint
Ashlesha Patil: to this. So the left vertex expansion, ratio L.
Ashlesha Patil: Of G and B is the
Ashlesha Patil: minimum of this expansion ratio over all sets S.
Ashlesha Patil: Since that
Ashlesha Patil: the size of S is less than B
Ashlesha Patil: meaning there are
Ashlesha Patil: at most the
Ashlesha Patil: it must be minus one. What he sees in S.
Ashlesha Patil: Okay.
Ashlesha Patil: Now let's define what I mean by large distance.
Ashlesha Patil: So i'm saying so. The claim I'm making here is.
Ashlesha Patil: if
Ashlesha Patil: L. Of G and D is greater than K. Over 2. Then the distance of this expander code
is
Ashlesha Patil: at least the
Ashlesha Patil: okay
Ashlesha Patil: is the degree of
Ashlesha Patil: all the nodes in
Ashlesha Patil: Vl: so basically this expander
Ashlesha Patil: graph is now K. Left regular. So every vertex in
Ashlesha Patil: Vl. Has degree. K:
Ashlesha Patil: So how do we prove this?
Ashlesha Patil: First, let's
Ashlesha Patil: right down
Ashlesha Patil: the number of edges between S and
Ashlesha Patil: the boundary of S. So they are K. Times number of 46 in. As this is very easy to see, because
Ashlesha Patil: every vertex and S. Has key neighbors.
Ashlesha Patil: then.
Ashlesha Patil: so we know that L is greater than K. Over 2.
Ashlesha Patil: L. Is this ratio here?
Ashlesha Patil: That means this ratio is greater than K. Over 2, so we can write the average node degree to be
Ashlesha Patil: average right node degree, meaning the average degree of notes in VR.
Ashlesha Patil: To be okay times more. S. And divided by the cardinality of the boundary of S.
Ashlesha Patil: And using this inequality here, we can say that the average no degree on the right is less than 2.
Ashlesha Patil: That means at least one vertex in VR. Will have exactly one neighbor in S,
Ashlesha Patil: which means that
Ashlesha Patil: S. Has a unique number.
Ashlesha Patil: and if you write
Ashlesha Patil: a code word Oh.
Ashlesha Patil: then it won't satisfy the parity check.
Ashlesha Patil: because the sound would. It would sum to one so s can't be a code word. and the size of the s was
Ashlesha Patil: so. This was true for
Ashlesha Patil: MoD as less than d.
Ashlesha Patil: so the size of s
Ashlesha Patil: needs to be greater than or equal to D, which is your quote, distance.
Ashlesha Patil: Are there any questions here
Stefan Krastanov: is as can be a code. Could you elaborate on this cannot be. All the word
Stefan Krastanov: is the cold war needs to be
Stefan Krastanov: do I is.
Stefan Krastanov: is is can be a cold. We're making this mean that the bit stream for which
Stefan Krastanov: the this corresponding to S. Or said to one cannot be a global does that what it means?
Ashlesha Patil: Yes, yeah.
Stefan Krastanov: okay. Sorry. I was going to shield, because S. Is not all this. So I wasn't spread to No.
Ashlesha Patil: Yes, I am talking about the bits corresponding to S in here.
Ashlesha Patil: So basically the claim is, if you have a set
Ashlesha Patil: S. And if you have
Ashlesha Patil: even number of.
Ashlesha Patil: if it if it has unique neighbors. that's our number of edges going to VR.
Ashlesha Patil: Then it's not a cold one because you won't satisfy the parity check condition.
Stefan Krastanov: I
Stefan Krastanov: Okay. I understand
Stefan Krastanov: the the way it's response to a bit string is
Ashlesha Patil: all the
Ashlesha Patil: Then the Next came the paper that came up with this construction made was the code corresponding to graph. G. Can be efficiently decoded, and
Ashlesha Patil: they had a very 9 scheme which can be
Ashlesha Patil: thought of as a generalization of belief propagation.
Ashlesha Patil: I'll go to them
Ashlesha Patil: So it says that
Ashlesha Patil: so basically this scheme is
as long as there exist a variable
Ashlesha Patil: such that most of its checks are not satisfied. Then we flip that variable.
Ashlesha Patil: and you keep doing that
Ashlesha Patil: I effectively. As long as the received code word
Ashlesha Patil: is
Ashlesha Patil: so the distance of the received code word. so the sorry the distance of the received bit string from the code word is at most d over 2, which is your
Ashlesha Patil: which is the number of errors you can correct.
Ashlesha Patil: And
Ashlesha Patil: I so yeah, that's it.
Ashlesha Patil: It was a very short presentation.
Stefan Krastanov: Thank you.
Stefan Krastanov: I know. Zoom Variable gets off the sound of we're. We're we're we're weing right now. So questions for all presentations.
Stefan Krastanov: One sort of trying to touch whether
and then
Stefan Krastanov: in the last
Stefan Krastanov: to
Stefan Krastanov: to me.
Stefan Krastanov: to be fair, that was an example that was specifically to show that one of the many problems after that seem to be connected can be solved with the expanding events. It's not necessary that
Stefan Krastanov: basically the presentation started with 3 seeming completion and completely and related problems that all of them, and from being solved by this 3
Stefan Krastanov: surprising family of us.
Stefan Krastanov: And the second presentation was just one of the problems. Okay, the the problem of fair operation.
Stefan Krastanov: Good night.
Stefan Krastanov: I was just like.
Stefan Krastanov: because in this graph there's just 2 sets of inputs it out, like all the notes are either.
Stefan Krastanov: Yeah. The other one was more about the question of
Stefan Krastanov: population where you kind of need the information for one day to
Stefan Krastanov: well, the face of one gate to be transferred to other gates within our system, if you want to.
Stefan Krastanov: Yeah. Well. a small set of gates.
Stefan Krastanov: if they sorry, I think.
Stefan Krastanov: Wow! Here we just have
to be
Stefan Krastanov: well connected. but sparse
Stefan Krastanov: and well. The first part representation was just about having these graphs
Stefan Krastanov: anything else.
Matheus Guedes de Andrade: Stefan. I had a question
Matheus Guedes de Andrade: move forward in the chat, but I didn't couldn't hear if it was addressed or not.
Matheus Guedes de Andrade: He was. and the first presentation. Sorry I cannot hear you
Matheus Guedes de Andrade: sorry, just your
Matheus Guedes de Andrade: In the first presentation there was a slide saying about the properties that we would like to see in the expenditure graphs. and there is something related to the convergence of random walks.
Matheus Guedes de Andrade: and my question was, If it means that you want graphs with short diameter.
Stefan Krastanov: So
Stefan Krastanov: for rap with the short diameter.
Matheus Guedes de Andrade: Diameter is the largest.
Matheus Guedes de Andrade: shortest distance distance in the graph.
Stefan Krastanov: so the graphs will naturally have
Stefan Krastanov: a small damage, or because there
Stefan Krastanov: sparse but well connected. So the
Stefan Krastanov: or diameter. But you're still sparse.
Matheus Guedes de Andrade: I see. Yeah, I see.
Matheus Guedes de Andrade: like the what is it? A small world model?
Matheus Guedes de Andrade: She been straw, that sort of graph similar to a small world, I see. Yeah.
Ashlesha Patil: So actually, I'm considering using expander graphs for the routing protocols because of this property, their hop distances.
Ashlesha Patil: Hello.
Matheus Guedes de Andrade: Yeah.
Stefan Krastanov: Example. With the
Stefan Krastanov: Metro stations we have a issue with
Stefan Krastanov: Metro stations. We can also actually pull down expander graph connectors between subway stations.
Stefan Krastanov: because there are 2 dimension.
Stefan Krastanov: And if you restrict yourself to a two-dimensional connectivity.
Stefan Krastanov: it becomes a little bit more difficult to create an expander. Graph. The expander graph frequently cast a much more higher dimensional topology.
Stefan Krastanov: That's kind of why the
Stefan Krastanov: the to.
Stefan Krastanov: And so, having these constraints of
Stefan Krastanov: for rate because the Tory calls is cast this two-dimensional connectivity in it.
Stefan Krastanov: It's not the one to one person to be careful with, to not over analyze the
Stefan Krastanov: can work out what i'm making. But the the two-dimensional story called
Stefan Krastanov: It's not like the tanner graph that you mentioned.
Stefan Krastanov: Okay, anyway.
Stefan Krastanov: But you made an argument a couple of weeks ago.
Stefan Krastanov: So, projecting these multi-dimensional networks on to the nearest neighbor to dimensional so sure the graph can always be written down on a on a piece of paper. But the edges will be crossing each other
Stefan Krastanov: when I say 2 2 dimensional, I mean nearest neighbor to the machine.
Stefan Krastanov: Any other questions we should be discussing.
Stefan Krastanov: Then, I guess. Let's adjourn for today. I'll be sending out requests for volunteers tonight, and if there are no volunteers, are we just the signing people? Tomorrow we have a few days left a few later days left. So those are new projects.
Stefan Krastanov: Probably that will be happening during 2 weeks presentations on those topics.
Stefan Krastanov: And
Stefan Krastanov: yeah, next week probably will be focusing on Decoders particular improvements of the
Stefan Krastanov: I.
Ashlesha Patil: Thanks.