Seminar • Algorithms and Complexity • Worst-Case to Average-Case Reductions via Additive Combinatorics
Please note: This seminar will be given online.
Vahid Asadi, PhD candidate
David R. Cheriton School of Computer Science
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 \log T) that are correct on all inputs.