2026-07-24T00:56:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9110 2024-03-06T10:43:23Z ddc:004 open_access

Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels Blocki, Jeremiah Gandikota, Venkata Grigorescu, Elena Zhou, Samson Relaxed locally correctable codes computationally bounded channels local expanders We study variants of locally decodable and locally correctable codes in computationally bounded, adversarial channels, under the assumption that collision-resistant hash functions exist, and with no public-key or private-key cryptographic setup. Specifically, we provide constructions of relaxed locally correctable and relaxed locally decodable codes over the binary alphabet, with constant information rate, and poly-logarithmic locality. Our constructions compare favorably with existing schemes built under much stronger cryptographic assumptions, and with their classical analogues in the computationally unbounded, Hamming channel. Our constructions crucially employ collision-resistant hash functions and local expander graphs, extending ideas from recent cryptographic constructions of memory-hard functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeremiah Blocki and Venkata Gandikota and Elena Grigorescu and Samson Zhou 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.106 urn:nbn:de:0030-drops-91102 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.106 eng https://creativecommons.org/licenses/by/3.0/legalcode