Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle.

Dylan M. McKay Richard Ryan Williams

Published in: ITCS (2019)

Keyphrases

lower bound
objective function
upper bound
real world
linear functions
worst case
lower and upper bounds
neural network
pairwise
search space
np hard
optimal solution
dimensionality reduction
space time
branch and bound
branch and bound algorithm
boolean functions
vc dimension
upper and lower bounds
lower bounding