{"data":{"id":"10.48550/arxiv.2010.04985","type":"dois","attributes":{"doi":"10.48550/arxiv.2010.04985","prefix":"10.48550","suffix":"arxiv.2010.04985","identifiers":[{"identifier":"2010.04985","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"2010.04985"}],"creators":[{"name":"Dall'Agnol, Marcel","nameType":"Personal","givenName":"Marcel","familyName":"Dall'Agnol","affiliation":[],"nameIdentifiers":[]},{"name":"Gur, Tom","nameType":"Personal","givenName":"Tom","familyName":"Gur","affiliation":[],"nameIdentifiers":[]},{"name":"Lachish, Oded","nameType":"Personal","givenName":"Oded","familyName":"Lachish","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification"}],"publisher":"arXiv","container":{},"publicationYear":2020,"subjects":[{"lang":"en","subject":"Computational Complexity (cs.CC)","subjectScheme":"arXiv"},{"lang":"en","subject":"Discrete Mathematics (cs.DM)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2020-10-10T12:46:42Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2020-10-13T00:11:04Z","dateType":"Updated","dateInformation":"v1"},{"date":"2023-12-12T16:00:36Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2023-12-13T01:30:22Z","dateType":"Updated","dateInformation":"v2"},{"date":"2020-10","dateType":"Available","dateInformation":"v1"},{"date":"2020","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1137/21m1422781","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"2","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"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 $n^{1- 1/O(q^2 \\log^2 q)}$ sample complexity, following the definition of Goldreich and Ron (TOCT 2016). We prove that this transformation is nearly optimal. Our theorem also admits a scheme for constructing privacy-preserving local algorithms. Using the unified view that our structural theorem provides, we obtain results regarding various types of local algorithms, including the following.\n - 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 (SICOMP 2021).\n - 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.\n - 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.\n Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal-Szemerédi theorem.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4yMDEwLjA0OTg1PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MjAxMC4wNDk4NTwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5EYWxsJ0Fnbm9sLCBNYXJjZWw8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPk1hcmNlbDwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5EYWxsJ0Fnbm9sPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkd1ciwgVG9tPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5Ub208L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+R3VyPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkxhY2hpc2gsIE9kZWQ8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPk9kZWQ8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+TGFjaGlzaDwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+QSBTdHJ1Y3R1cmFsIFRoZW9yZW0gZm9yIExvY2FsIEFsZ29yaXRobXMgd2l0aCBBcHBsaWNhdGlvbnMgdG8gQ29kaW5nLCBUZXN0aW5nLCBhbmQgVmVyaWZpY2F0aW9uPC90aXRsZT4KICA8L3RpdGxlcz4KICA8cHVibGlzaGVyPmFyWGl2PC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDIwPC9wdWJsaWNhdGlvblllYXI+CiAgPHN1YmplY3RzPgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+Q29tcHV0YXRpb25hbCBDb21wbGV4aXR5IChjcy5DQyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5EaXNjcmV0ZSBNYXRoZW1hdGljcyAoY3MuRE0pPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogQ29tcHV0ZXIgYW5kIGluZm9ybWF0aW9uIHNjaWVuY2VzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAyMC0xMC0xMFQxMjo0Njo0Mlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAyMC0xMC0xM1QwMDoxMTowNFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDIzLTEyLTEyVDE2OjAwOjM2WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDIzLTEyLTEzVDAxOjMwOjIyWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMjAtMTA8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlRleHQiPkFydGljbGU8L3Jlc291cmNlVHlwZT4KICA8cmVsYXRlZElkZW50aWZpZXJzPgogICAgPHJlbGF0ZWRJZGVudGlmaWVyIHJlbGF0ZWRJZGVudGlmaWVyVHlwZT0iRE9JIiByZWxhdGlvblR5cGU9IklzVmVyc2lvbk9mIj4xMC4xMTM3LzIxTTE0MjI3ODE8L3JlbGF0ZWRJZGVudGlmaWVyPgogIDwvcmVsYXRlZElkZW50aWZpZXJzPgogIDx2ZXJzaW9uPjI8L3ZlcnNpb24+CiAgPHJpZ2h0c0xpc3Q+CiAgICA8cmlnaHRzIHJpZ2h0c1VSST0iaHR0cDovL2FyeGl2Lm9yZy9saWNlbnNlcy9ub25leGNsdXNpdmUtZGlzdHJpYi8xLjAvIj5hclhpdi5vcmcgcGVycGV0dWFsLCBub24tZXhjbHVzaXZlIGxpY2Vuc2U8L3JpZ2h0cz4KICA8L3JpZ2h0c0xpc3Q+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij5XZSBwcm92ZSBhIGdlbmVyYWwgc3RydWN0dXJhbCB0aGVvcmVtIGZvciBhIHdpZGUgZmFtaWx5IG9mIGxvY2FsIGFsZ29yaXRobXMsIHdoaWNoIGluY2x1ZGVzIHByb3BlcnR5IHRlc3RlcnMsIGxvY2FsIGRlY29kZXJzLCBhbmQgUENQcyBvZiBwcm94aW1pdHkuIE5hbWVseSwgd2Ugc2hvdyB0aGF0IHRoZSBzdHJ1Y3R1cmUgb2YgZXZlcnkgYWxnb3JpdGhtIHRoYXQgbWFrZXMgJHEkIGFkYXB0aXZlIHF1ZXJpZXMgYW5kIHNhdGlzZmllcyBhIG5hdHVyYWwgcm9idXN0bmVzcyBjb25kaXRpb24gYWRtaXRzIGEgc2FtcGxlLWJhc2VkIGFsZ29yaXRobSB3aXRoICRuXnsxLSAxL08ocV4yIFxsb2deMiBxKX0kIHNhbXBsZSBjb21wbGV4aXR5LCBmb2xsb3dpbmcgdGhlIGRlZmluaXRpb24gb2YgR29sZHJlaWNoIGFuZCBSb24gKFRPQ1QgMjAxNikuIFdlIHByb3ZlIHRoYXQgdGhpcyB0cmFuc2Zvcm1hdGlvbiBpcyBuZWFybHkgb3B0aW1hbC4gT3VyIHRoZW9yZW0gYWxzbyBhZG1pdHMgYSBzY2hlbWUgZm9yIGNvbnN0cnVjdGluZyBwcml2YWN5LXByZXNlcnZpbmcgbG9jYWwgYWxnb3JpdGhtcy4gVXNpbmcgdGhlIHVuaWZpZWQgdmlldyB0aGF0IG91ciBzdHJ1Y3R1cmFsIHRoZW9yZW0gcHJvdmlkZXMsIHdlIG9idGFpbiByZXN1bHRzIHJlZ2FyZGluZyB2YXJpb3VzIHR5cGVzIG9mIGxvY2FsIGFsZ29yaXRobXMsIGluY2x1ZGluZyB0aGUgZm9sbG93aW5nLgogIC0gV2Ugc3RyZW5ndGhlbiB0aGUgc3RhdGUtb2YtdGhlLWFydCBsb3dlciBib3VuZCBmb3IgcmVsYXhlZCBsb2NhbGx5IGRlY29kYWJsZSBjb2Rlcywgb2J0YWluaW5nIGFuIGV4cG9uZW50aWFsIGltcHJvdmVtZW50IG9uIHRoZSBkZXBlbmRlbmN5IGluIHF1ZXJ5IGNvbXBsZXhpdHk7IHRoaXMgcmVzb2x2ZXMgYW4gb3BlbiBwcm9ibGVtIHJhaXNlZCBieSBHdXIgYW5kIExhY2hpc2ggKFNJQ09NUCAyMDIxKS4KICAtIFdlIHNob3cgdGhhdCBhbnkgKGNvbnN0YW50LXF1ZXJ5KSB0ZXN0YWJsZSBwcm9wZXJ0eSBhZG1pdHMgYSBzYW1wbGUtYmFzZWQgdGVzdGVyIHdpdGggc3VibGluZWFyIHNhbXBsZSBjb21wbGV4aXR5OyB0aGlzIHJlc29sdmVzIGEgcHJvYmxlbSBsZWZ0IG9wZW4gaW4gYSB3b3JrIG9mIEZpc2NoZXIsIExhY2hpc2gsIGFuZCBWYXN1ZGV2IChGT0NTIDIwMTUpIGJ5IGV4dGVuZGluZyB0aGVpciBtYWluIHJlc3VsdCB0byBhZGFwdGl2ZSB0ZXN0ZXJzLgogIC0gV2UgcHJvdmUgdGhhdCB0aGUga25vd24gc2VwYXJhdGlvbiBiZXR3ZWVuIHByb29mcyBvZiBwcm94aW1pdHkgYW5kIHRlc3RlcnMgaXMgZXNzZW50aWFsbHkgbWF4aW1hbDsgdGhpcyByZXNvbHZlcyBhIHByb2JsZW0gbGVmdCBvcGVuIGJ5IEd1ciBhbmQgUm90aGJsdW0gKEVDQ0MgMjAxMywgQ29tcHV0YXRpb25hbCBDb21wbGV4aXR5IDIwMTgpIHJlZ2FyZGluZyBzdWJsaW5lYXItdGltZSBkZWxlZ2F0aW9uIG9mIGNvbXB1dGF0aW9uLgogIE91ciB0ZWNobmlxdWVzIHN0cm9uZ2x5IHJlbHkgb24gcmVsYXhlZCBzdW5mbG93ZXIgbGVtbWFzIGFuZCB0aGUgSGFqbmFsLVN6ZW1lcsOpZGkgdGhlb3JlbS48L2Rlc2NyaXB0aW9uPgogIDwvZGVzY3JpcHRpb25zPgo8L3Jlc291cmNlPg==","url":"https://arxiv.org/abs/2010.04985","contentUrl":null,"metadataVersion":1,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":1,"created":"2022-02-23T23:23:25.000Z","registered":"2022-02-23T23:23:26.000Z","published":"2020","updated":"2023-12-13T02:45:40.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.2010.04985","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[{"id":"10.1137/21m1422781","type":"dois"}]}}}}