All-Pairs Min-Cut vs. All-Pairs Shortest-Path - Amir Abboud

What is discussed, and when

1. 0:00 – 10:00: Max Flow, Shortest Path, Graph
2. 10:00 – 20:00: Max Flow, Shortest Path, Jason Lee
3. 20:00 – 30:00: Max Flow, Graph, Shortest Path, Expander Decomposition
4. 30:00 – 40:00: Max Flow, Expander Decomposition
5. 40:00 – 50:00: Matrix Multiplication, Max Flow, Shortest Path, Boolean Matrix Multiplication
6. 50:00 – 1:00:00: The BSG Theorem, Additive Combinatorics, K Click, Triangle Detection

Notable quotes from "All-Pairs Min-Cut vs. All-Pairs Shortest-Path - Amir Abboud"

• So these are very basic graph parameters. You know you have a graph and the these two parameters or problems or functions they ask two different things. So in both cases you have a.

  about Graph · at 1:03

• So for short path we have dra algorithm very classical it's a very simple algorithm and it solve it very fast. M is if M is the number of edges, N is the number of nodes, it's essentially linear.

  about Shortest Path · at 2:23

• Differences. So you can notice that when you run dystra, you don't only get the distance from S to T. You run it from S and you get the distance to all the nodes, you get this…

  about Dijkstra · at 4:49

• The output I want you to give what is the complexity of this problem And so for shortest paths we can just run destroy every source and we get this n times the extra complexity…

  about All Pairs Shortest Path · at 6:05

• Actually happened so we solved the general weighted case also in quadratic this is with Jason Lee de Malia panigra and such a false finding the grammar with three yes so the…

  about Jason Lee · at 18:24

• Source problem. You have your source and so you compute an expander decomposition of your graph. An expander de composition is a de composition of the graph into such that…

  about Expander Decomposition · at 35:33

• Weighted. But this is actually how you solve the unweed APS. I said you can solve it with fast matrix multiplication and enter to the omega. So this is how you actually how you…

  about Matrix Multiplication · at 46:04

• And so we use the BSG theorem famous theorem from commentorics. Nick needs in addition to use conjectures the something called PFR conjecture the polinomial frame ruia.

  about The BSG Theorem · at 57:54

Who and what is mentioned in this episode?

People

• Gomory — Person · Referenced expert · 3 mentions
  Credited for the 1961 result (Gomory–Hu) showing all-pairs min-cut values can be represented by a cut-equivalent tree, foundational to the episode’s max-flow discussion.
• Dijkstra — Person · Referenced expert · 2 mentions
  Referenced via Dijkstra’s algorithm as the canonical fast method for shortest paths, used as a baseline comparison against max-flow/min-cut complexity.
• Jason Lee — Person · Referenced collaborator · 1 mention · first at 18:31
  Named as a coauthor on the later quadratic-time weighted all-pairs max-flow / Gomory–Hu tree result discussed in the talk.
• Albert Einstein — Person · Referenced historical figure · 2 mentions
  Not substantively integrated into the technical narrative in the provided excerpt; likely a passing reference elsewhere in the episode or an extraction artifact.

Concepts & topics

• Graph — Concept · Core topic · 3 mentions · first at 1:05
  Fundamental concept discussed in the context of algorithms and computational complexity
• Max Flow — Concept · Core topic · 20 mentions · first at 0:57
  Key problem in graph theory discussed in relation to shortest path and computational complexity
  And this is one problem. The other problem is the minimum cut or the max flow. So the max flow is you're trying to push the maximum amount of flow from S to T while respecting…
• Shortest Path — Concept · Core topic · 8 mentions · first at 1:20
  Fundamental problem in graph theory compared to max flow in terms of computational complexity
• All Pairs Shortest Path — Concept · Core topic · 5 mentions
  Generalization of the shortest path problem discussed in the context of computational complexity
• Matrix Multiplication — Concept · Referenced concept · 4 mentions · first at 46:08
  Discussed in the context of solving graph problems and computational complexity
• Expander Decomposition — Concept · Referenced concept · 2 mentions · first at 23:56
  Mentioned as a technique for structural analysis in graph algorithms
• The BSG Theorem — Concept · Referenced concept · 2 mentions · first at 57:59
  Mentioned in the context of additive combinatorics and its application to solving problems
• Steiner Tree Packing — Concept · Referenced concept · 1 mention · first at 41:33
  Mentioned as a technique used in weighted graph problems
  Then it helps us get to this poly log call to this isolating cuts thing which then reduces the poly log max flow. For the weighted we couldn't break the cubic barrier at all…
• Boolean Matrix Multiplication — Concept · Referenced concept · 1 mention · first at 46:13
  Mentioned in the context of solving graph problems and computational complexity
  Solve it with fast matrix multiplication and enter to the omega. So this is how you actually how you do it. So you go from unwrae APS to boolean matrix multiplication where you…
• Additive Combinatorics — Concept · Referenced concept · 1 mention · first at 57:47
  Mentioned in the context of solving problems with small distinct weights
  Weights are from this interval of 1 to n. That's all you have to do to solve it. And both of these results are using additive combinatorics which is be my last slide.
• Polynomial Frame Ruia Conjecture — Concept · Referenced concept · 2 mentions
  Mentioned in the context of additive combinatorics and its application to solving problems
  And so we use the BSG theorem famous theorem from commentorics. Nick needs in addition to use conjectures the something called PFR conjecture the polinomial frame ruia conjecture. So his result is it equivalence is conditional on some.
• Triangle Detection — Concept · Referenced concept · 1 mention · first at 54:04
  Mentioned in the context of graph problems and computational complexity
  With new notions and one thing I wanted to say so there's these stronger versions of APS this the same happens with the boo triangle detection you can think of like the k click…
