I'm studying the reduction about some hard problems on the lattice. What's the meaning of "worst case to average case reduction" ? For example, the paper "Worst-case to Average-case Reductions based on Gaussian Measures" gives the reduction from the worst case INCGDD problem to average case SIS problem, what does it mean?
1 Answers
A problem has average-case time complexity C if there exists an algorithm that solves the problem in C time on average, if the inputs are chosen randomly according to some distribution. Formalizing this is tricky, see here.
A problem has a worse case to average case reduction if you can show the following: if an algorithm solving the problem with average-case complexity C exists then this algorithm can be applied to also solve the worst-case with the same complexity (modulo a polynomial factor).
Related