The Library
A structural theorem for local algorithms with applications to testing, coding, and privacy
Tools
Tools
Tools
Dall'Agnol, Marcel, Gur, Tom, Wajc, David and Lachish, Oded (2021) A structural theorem for local algorithms with applications to testing, coding, and privacy. In: ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021. Published in: SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1651-1665. ISBN 9781611976465. doi:10.5555/3458064.3458164
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-structural-theorem-local-algorithms-applications-testing-coding-privacy-Gur-2020.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (1123Kb) |
Official URL: https://dl.acm.org/doi/10.5555/3458064.3458164
Abstract
We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes q adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with n1−1/O(q2 log2 q) sample complexity. We also prove that this transformation is nearly optimal, and admits a scheme for constructing privacy-preserving local algorithms.
Using the unified view that our structural theorem provides, we obtain the following results.
• We strengthen the state-of-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish (SODA 2020).
• We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity; this resolves a problem left open in a work of Fischer, Lachish, and Vasudev (FOCS 2015) by extending their main result to adaptive testers.
• We prove that the known separation between proofs of proximity and testers is essentially maximal; this resolves a problem left open by Gur and Rothblum (ECCC 2013, Computational Complexity 2018) regarding sublinear-time delegation of computation.
Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal-Szemerédi theorem.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Journal or Publication Title: | SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||
| Publisher: | SIAM | ||||||
| ISBN: | 9781611976465 | ||||||
| Official Date: | January 2021 | ||||||
| Dates: |
|
||||||
| Page Range: | pp. 1651-1665 | ||||||
| DOI: | 10.5555/3458064.3458164 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | ACM-SIAM Symposium on Discrete Algorithms (SODA21) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Virtual | ||||||
| Date(s) of Event: | 10-13 Jan 2021 | ||||||
| Related URLs: | |||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
