actual abstract:
The max flow problem is one of the most fundamental and well-studied network problems. In this talk, I will revisit it from the perspective of distributed algorithms. For decades, the million-dollar question here has been whether there *is* a fast distributed algorithm or one should rather collect all information at a single location and apply an old school centralized algorithm. On the way to answering this question, we will get to see several of the brilliant ideas that have come up recently on this evergreen among the classic graph problems. The talk is tailored to a general CS audience; don't worry if you're not familiar with the topic - come to enjoy the show!