• K Click — Concept · Referenced concept · 1 mention · first at 54:07
  Mentioned in the context of graph problems and computational complexity
  With new notions and one thing I wanted to say so there's these stronger versions of APS this the same happens with the boo triangle detection you can think of like the k click…

Places & events

• AWS re:Invent — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a tech conference
• CES — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a tech conference
• Coachella — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a music festival
• COVID-19 pandemic — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a significant global event
• Nobel Prize — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a prestigious event
• Olympics — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a major sporting event
• Oscars — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a prestigious award event
• Super Bowl — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a major sporting event
• SXSW — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a conference or festival
• Ted Talks — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a speaking event
• The Burning Man — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a festival or cultural event
• World Cup — Event · Referenced event · 3 mentions
  Mentioned in passing, likely as an example of a major sporting event

Full transcript with timestamps

0:14 Okay. And yeah, very happy to start with Ben. We have a double feature today. Uh starting with air who will tell us about some exciting work and then we will have all after break. Oh, we will decide.

0:30 Okay. All right. Thank you. Okay. Hello everyone. Thanks for walking in the call to come to my talk. I appreciate it. Um, so I want to talk about this uh very simple question. I have two problems we really like. Uh what is the relationship between them? What's easier or harder? So two problems are shortest pass and connectivity. So connectivity I mean like minimum cut or maximum flow. It's the same thing uh for me. And I'll use min cut or max flow interchangeably throughout the talk. Um so these are very very basic uh graph parameters. You know you have a graph and um the these two uh parameters or problems or functions they ask two different things. So in both cases you have a graph and you have a source and a target s. In shortest path, you're trying to go from S to T while walking on the cheapest path. You know that you want to choose edges, a path that's made up of the cheapest total sum of edges. So in

1:34 this example, it's like 60. And uh this is one problem. The other problem is the minimum cut or the max flow. So the the max flow is you're trying to push the maximum amount of flow from S to T while respecting the edge capacities. uh but it's equivalent to the min cut which may be easier to think about where all you have to do is you have to separate s from t by deleting the minimum total number of edges and this is the same graph the the flow is is okay so these are two very basic problems you see them in a basic algorithms course and you may wonder which one which of the two is harder to to compute and I I'll be talking in the standard model of computation weights are integers and so on.

2:23 So for short path we have dra algorithm very classical it's a very simple algorithm and it solve it very fast. M is if M is the number of edges, N is the number of nodes, it's essentially linear time and so it's so so good. It's kind of easy and simple for max flow or B cut things are more complicated and it took much longer uh for us to get to such good algorithms. So even just getting some polomial time algorithm uh took many more years and uh so it was good and there were some more improvements to that algorithm and then in the last two decades or so there was these methods from continuous optimization solvers and things like that got the complexity down

3:16 this approxim even for exact so you can use them also to get exact and even so when I started my PhD started think about these problems these people would I would meet them at conferences and they would tell me oh it's going to be linear time it's just a matter of you know analyzing it the right way and so on so the these techniques were clearly powerful enough to get us all the way to linear time and this actually happened in remarkable breakthroughs uh recently so this result gives uh almost linear So if we ignore so throughout the talk I'm going to be mostly ignoring these sub polinomial factors. I'm only going to care about the polinomials and uh also I'm just going to drop m and just analyze things in terms of n. So both of these things are like n² m could be up to n square. So both both of these things are like um easy problems like essentially linear time solvable problems. But of course

4:17 this is much much simpler right this lecture is very very simple very easy this is you know a very complicated paper building on a lot of 100 pages of hundreds of pages of work okay but to summarize what I said so far if you look at these two problems and you're in this uh what we can call the single pair setting where you want to know the answer for single pair S&T they're both at the same complexity but if you think about maybe more general problems, you can start seeing differences. So you can notice that when you run dystra, you don't only get the the distance from S to T. You run it from S and you get the distance to all the nodes, you get this shortest path tree. So at the same time, you also solve the single source problem where you have S and you want to know the distance to all other T's in the graph.

5:08 And this is the difference between the two problems because these algorithms, these very complicated algorithms, they don't give you that. If you wanted to know the single source information, you would have had to run them once for every target. So you can run them um by choosing, you know, s t1, t2 up to tn, and you'll get this information, but it's going to cost you an n additional n factor. And so let's look at the the kind of most general problem in the studing, the all pairs problem, which will be the main focus of our investigation.

5:42 So in this all pair problems you get one graph you don't get S&T and you need to output for every pair what is the distance or for every pair what is the minimum cut or maximum so you just have to output the values you don't have to output the path itself or the flow itself that would be expensive just output the you know the value of the flow or the path uh so the output size is this n squ numbers that the output I want you to give what is the complexity of this problem And so for shortest paths we can just run destroy every source and we get this n times the extra complexity which is n cubed. And again this is a very simple kind and a very very classical algorithm for all pairs max flow you can still do the naive thing of for every st run the single pair algorithm and now you'd have n squ additional overhead and that's n to the 4 but then in 61 1961 there's a remarkable paper by go which solved this old pair

6:48 problem for mata max flow in a better time in a time that's n factor times the single pair as opposed to n square which if you plug in the what we know now for the single pair you get n cubed as well. So let me spend one slide telling you about this gmor result because um you know it's it's a kind of show that this old pair max flow problem is like fundamental beyond just being like a basic problem we we like to think about. Um so what go showed is this fundamental fact about graphs that says that you can take any graph any undirected graph even weighted and you can turn it into what's called a cut equivalent tree. So what that means is there is a tree t on the same set of vertices but it's a tree so it's a much simpler graph. Uh it has weights that could be different from the original weights and it has a very strong property. It's a it's a cut equivalent tree. So what that means is for any pair of nodes S&P if

