Open problems
l Flow in O(n2) time
» Eliminate v dependence
» Apply to weighted graphs with large flows
» Flow in O(m) time?
l Las Vegas algorithms
» Finding good certificates
l Detrministic algorithms
» Deterministic construction of “samples”
» Deterministically compress a graph