« search calendars« Workshop on Hardness of Approximation in P

« Space Complexity for (approx) All-pairs Max Flows

Space Complexity for (approx) All-pairs Max Flows

July 23, 2025, 11:30 AM - 12:00 PM

Location:

Rutgers Academic Building, Room 4225 (East Wing)

Rutgers University

College Avenue Campus

15 Seminary Place

New Brunswick, NJ 08901

Click here for map.

Thatchaphol Saranurak, University of Michigan

I discuss the n^2-space lower bound for all-pairs maximum flows in graphs with unit-vertex capacity. I explain the gap amplification idea inside this lower bound.

[Video]   [Slides]