Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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] 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

Request Changes to record.

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:
DateEvent
January 2021Published
1 October 2020Accepted
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
Date of first compliant deposit: 28 November 2019
Date of first compliant Open Access: 2 December 2019
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:
  • Organisation
Open Access Version:
  • ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us