7:52 you want to know the cut in the graph you can look at this same pair in the tree compute the minimum cut in the tree. the same cut that you got you look at it in the graph it would correspond to a minimum cut between them. So it's like an exact uh reduction. There's no loss. It's like it's like a graph spification and simplification result maybe the first in kind of the literature um which now has become like a whole industry of of things. But this is like exact there's no loss and it works for every pair at the same time

8:27 right and uh importantly for us they also gave an algorithm like the the proof of existence was algorithmic and it showed that you can compute it by making a a call to a st minimum cut algorithm n minus one times I'll show this algorithm later in the talk but yeah so if you had the tree Then the old pairs Mac flow problem would be easy. I mean all you have to do is solve it in a tree. Minimum cut in a tree. You just seem to find the cheapest edge on a path. It you can then solve it in n square time. Like it's some easy exercise. But the main thing for us is you know how do we get the tree? How fast can we compute the tree? They gave this algorithm that's n times max flow.

9:11 And since their work it has been open question to get anything better. So can you reduce the number of queries below n and there was no progress on this since then. Uh meanwhile if you go back to the shortest path setting where we had this n cubed algorithm and also people have tried to improve it um a lot and there was some progress. So they were sh log factor shaving results and even there was a result by Ryan shaving a super log factor and so it's still at n cubed like the polinomial but you know it looked like there was something happening here maybe this was going to break or something but nothing was happening for max. So the bottom line is is that you know they're both at n cubed but shortest path seems easier.

10:07 And this is basically what I all I've said so far. So we have these two problems. Max flow sorry the all pairs they're both at n cubed. And our feeling was that it max flow should you know if we if one of them okay the question was which one is harder. Our feeling was that max flow is harder and let me give you two more reasons to think that way. You thought so one reason is if you look at the unweighted graphs so you just remove the weights all weights are one what happens uh for short pass you can use fast matric multiplication and you break the n cubed result so there's this classical n to the omega algorithm whereas for max flow we didn't know anything you couldn't beat the lumeric result so that's one reason so for this kind of fundamental setting there's a kind of separation and if you look at directed graphs another interesting setting um for juris everything still works direct still

11:11 works so you still get n cubed but uh for max flow this go result fails so directed cuts are just much more complicated than undirected you can prove that there isn't such a thing as a go tree so the best we know is n to the four which is much higher than the shortest perspective. So like these two kind of settings we do have separations. Uh so yeah, this is just some reasons to think that max flow is harder. So that's where where we're at. We feel like max flow is harder. Can we can we prove it? And this is where fine grain complexity comes in which is uh this kind of uh literature where we take problems fundamental problems and we try to find connections between them and whereas kind of before we had this all these nice problems polinomial time solvable problems we didn't know which was harder which was easier um and but we've developed a lot of reductions that let us draw a nicer picture that gives us

12:16 some kind of understanding where there's some core problems that um maybe a lot of people have thought about and there's famous conjecture saying that for those problems we have reached the right bounds and then you can reduce these core problems to dozens of other problems and explain their bounds and showing that for all these other problems you cannot prove them you cannot solve them faster unless you break these famous conjectures And importantly for us all pair shortest path is one of these core problems for which there's a conjecture. So the conjecture says that you cannot beat the cubic bound for APS and under this conjecture there are reductions and conditional or bounds for a lot of basic graph problems even very very simple ones. Um but notably or b max flow is not in this list and it was very natural for us to try to put it in the list. Yeah, it's notable that a that this conjecture is

13:25 equivalent to the version for directed graphs too which you know which also might indicate that like this is different from all

13:34 right so the directed cases are actually equivalent not only does work but they're literally equivalent

13:46 yeah but probably not for Max. So, so that Yeah. So, we had this class, you know, open max flow was not classified. We really tried hard to to do it. It was something I thought about very from a very long time ago and we did have some results. So, we did show what we believe that max flow is harder than shortest paths. But we could only show it for directed graphs which is as I said is not a very interesting setting because uh directed cuts are weird and the whole result doesn't doesn't really apply. So we basically showed that this bound probably cannot be much faster. This is different under the depending on the conjecture and I don't want to go into the details but uh for example there's an nub lower bound under our self.

14:38 Um good. So, so you know we confirmed what we believed but not for the more like the fundamental question we were uh asking about. So let's forget about the recorded graphs and let's go back to the undirected graphs and see what's what we know there. And we didn't know anything. So we didn't have any loads. And here I want to give like conceptual credit to fine complexity. So when I started looking at these things uh this is a list of problem that I thought are very nice problems very fundamental problems that we should really solve and and so on but it was a mess like and I wouldn't you know or operate Mflow was one of them but I wouldn't like spend years and years working on it because you know there's all these other problems I could be working on and why why spend all my time on this one you know maybe I'll fail and so on but then at after I finished my PhD the picture was very different. So for

15:40 my list, so there was these red problems. These are conjecture to be hard problems. You have to be very very brave to work on them. So on all the other problems were grayed out. So there we knew that you cannot solve them faster until you solve a red problem first. So working on the gray problem is also something um that you have to be very very brave for. But then all max flow really stood out as problem where we didn't know. And I did think it was really worth studying at that point. And at that time he was a PhD student of rob programmer came to do internship at at IBM with me. I said let's work on this problem and we've discovered a bunch of results.

