Worst-Case to Average-Case Reductions via Additive Combinatorics.

Vahid R. Asadi Alexander Golovnev Tom Gur Igor Shinkar

Published in: CoRR (2022)

Keyphrases

average case
worst case
worst case analysis
learning curves
np hard
uniform distribution
upper bound
approximation algorithms
graph theory
lower bound
average case complexity
data sets
online algorithms
training data
sample size
small number
feature space
computational complexity
optimal solution