Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms.

Sepehr Assadi Ran Raz

Published in: FOCS (2020)

Keyphrases

lower bound
graph theory
computational complexity
learning algorithm
random walk
theoretical analysis
objective function
online algorithms
optimization problems
upper bound
data structure
worst case
linear programming
np hard
pairwise
shortest path
branch and bound
graph matching
data streams
max flow