16:24 Uh I don't want to go into the details but you know making some kind of progress here and there explaining why we don't have reductions and so on. um until we discovered this result and we were very very happy. We got the first improvement over go marinu. It was only for unweighted graphs but we broke the cubic pound. So we got into 2.5 uh time and then things started accelerating from then on. Uh 6 months later there were three papers on archive uh improving this all the way to n square. So what happened is that this thing dropped from n cube to n squ which is great. It's like a tight algorithm.

17:09 Um and square is like the output side meaning you can optimal is great and for the first time kind of in history this ape max flow became easier than shortest path and and yeah so like what's going on? We were very very confused. Um but then maybe the answer to the confusion was that well you know just like the experts were telling us that max flow will be linear time the experts are also saying omega will be like magic multiplication will be linear time and so maybe this is just n squ and there's no separation both are easy problems uh and that's like that's what it is.

17:50 So then okay if that's true then the real question is for weighted graphs where if you can break this bound then you would get this counter in separation because here like the experts are putting this conjecture like as opposed to this like we don't really know how we don't really believe or we don't have strong reasons to believe that this will be broken. So then if you do break this then you would separate the two problem and and yeah so but a year or two later this actually happened so we solved the the general weighted case also in quadratic this is with Jason Lee de Malia panigra and such a false

18:36 finding the grammar with three yes so the algorithm not only solve the problem but even finds the go tree of a brush. So good. So under the APS conjecture, this is the right thing. Then we got the opposite separation of what we were setting out to to prove that next flow is actually a much easier problem. And so maybe the conclusion is that maybe this not a this conjecture should be uh broken and you know either that you know either you accept this or you try to break the conjecture and this I'm going to spend the the last part of the talk on this uh on this but yeah before I talk about this you know how you might like inspirations from this work to try to break the APS conjecture uh I want to spend a bit more on the max flow result.

19:43 So and just before we get to the technical part uh some follow-up works. So for computing the Bori tree n squ is not the is not uh satisfying you may want to compute it in linear time and this we actually did that too. So you can take a graph has images could be sparse graph in linear time produce the tree almost linear time and then once you have the tree you can just look up the old pairs information. So we don't and the the title of the paper is that the all pairs max flow is not harder than single pair. So it's like a reduction from all pairs to single pair that has just poly logarithmic open.

20:26 That was the first thing we asked. The second thing we asked was uh the randomization. It was randomized and this is uh more recently we got everything to be deterministic as well. And then the third question so these are three questions we asked in that paper. The the last question was whether we can simplify things. So I didn't show you the the technical but it was pretty complicated using a lot of different things and so on. Um and uh these guys Rasmusking, Max Gutenberg and Yuan Yuan they have been working and this is very recent like last week I saw them and Sosa they have been simplifying and a lot of the fancy things that we've used are now not necessary which makes my life easier for the technical part because then I I'm not feeling guilty about not telling you about all these fancy stuff. So I'll just focus on the the things that will actually as they're showing is kind of all you need.

21:22 So good. All right. So the next part is going to be some kind of technical overview. Um it'll be a pretty high level trying to inspire you to think you know to get something from the APM MF results but then inspire you to think about the APS the goal.

21:41 Okay. So I want to you know draw like a high level picture of of what these algorithms is which can say it's a general thing about modern algorithms and how they they work. So there's like three main components. Uh some combinatorial algorithmics, some structural analysis and some heavy tool. And I'm going to say what these things are in the context of max flow and then we'll try to say what they might be for the context of shortest path. So, so the heavy kind of the tool the kind the powerful tool at the end that you use for us for computing all pairs max flow is the single pair algorithm.

22:23 So this is something we use like as a black box at the end what we're doing is a reduction to single pair and this is you know it's a tool that to to actually solve it in linear time you need to use this uh optimization and lesson system solver dynamic data structures and so on. Okay. But like our work is kind of on top of it like on the other things leading us to to this reduction. And so the the first thing that is always there is some kind of combinatory algorithms. Uh we're using things like you know divide and conquer or sampling and and sort of combined to be a linear time. Near linear time.

23:04 Yeah. Yes. At the end of the day for many to single. Yeah. Um it's it's it's a little the overhead is polarithmic overhead. In fact, it's not like we're only going to make poly logarithmic calls. No, we're still going to make end calls, but they will be on smaller instances.

23:26 Yeah, the total time of the thing will be just later. Um okay so you know there's this uh algorithmic stuff and then one thing that's kind of there in mo we might say modern algorithms is some kind of data dependent thing or some kind of structural analysis of the input itself where you know you do something for the input for the graph something like an expander decomposition or or something else that we've used here standard tree packing and it lets you really kind of um it just helps the the algorithmics basically and I'll touch on how that happens. But you can think of this as also as a worst case to average case reduction for your problems. It's like you know you do these things and you wish the graph was random. If it was random you're happy. So then you try to find some way to make it random.

24:27 Okay. And okay. So this these things uh this is like new for the Gmori who I'm going to start with the Gmori algorithm. It was just like basically this and this uh so I'm going to start with that now. Okay. And uh the what I want you to show you is actually a reduction from uh construction to to the single source problem. So like reducing all pairs to single source. This is one of the new things we have we have done which um so it's one of the ideas I want to share with you today. So and then the way I'm going to explain is I'm going to start with Gmoru and say how a single source might help you.

25:10 Okay. So let's go back to 61. This is what the Gmoru algorithm does. You have uh your graph. You want to compute a tree, the Gmoro tree. So you start with you put all the nodes in one super node and you pick an arbitrary pair of nodes S and T. You ask for the minimum cut between them. That's the minimum cut. So you get that this is the the cut and so you use this cut to divide your super node. Okay. So you you know one side of the cut goes here, the other side goes here and you put an edge between them with weight that corresponds to the weight of the cut that you find.

