Seminar • Algorithms and Complexity • Space Complexity for Approximate All-pairs Max Flows

Please note: This seminar will take place in DC 1304 and online.

Thatchaphol Saranurak, Assistant Professor
Computer Science and Engineering, University of Michigan

I will show that any data structure for sqrt{n}-additive approximate max flow requires \Omega(n^2) space, generalizing the trivial lower bound of n^2 in the exact case.

To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.