Worst and Average Case Hardness of Decoding via Smoothing Bounds.

Thomas Debris-Alazard Nicolas Resch

Published in: IACR Cryptol. ePrint Arch. (2022)

Keyphrases

average case
worst case
upper bound
worst case analysis
learning curves
uniform distribution
np hard
lower bound
computational complexity
vc dimension
data sets
machine learning algorithms
approximation algorithms
phase transition
np hardness
agnostic learning