25:51 Okay. And you continue. It's like a divide and conquer thing. You you divided it and then you want to continue recursively on the two sides. But a critical thing is when you when you continue, say let's say you want to continue on S, you have to contract T. It's like a clever thing that happens. So you take T, you contract it into a single node. you adjust like the edge weight and then you do the same thing on the contracting graph. You pick a new pair, arbitrary pair, you find the minimum cut between them in the contracting graph.

26:26 Let's say maybe this is the new cut and you use it to to make progress on S to separate S. The contraction is very important so that the cut that you find doesn't mess up uh the other side. So, so then you really end up with a clean tree structure.

26:45 The partition may not be balanced. It may be the partition may not. Yes, we wish it was balanced. I'll get to in the next slide. But um but the fact that this is correct that this contraction doesn't uh cause you to get suboptimal cuts. This is a what's called the subm modularity of cuts. It's a lema from go. um very important. So that's it. That's the Gummoro algorithm.

27:15 This works for any submod function. Yeah. You always have a tree which Mhm. Yeah.

27:28 Can you say something about it? About what? Like why is it true? Oh, why is it true? Um no it's it's just calculations basically if you if you work on it you can just move this or this would be better kind it's yeah

27:44 just to prove by calculation okay so that's the algorithm how much does it cost what's the time complexity so notice that we're going to keep doing this and you know discovering new edges every time we make a call we discover a new edge so we're going to have n minus one calls at the end We're going the tree has n minus one edges. The number of calls that we're making is n minus one always. But you might hope that you know these graphs are getting smaller and smaller and you're contracting. So so then the you might hope that the total size is is good and uh unfortunately um let me see.

28:27 Yeah, if the gra the cuts were balanced and you were cutting in half and you're contracting and you have this you'd have like a login depth tree and every layer you'd have the linear size total, you'd be very happy and that's kind of where we would like to go. The issue is that this doesn't always happen.

28:44 If your input graph is an expander, can you show that the graph indeed get smaller?

28:49 Great. So, thank you for the question. Uh, actually expanders are actually the worst case here. So, so what is the worst case? The worst case is whenever you you pick a pair the cut that you get is is um t is on one side and everything else is on the other side. So you only reduce the graph by one graph side by one and then you do you pick another pair here and again you just remove one. So the depth would be n and I claim that this goi this is the final gummor. I claim that this is what you get in an expander. And to see this uh imagine you have your graph is an expander.

29:28 This means that if you have a pair of vertices, the the minimum cut between them is just take your degree take your the minimum cut would just be equal to the degree. And this is what you would expect in an expander because if you go kind of further away from you like somewhere in the middle, you know, it's an expander. So there will be a lot of edges crossing. So, so this kind of thing is not a contrived example. It's actually what happens a lot.

29:57 It would be a path rather than self. You remove Yeah, you remove a vertex and you remove it. It's not clear. It will look like

30:10 um a path where the edges are increasing. You don't want to you're saying a graph where every the minimum cuts are actually the degree cuts could be a

30:22 no I feel yeah it doesn't right I mean because as you said an expender is regenerate in the sense that the minimum cut is always

30:35 the degree yeah yeah so you don't make enough progress and as you can observe and expand. For example, even if you pick these pairs at random and so on, it doesn't help you. You're still going to get the degree cuts. So, one idea that underlies a lot of what's going on is that it's like you want to compute not just for a pair, you want to compute a lot of minimum cuts at the same time. And one clean way to do it is with single source cuts. So, you pick a pivot node and you want to compute the minimum cut between them and everybody else. And it's it's a we don't know how to compute this in linear time but suppose we could then everything will just work. You pick the pivot at random. You find these minimum cuts and you can show that with high probability all of these cuts.

31:28 It'll let you kind of recursion to constant fraction of instance sizes. Wait, why is this true for expanders? So for expanders if you pick a node then uh the minimum cut it's so you're the single source minimum cut from that node to everybody it's true you might worry that it's you know that node versus everybody else that's the best cut for everybody else but it might also be that they are on their own and

32:00 so it's like you can pick the the latest cuts if there's a tie But if there was no ties then, you know, for half of the vertices, uh, it's not, you know, it's not I'm on my own. It's not a pivot on its own and everybody else together. It's that they are on their own. And

32:22 I see. So you kind of get one big component and other isolated. Exactly. You get half on one component and then half are isolated and that's that's progress. Mhm.

32:34 Previously your reduction was using a single pair cut right and that is every time you will expand one node into an H.

32:43 So how do you get this structure like how do you go from one node to three parts?

32:49 Uh the yeah if you so I mean if you had these cuts then you would need to adjust the gummoro strategy. Instead of learning one edge at a time you're learning a few edges at a time. You recurse here, you contract everything else. And so it's kind of you you adapt the Gumari algorithm that way. But if you're asking about computationally, this is a big difference. We don't know how to compute this efficiently. For single pair, we knew how to compute it. This uh you have to work hard to compute the single source cuts. Can you say about the reduction like if you have this single source cuts how do you uh go from like one node to uh the outcome of your single source cut

33:38 like what are the three parts we would like this to be the output of the algorithm so I see I didn't define the single source mut problem uh properly but so for the purpose of the talk just assume you get these uh You're saying that you know for each of these nodes there could be like a smaller cut and or no what are the three parts

34:01 the three parts is think of it that uh for these nodes for everybody here this is uh this it's not quite it it could be that for this node there's a smaller cut. So there's like a like a nesting structure of of the cuts. So this cut is the minimum cut for somebody here, but then for others there could be even better cuts.

34:27 So is P a node or a super node? It's a node. It's a random node. It's a random node.

