On the Hardness of Average-case k-SUM.

Zvika Brakerski Noah Stephens-Davidowitz Vinod Vaikuntanathan

Published in: CoRR (2020)

Keyphrases

average case
worst case
worst case analysis
uniform distribution
learning curves
np hard
average case complexity
objective function
computational complexity
agnostic learning
lower bound
upper bound
phase transition
sample size
learning theory
data sets
special case
machine learning