Worst-case to average case reductions for the distance to a code.

Eli Ben-Sasson Swastik Kopparty Shubhangi Saraf

Published in: Electron. Colloquium Comput. Complex. (2018)

Keyphrases

average case
worst case
worst case analysis
uniform distribution
learning curves
lower bound
upper bound
np hard
euclidean distance
greedy algorithm
approximation algorithms
average case complexity
reinforcement learning
theoretical analysis
distance function
sample size