Worst-case to average-case reductions via additive combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar · 2022
We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time T that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time O(T) that are correct on all inputs.