论文标题
通过添加剂组合制剂，平均案例减少的最差案例减少
Worst-Case to Average-Case Reductions via Additive Combinatorics
论文作者
论文摘要
我们提出了一个新的框架，用于设计最坏情况，以减少平均案例。对于大量的问题，它提供了在时间$ t $中运行的算法的明确转换，这些算法仅在其输入的小（子构成）中正确地转换为在时间上运行的算法$ \ widetilde {o}（o}（t）$，这些算法在所有输入中都是正确的。 使用我们的框架，我们为各种计算模型中的基本问题提供了如此有效的最坏情况。也就是说，用于矩阵乘法的算法，在线矩阵向量乘法问题的流算法以及所有线性问题的静态数据结构以及多元多项式评估问题。 我们的技术至关重要的是添加剂组合学。特别是，我们展示了局部校正引理，该校正引理依赖于准多项式Bogolyubov-Ruzsa引理的新概率版本。
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 $\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.
