Linear Space Streaming Lower Bounds for Approximating CSPs.

Chi-Ning Chou Alexander Golovnev Madhu Sudan Ameya Velingker Santhoshini Velusamy

Published in: CoRR (2021)

Keyphrases

linear space
lower bound
constraint satisfaction problems
upper bound
space efficient
data streams
np hard
external memory
search space
nearest neighbor search
arbitrary shape
locality sensitive hashing
optimal solution
worst case
objective function
data structure
sliding window
database management systems