Worst-Case to Average Case Reductions for the Distance to a Code.

Eli Ben-Sasson Swastik Kopparty Shubhangi Saraf

Published in: Computational Complexity Conference (2018)

Keyphrases

average case
worst case
worst case analysis
learning curves
uniform distribution
lower bound
approximation algorithms
upper bound
greedy algorithm
distance measure
online algorithms
np hard
boolean functions
average case complexity