34:34 Okay. Okay. Yeah, it's Yeah, I didn't want to go into these technicalities of how it's defined. You're right that it's a bit subtle. Okay. So that so that was like kind of this part and the sampling and and so on divide and conquer. Uh now I want to explain how this goes into the picture data dependent stuff.

35:05 Yeah. But you still don't know how to compute the single source in linear time. So this will solve this problem.

35:12 Yeah. So how the main thing now is how do you compute the single source main cut? And this is where we're actually going to need some um data dependent thing some kind of uh specifically I'm going to explain how expander decomposition goes into it and helps you. Um so this is why it helps you. So imagine you want to solve the single source uh problem. You have your source and so you compute an expander decomposition of your graph. An expander de composition is a de composition of the graph into such that every component is an expander and there are few edges are left outside and the few and how much of an expander and so on. There's a trade-off here. You you can choose it.

35:55 I'm not going to go into it, but just as a picture, this is what what you have. And then you want to know the the cut from P2 to all the other nodes. And as a wishful thinking, you might hope that these minimum cuts, they will never cut expander. So they will always go like this. So an expander will always be on one side of the cut. And so if that were the case then you know it's easy because then you don't you can treat kind of a contract expander you can for every expander you can only do one query that would be good and of course things are more complicated and um you know it's actually possible that you will cut a small piece of expanders um and this creates a lot of complications and um and we had to deal with this. But this is more like you know algorithmics kind of

36:52 but also the number of expanders in the composition method. Yeah. Yeah. This there's I'm rushing so much here. There's a have to choose the parameters. You might have to do this because it's it's a lot of work and these guys at the source of paper they're trying to make it cleaner and clearer. It's still uh not enough for me to present everything an hour or two but uh but I I just wanted to share this as a a main idea of what's going on. Um yeah, and I'll just quickly flash this. I'm going to skip it for the So I'm running out of time. Um one of the main new algorithmics things.

37:37 Okay. Uh okay. So then I'll I'll share this slide or two. So this is uh one of these algorithmics that was really important and needed for to help you with the case of uh you know cleaning up these kind of pieces and stuff. But it's it turns out to be so useful that now there's like more than 20 30 papers on cut algorithms in the literature that uses this result. They generalize it now to everything hyperraphs all these different models. Uh it's it's a very simple thing that actually very easy to prove from the Gmoro result but somehow it has been very helpful. Um and so let me just say what it is. It's uh it's a result it's a it's a new problem. So the problem now is you get a graph and these terminals say K terminals and you want to compute the minimum isolating cuts. So these are the minimum cuts under the restriction that there's one terminal on on one side of the cut. So you're trying to separate

38:39 one terminal from all the other terminals. This is the cut that you would find. Okay. So it's a kind of like a multi-way cut problem. The cool thing about it is that you can actually compute it. It's not an APR. It's an efficiently computable. You could have computed it in K times max flow by just doing it one for every terminal. you contract all the other terminals and you find compute a minimum cut. That's what you're looking for. But it turns out you can do it with just log k instead of k is just a node, right?

39:11 It's just a node. There's a subset of the nodes that you care about basically. Yeah. Um and uh so the the the super useful thing is that you can do it with log k instead of k. And it's some simple thing where you take half edge each time and you you do it. Um yeah, this and let me just say quickly like at high level why this is useful. Like imagine you sample uh you're worried about a a cut that's like not balanced. So your graph might have a lot of small cuts that you want to compute all at once. If you sample terminals at random and your cut is small, then you're likely to hit only one of them and not not more. So then you compute this once and you kind of find all the small cuts at the same time. Then you only have to worry about the the big cuts and then the expanders somehow are better to to handle those.

40:13 So for example, in in the expander example, you have this situation where every cut is very small. Uh yeah but expander is so easy that yeah but for expanders yes like but expanders it's like okay you have like the guess that you're the degree cuts are like your first guess and they're correct for expanders but sometimes you have these graphs where you have you every three need to be together and then like how do you efficiently find your friends like

40:43 okay who would be the terminals in that case just pick everyone at random with probability like one over three

40:49 okay so one of the three would chosen and you will find all the triples in one column.

41:00 Okay. So the high level of our algorithm is like this. So you want to compute the gumor tree. You do this reduction to single source main cuts. Then you do the structure analysis and for the unweighted case we just use expander decompositions. It's pretty simple. And then it helps us get to this poly log call to this isolating cuts thing which then reduces the poly log max flow. For the weighted we couldn't break the cubic barrier at all with just expanders. We had to introduce a new kind of graph thing which is based on Steiner tree packing. It's very fancy, very nice. It generalizes carers work on tree packings. Uh those SOSA papers are showing that this is not really necessary. They can do everything with the pender. So I'm not feeling guilty about not telling you about all that stuff. You still need it to get all the way to linear time currently.

41:57 Okay. So that's that's the end of the the max overview. So can I go to the slide? So the the isolating cuts the algorithm is going to help the the cuts through through the expanders or across expanders.

42:16 Uh it's going to help you with the cut that cut few of an expander that really touch expanders those you will somehow you would also do isolating costs and then so on like you will pick the terminals from the expander for example. Um I didn't explain it but it's

42:34 okay. It goes into that. Okay. Okay. So good. So for the last part of the talk I want to talk about uh APS and so this is inspiring us to doubt this conjecture and u yeah so let's see how can we you know what can we do and first of all I want to start by saying okay like this fine grain complexity these conjectures you know they're great we're building this this thing but you know they're not meant to be as you know untouchable I view this work uh saying, you know, there's these hundreds of problems. Don't work on these hundreds of problems until you break the conjectures. And once you kind of classify everything, now we should really be working on these conjecture trying to break them. It's like saying, you know, before we didn't know what to work on, now we know what to work on. We have these three conjectures. Now is the time to really attack them. You know, if they break, it'll be a mess. that you know that's

