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