[0:00:00] Michael and I worked on. It was Fast Laplacian Solvers. So that project was masterminded by Richard Pank, who actually introduced Michael and me in an academic context. We've met a couple of times before at Facebook and at various programming competitions, but this is the first time we actually got to talk and work over a longer period of time.
[0:00:31] The project was about trying to just take the current fastest application solver, which was at the time due to and try to make it faster. Richard had a pretty clear vision of how to do it, even over a year before we actually got the result.
[0:01:04] And it was divided into two parts where we had to work on sub-combinational properties of graphs, and we had to work on linear algebra optimization. And that was Michael's last year of undergrad at MIT. So he was actually, I think he started working on it a bit before the summer, before his last year of undergrad. And for me, it was right about the start of my PhD at Carnegie Mellon.
[0:01:34] So we started talking while I was still in Poland, and we collaborated remotely on faster load search spanning trees, which were a tool we use for application solvers. And we got a result there, together with Gary Miller and Chen-Zhen Xu and Richard. And then we spent some time
[0:02:08] Working on this problem and looking forward at CMU where Michael was visiting Gary for the summer. Actually, I remember Michael's office at CMU. So he was given an office for visiting academics and it wasn't a very nice office. It was sort of this
[0:02:40] Small thing with no windows. But Michael really found one very nice property of it. So he was very happy with the office. So now that Michael really thrived when talking to people, he really found that stimulating and enjoyed it very much. And he really liked talking to Gary. They really had an amazing connection. And the problem was,
[0:03:12] And Michael's office was on the sixth floor and Gary's office was on the eighth floor. And so it was problematic to see if Gary was around. But actually, there was a big open space in CMU. So let me have a picture. So Gary's door were here. There was a balcony here. And then there was this painfully long staircase here and an open space here. So essentially,
[0:03:47] If you wanted to see if Gary was in, you could just see whether his door was open because Gary always keeps his door open when he's in the office. But the problem was you couldn't really do this from this open area here, right? Because you would stand here and you would not be able to see whether the door was open. So Michael's office was here. So I saw multiple times Michael get out the key and walk into his office and walk right back to his desk.
[0:04:26] Where he could easily see from his chair whether Gary was in. I found it really funny. Yeah, so let me say a bit about the problem we worked on. So I won't talk too much about the whole problem. I will tell only about the issue that really took us, I would say, all the time after we have, or at least on the second part of the paper that we worked on together with Richard, Rasmus, and Anuprao.
[0:05:04] So the basic approach for the problem was to solve linear systems on graphs using preconditioned iteration, with the preconditioner being a sparsified version of the graph. So the basic idea would be you would have your current solution x,
[0:05:41] Replace it with, so this is essentially, so if H was identity, so if you had a simple, if you use no-predicature, that would be just gradient descent, and here it's just gradient descent with, on H in your cell, which we hope to be well-conditioned. So if you, so the typical way to,
[0:07:03] Proving these things work is you take the... So let's say you're looking for the optimal solution X dash. So you'll typically be bounding the distance between your current solution and X dash in L norm. And if you know that the condition number of H relative to L is actually low, so you actually have a good preconditioner in the classical sense,
[0:07:38] Then this is actually very easy to prove. You just write this out, and you will get some terms that look like, that will say that sort of your next, so let's say this is i plus one, or maybe t plus one. That will say that your next distance looks somewhat like the previous one, minus, and now you will get some terms,
[0:08:34] Let's look at H inverse. So the bulk of your reduction will be here. You will get something like, and then you'll get a similar term, and you'll get one over here, plus alpha squared times, a similar term with H inverse, LH inverse. I won't do the full computation here. But essentially, if you know that H and L are close, then these terms,
[0:09:25] Are pretty easy to bound. Also, the way we actually obtain this sparsifier H in previous algorithms is we take a low-stretch spanning tree of the graph, which is essentially a graph that has the property that any, well, let's say any remaining edge of the tree has low stretch with respect to it.
[0:10:00] Then we sample a bunch of additional edges and add them to that preconditioner. So then if you sample enough edges through matrix contrastation bounds, it's pretty easy to show that H is actually spectrally close to L and these things become very easy to bound. So Richard's idea was that maybe because of the way we construct this preconditioner, we don't actually need to sample
[0:10:31] As many edges as to be able to say that these things are spectrally close, maybe what we should be looking at instead is just looking at this expression directly and just look at when it decreases in expectation. Because if the right-hand side or if this distance is just smaller in expectation by a constant factor, then we know we're going to solve the problem quickly regardless of it being true always.
[0:11:03] And so Richard put Michael, Rasmus, Anup, and me on a quest of trying to figure out how to bound these terms. So actually the bounds for H inverse itself, just proving that. So what you'd like to prove actually is you'd like to prove that if you sample H by taking a loss-rate spanning tree and adding a match of edges to it,
[0:11:36] Then for any vector, it will be true that it's somewhat close to, and you'd like to prove that this extra part, which is H inverse LH, is not too large. If you obtain bounds of this sort, then you can set Alpha appropriately and you're going to know you're making progress. So this is actually not that hard to show. So actually, Richard gave a proof of this himself for some particular sampling scheme.
[0:12:35] And so what most of our attention focused on was proving this bound for the second order term. And it was something I worked on for quite a few months, and it was hard. It was actually one of the first problems I worked on in academia, and it was sort of the first problem I really got to grind my teeth on.
[0:13:09] And we had a bunch of these attempts based on writing it out and trying to put different inequalities in different places, and maybe something will stick. And it was really proving out to be quite hard. And Michael, who we collaborated with on the construction of search mining trees before, he started his first
[0:13:41] It's his last year of undergrad at MIT. He, I think, took a break from this problem for a month or two and then came back. And first of all, he was sort of unhappy with the proofs we had for this. So he didn't really start out thinking about bounding the second-order term, which was not obvious to anyone. But he really wanted to understand
[0:14:11] These things. So the proofs we had were sort of ad hoc and combinatorial. And she really wanted to get a good understanding of why we can really expect the inverse of this funny sample sparsifier to be similar on any vector to the original graph. And so the notation we would typically use then is
[0:14:47] If you're only worried about proving these problems, you can just assume that L is identity, which will simplify things quite a bit. So then really what our problem is is we have a bunch of vectors that sum to identity. So these will correspond to edges in our graph.
[0:15:52] Stretch less than epsilon with respect to T, which is a spanning tree, but we don't really care. The tree here is just some matrix. And what we want to prove is that if we take T and then we, and let's say there is, they go from one to M. What we want to prove is that if we take the tree T and we add random edges,
[0:16:25] From here, we really only have to add a constant factor of them in order to get a good approximation here, which will allow us to recurse. So Michael started out thinking about how to really get to the bottom of this inequality, so trying to understand what happens when you move the first order inverse.
[0:17:16] Let's say we have some sample H i that is obtained after sampling i of these edges. So we sample them just e. Let's say it's actually always equal to Epsilon for simplicity. So we sample these edges uniformly with replacement. We have some H i and then we wonder, how will the expression v transpose H i inverse v change after we add one additional edge to H i?
[0:17:49] OK, so first, like I said, is imagine instead of adding the actual edge to hi, we add the expectation of what we would add. So the expectation of what we would add is just 1 over m times identity, because we have m edges that sum to identity. So then proving a bound for this, proving that this is actually smaller than hi is quite simple.
[0:18:26] And we can actually show that this is, yes. So this should be less than one over V transpose HI inverse V. And here we'll just have, right, okay. Ah, yes. So then we'll have plus M, I believe.
[0:20:23] Minus... I'm getting lost a little bit since I'm looking at... I'm giving the proof from the unrefined original Michael node from the date of invention, which was refined many, many times afterwards. But I really think the idea he had there was very nice and yields some insight into how he came up with the solution. Anyway, there is a lot of inverses here. Okay, but anyway...
[0:21:17] I'm sure you can believe me, this is not a very hard expression to bound. What is interesting is, and what really was, in Michael Wurst himself, was the key idea to his solution is that, so this is what will happen if you add the full edge. And here the idea was saying, well, what happens if instead of adding a full edge, I just add a
[0:21:49] I just think of adding it continuously, right? So I start with my sparsifier and then I add, instead of adding at the edge at once, I add it linearly. So he defines the function f of x where x goes from zero to one as this. So yeah, at f of one, we know we'll actually, we have made some progress with regards to our original sparsifier. And the idea is that
[0:22:25] This function f of x is actually convex with regards to x. So it has an increasing derivative, which actually means that because we can bound this expression for x equals to 1, we can bound the derivative of x at 0. So we can actually say that f prime of 0 is at most f of 1 minus f of 0.
[0:23:02] Right, and actually, okay. So f of one, the expression I was missing is actually the harmonic sum. So there Michael coined of the previous score and one over m, and harmonic sum is just the inverse of the sum of inverses. So this is, and now, okay. And now, the very nice part is,
[0:24:16] So this is the derivative of adding the entire graph to our current graph. But actually, this derivative is equal to the sum of derivatives of what would happen if I took a random edge and added it to my current sparsifier. So if instead of i in this expression, I had only some single edge, and I tried to add that,
[0:24:52] I tried to add that and then look at how this V transpose sparsifier inverse V changes. If I'm only looking at the derivative at zero, I can actually say that this derivative is the sum of those derivatives, which is actually very nice because if you try to look at these terms directly, so after you take a discrete step,
[0:25:23] It's pretty hard to say something interesting. So then we can actually get a bound on H inverse based on that. But there is one very beautiful consequence of this more principled way of looking at
[0:26:10] at this problem. And that is that this f prime of 0 that we are looking at, if you actually compute its value, it's going to be roughly 1 over m times v transpose h to minus 2 v. And so we have proved that this thing is
[0:26:44] That this thing is not too large. And we actually know that because this function is convex, we know that if we sum the values of f prime of zero as we go with h i over a large period, we know that the sum of all these derivatives is bounded by the total progress that we made. And so we can actually
[0:27:16] We can actually use this fact to get a bound on the second moment of our sparsifier. I think that's really cool how Michael's desire to just understand the first part, the first order approximation of a sparsifier has led to just solving the whole problem.
[0:27:51] And if there is any extra time, I might add a conjecture that we worked on with Michael for a lot of the time that we were together at CMU and later, and we have never really solved, but Michael was very excited about it at some time. And that conjecture is the existence of a spectrally supported spanning trees with
[0:28:30] Constant tall stretch. So actually, the question, so, okay, I don't have extra time, but, okay. Okay, well, okay. Sorry. What is this conjecture that Michael was saying? I use this trick as well. Yeah, so, thank you. So the conjecture is, so we now drew to Abraham and Naaman that if you have a graph, you can find a low stretch spanning tree.
[0:29:21] We have total stretch of m log n log log n. And now it turns out that if you, so the directory has a fairly certain property in that it's actually a subgraph of the graph. So instead you might only want the tree to be, to be spectrally supported by the graph. So just spectrally less than the graph as a matrix. So if you want that, it's immediately, not too hard to just
[0:29:50] You can just apply any sparsification algorithm, sparsify the graph first, and you can get a tree with total stretch say n log n log n. Let's say you can actually use Steiner vertices, and you can actually prove that you will need Steiner vertices for the full conjecture. So let's say we only want a graph that is specularly supported by our graph, and it can have more vertices. We just want to be able to sure complement them out.
[0:30:17] In order to get a graph that speculates less than our graph. And let's say we want a tree like that. It's very easy to show you can get that tree to have stretch n log n. And the conjecture is that you can get always, that there always exists such a tree of total stretch n of all of them. So we had this nice thing going on for a month or two where we would come up with examples and then mostly Michael would try to
[0:30:48] Find a way of constructing trees for that particular family of graphs. It's a very entertaining source of puzzles. You can come up with all sorts of weird graphs. Yeah. So the conjecture is still unresolved. Are you willing to bet on one of the outcomes? I think if he would bet, he would bet that they exist. But he didn't bet. But I mean, I also believe that they exist. So maybe we didn't find anyone.
[0:31:18] So there's a reception outside, so you can just chat there.