ECCC-Report TR22-020https://eccc.weizmann.ac.il/report/2022/020Comments and Revisions published for TR22-020en-usFri, 18 Feb 2022 12:38:25 +0200
Paper TR22-020
| Worst-Case to Average-Case Reductions via Additive Combinatorics |
Vahid Reza Asadi,
Alexander Golovnev,
Tom Gur,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2022/020We 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 $\widetilde{O}(T)$ that are correct on all inputs.
Using our framework, we obtain such efficient worst-case to average-case reductions for fundamental problems in a variety of computational models; namely, algorithms for matrix multiplication, streaming algorithms for the online matrix-vector multiplication problem, and static data structures for all linear problems as well as for the multivariate polynomial evaluation problem.
Our techniques crucially rely on additive combinatorics. In particular, we show a local correction lemma that relies on a new probabilistic version of the quasi-polynomial Bogolyubov-Ruzsa lemma.Fri, 18 Feb 2022 12:38:25 +0200https://eccc.weizmann.ac.il/report/2022/020