On the Hardness of Average-Case k-SUM.

Zvika Brakerski Noah Stephens-Davidowitz Vinod Vaikuntanathan

Published in: APPROX-RANDOM (2021)

Keyphrases

average case
worst case
uniform distribution
worst case analysis
learning curves
agnostic learning
np hard
objective function
average case complexity
vc dimension
computational complexity
upper bound
decision trees
lower bound
learning theory