The Library
Worst-case to average-case reductions via additive combinatorics
Tools
Asadi, Vahid R., Golovnev, Alexander, Gur, Tom and Shinkar, Igor (2022) Worst-case to average-case reductions via additive combinatorics. In: The 54th ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, 20-24 Jun 2022. Published in: STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing pp. 1566-1574. ISBN 9781450392648. doi:10.1145/3519935.3520041
|
PDF
WRAP-worst-case-average-case-reductions-via-additive-combinatorics-Gur-2022.pdf - Accepted Version - Requires a PDF viewer. Download (783Kb) | Preview |
Official URL: https://doi.org/10.1145/3519935.3520041
Abstract
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.
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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Combinatorial analysis -- Computer programs, Computational complexity | ||||||
Journal or Publication Title: | STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | ||||||
Publisher: | ACM | ||||||
ISBN: | 9781450392648 | ||||||
Official Date: | 10 June 2022 | ||||||
Dates: |
|
||||||
Page Range: | pp. 1566-1574 | ||||||
DOI: | 10.1145/3519935.3520041 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | © ACM, 2022 This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. June 2022 http://doi.acm.org/10.1145/3519935.3520041 | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 3 March 2022 | ||||||
Date of first compliant Open Access: | 7 March 2022 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | The 54th ACM Symposium on Theory of Computing (STOC 2022) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Rome, Italy | ||||||
Date(s) of Event: | 20-24 Jun 2022 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year