43:37 that's kind of um like now it's kind of we're more focused now. So and I just want to quickly say like what would happen if this conjecture breaks APS. So in fact APS there's like even stronger versions of it that are out there that people have used as conjectures and you can think of them as saying that APS is still true. You cannot solve it even if the graph has certain structure. The graph is a product graph or if it comes from some kind of uh convolution or if the weights are small or if you just want to compute the largest weight or things restrictions on the problem. So when I say let's attack APS, I'm also saying let's attack these harder versions and you know see which ones are actually false.

44:25 But yeah, so but then APS has its equivalence class. So there's a bunch of fundamental problems that are equivalent. So if you solve APSB faster a lot of its class will just be solved with it. So you would solve a lot of problems as well. Of course you would refute uh the other stronger versions and they have some some some of them have their equivalences but then for a lot of problems this is just one way reductions. So you would get this class of problems where the lower bounds fails but uh we don't have faster algorithms and then you okay then you just have to work on them.

45:05 Okay. So how do we I want to you know describe some attacks on the APS conjecture share some recent progress uh under this kind of framework of some combinatorics some structural analysis and some heavy tool and so of course in everything you know you we're looking for new things but let me just suggest some of the things that are out there. uh so some of the work here has been done for us specifically for APS there's very yeah you know has been studied a lot and we know a lot so some of the most uh this is great work allowing us to focus on just the triangle or matrix problem so let me explain what I mean um so I kind of mean is that you you all you have to do is look at these gra these layer three layer graphs Um, so let's start with the unweighted APS thing and then we're going to move to weighted. But this is actually how you solve the the unweed APS. I said you can solve it with fast matrix multiplication

46:10 and enter to the omega. So this is how you actually how you do it. So you go from unwrae APS to boolean matrix multiplication where you want to compute you know this kind of uh product which kind of as a graph thing you have you get a three layer graph and you want to know for every pair on the left and on the right is there a two path. So this boolean matrix multiplication is just this where this is a matrix a matrix

46:38 and a complicated reduction. Sorry. I mean you you start with shortest path on a general graph and you reduce it to this kind of graph. How complex is this? I mean

46:51 um equivalent to say so there so they're equivalent in the not really. So it's not true that they're equivalent to the omega. It's not quite true. What we know is if this is sub cubic then that is sub cubic. Um it's at a high level you can think of it as some kind of repeated squaring going from this to to the longer. So you have long pass this gives you the two halves and uh yeah okay and then if you go to weighted uh APS so here we know the sub cubic here we want to get subic we don't know. So you can still do the same thing and what you get is this min plus matrix multiplication uh where instead of the you know the and you get a plus and instead of the or you get a min. Uh and again what it really says is for every pair on the left and on the right you want to find the cheapest two path.

47:53 Virginia I came up with this equivalence while we were here. Yeah. Yeah. I didn't remember anything about that.

48:01 I don't think we told you about it then. Good. So, so we have this weighted thing this min plus and we want to solve it faster in sub cubic time and I I think there's two ways to go about it. One way is to still reduce this uh min plus to the normal matrix multiplication the plus times which is how you solve the boolean other thing. And here the idea is to somehow you know remove the weight. So you know you have the weight you want to get rid of them or handle them better and so on. And for here like you can even assume omega is two and this something whenever I'm thinking about this direction I assume omega is two doesn't really matter and you just want to deal with them better.

48:51 Uh but there's a different approach that says let's try to solve the unweighted thing in a new way and hope that this generalizes. So the thing is the you know this regular metric multiplication it doesn't you know this the way you solve it straen and all these improvement they don't allow you to solve the m plus this is like very clear barriers for that um so you can either reduce this to that or try to come up with something new for this or rather for the boolean that would generalize to men plus and this is kind of what this second direction is and it's described under this combinant the search for a combinatorial algorithm for BMM and the point is you're just trying to find a new algorithm for the unweed case and hope that it would generalize to make lusp.

49:41 So there's these two uh directions and I think both are promising in particular if you think about random the random case then for both of them it's easy like

49:53 what's random there if the graph was random or the ways are random yeah if you do these kinds of exercises then oh yeah it's easy

50:02 why is the right hand side easy for random clips if you have random weights here and there it's been known for a long time that you can actually do it in quadratic time. Can imagine if the weights are random from one to n then you expect

50:18 I thought you mean easy to reduce mean plus to plus oh sorry no I I meant the problem can be solved

50:25 the problem that makes sense. So I want to spend a bit on on each of these directions and report some new progress on them. So good. So for this direction of coming up with a new algorithm for the unweighted case. So let me tell you what is known. So you want to solve boolean metric multiplication um what can you do other than use fast multiplication. So there's this four Russians technique classical one gives you a log square shaving. Um there's these works that do divide and conquer and get some locked cube lock the four and there's uh another method using regularity decompositions by Ryan and Nicl Benzel where you know they were able to get this 2.245 and recently we got a super polylo shaving with the same framework.

51:21 uh so let me tell you a bit about that but here like the point I'm trying to make is uh maybe the regularity leas are like this structural analysis tool that we need again because random is easy and so how does regular dilemma come in so you you know you have this graph you can do a regular decomposition decompose it to a small number of graphs and each are regular and then you know once you have regular it's like random and it's But uh the bounds that you get from this is really depend on the notion of regularity like what does it really mean to be regular and there's the summary notion there's a free canon uh these give you different bounds on the number of graphs that you get and different they result in different bounds for the problem

