Upper and Lower Bounds on the Space Complexity of Detectable Objects.

Ohad Ben-Baruch Danny Hendler Matan Rusanovsky

Published in: PODC (2020)

Keyphrases

upper and lower bounds
space complexity
upper bound
lower bound
worst case
lower and upper bounds
arc consistency
sample complexity
worst case time complexity
machine learning
support vector machine
constraint satisfaction
dnf formulas
tight upper and lower bounds