Almost optimal super-constant-pass streaming lower bounds for reachability.

Lijie Chen Gillat Kol Dmitry Paramonov Raghuvansh R. Saxena Zhao Song Huacheng Yu

Published in: STOC (2021)

Keyphrases

lower bound
constant factor
upper bound
optimal solution
optimal cost
worst case
optimal control
competitive ratio
objective function
min sum
lower bounding
data streams
dynamic programming
lower and upper bounds
arbitrarily close
real time
memory efficient
optimal strategy
state space
np hard
data sets