Linear space streaming lower bounds for approximating CSPs.

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

Published in: STOC (2022)

Keyphrases

linear space
lower bound
constraint satisfaction problems
space efficient
upper bound
data streams
np hard
objective function
external memory
nearest neighbor search
worst case
optimal solution
arbitrary shape
search space
data sets
locality sensitive hashing
multimedia