52:13 exactly yeah so the the one we use is regularity it's very similar to what Mecca used for arithmetic progressions. Uh and so we got thing because the number of the thing is like here you're going to weaker and weaker notion. So this is a weaker notion to be regular under this notion. You're not necessarily regular under these other notions but you can show that it's enough to make the problem easy. Um and you you gain

52:46 and so the question here now oh uh for the 3 AP program Bhan's construction gives you some uh lower bound of two does that imply any like technical barriers. Yeah, great. Great. So that's exactly what I was going to say.

53:03 Oh, the question now is can you uh can you do better maybe a different notion or something to to go beyond to get a polomial improvement and as you pointed out Barren's construction is a well-known construction that of a graph that seems to be regular or is regular under a lot of notions but it has uh this kind of uh dependence. Um so we don't know we we suspect that uh balance construction is regular under this notion we could improve it. So this one question open question like it seems to be a barrier. Is it really a barrier? I'm not sure technically.

53:43 I think it's not but you remember I thought that was unlikely but we didn't do it either way.

53:50 Yeah. So that's one question. The other question is um of course you can come up with new notions and um one thing I wanted to say so there's these stronger versions of APS this the same happens with the boo triangle detection you can think of like the k click uh which when you translate it to triangle or bometric you get a graph that's a product a graph product of of other graphs and there I'm pretty sure barant fails completely so there's no barrier there to do it. I don't know how to So, what I'm saying like this same notion could still work for these stronger versions.

54:33 I I don't know how to prove it, but that's hopefully that'll inspire you to think about this. Uh, good. So, that was the first direction. Now, back to the second direction where omega is two. We want to use match fast match multiplication, but we have the weights. How do we handle them? And like in the scheme thing of things I have this heavy tool I want to use but I still might apply something here. Um and just as an example Ryan's current best algorithm for APS can be viewed that way. So you know he uses polinomial method circuit complexity to get a reduction from in plus to plus times.

55:15 Um, if it was better, we could get better, but that's what uh we get. Um, I'm going to talk about other things that don't go through this uh approach. And here I want to ask, okay, so what are these hard instances of APS? Like where are we stuck? And we didn't um we didn't really know much about this. I mean, uh let me tell you some of the things we didn't know. So, okay. Okay, so we have these weights. So what are these weights? What do they look like? You know, random we said looks kind of easy but um so the things we knew is this. So if you look at the maximum weight you can get this bound m the max weight times n to the omega. So if m the max weight was sublinear like smaller than linear then it's sub cubic. for me to and it was conjectured to this conjecture called the strong APS conjecture that the hardest cases are when M is N. So so even at the threshold where you know if the weights are smaller than N we

56:25 know how to solve it. If this the weights are n uh this conjecture said that this is as hard as APS and so it was open and it was even open more basic things like it could be that uh the number of distinct weights is small and that's still hard. So it could be that on all these edges only root n weights. Is that hard or easy? we didn't know. So recently with Nick Fischer and Sin Virginia and Sue we uh answered this question. So we showed that yes it's easy when the number of distinct weights is small. So even so if the number of distinct weight is sublinear then it's already small.

57:16 And very recently in a paper I'm very super excited about by Nick uh he showed that uh he answered this question. So he showed that APS and strong APC are equivalent. So he shows that you can take any weights and reduce them to to N. And so this result really show you know puts us at a very good place where we really know what the hard cases are. The weights are from this interval of 1 to n. That's all you have to do to solve it. And both of these results are using additive combinatorics which is be my last slide.

57:54 Um and so we use the the BSG theorem famous theorem from commentorics. Nick needs in addition to use conjectures the something called PFR conjecture the polinomial frame ruia conjecture. So his result is it equivalence is conditional on some addative combinatorics. Um okay so how does additive comic go in? So I view this BSG theorem as just another way of getting regularity some kind of structure analysis of the weights and quickly

58:38 yes and uh yeah so so this is a theorem that says you can you have a set of numbers set of imagine weights uh you can decompose them or cover them with few sets That's every set has a small subset and that's a remainder. And to really show why this helps is I just want to say that there is a generalization of this algorithm that depends on the max weight to this kind of bound where if you look at the set of weights and if the subset of the set of weights is small then you get something good. So this and it's kind of a similar algorithm and so this really shows that if you could decompose the weights or if you had these weights had small subsets then you would be happy. So then all you have to do is apply BSG and and work with that.

59:37 Wasn't the polomial 5 result you talking about? Yeah was sold. So some version was solved over F2 or something. He needs it for integers or something.

59:52 Yeah. Um the thing he uses I think seems to be very plausible but not not there. Okay. So that's the end of my talk. Thank you.

Questions about this episode

What is discussed in "All-Pairs Min-Cut vs. All-Pairs Shortest-Path - Amir Abboud"?

In order: 0:00 Max Flow, Shortest Path, Graph; 10:00 Max Flow, Shortest Path, Jason Lee; 20:00 Max Flow, Graph, Shortest Path, Expander Decomposition; 30:00 Max Flow, Expander Decomposition; 40:00 Matrix Multiplication, Max Flow, Shortest Path, Boolean Matrix Multiplication; 50:00 The BSG Theorem, Additive Combinatorics, K Click, Triangle Detection.

What is mentioned in this Institute for Advanced Study episode?

29 people, works and ideas are mentioned, including Graph, Gomory, Max Flow, Shortest Path, All Pairs Shortest Path, Dijkstra. Each one on this page links to its own page with every episode that mentions it.

How long is "All-Pairs Min-Cut vs. All-Pairs Shortest-Path - Amir Abboud"?

The episode runs 1 h; the transcript is about 9,826 words in 99 timestamped sections.

More from Institute for Advanced Study

• All analyzed episodes
• People mentioned on Institute for Advanced Study
• Topics mentioned on Institute for Advanced Study