Brief announcement: Relaxed locally correctable codes in computationally bounded channels

Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770767
DOIs
StatePublished - Jul 1 2018
Externally publishedYes
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: Jul 9 2018Jul 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume107
ISSN (Print)1868-8969

Conference

Conference45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
CountryCzech Republic
CityPrague
Period7/9/187/13/18

Keywords

  • Computationally bounded channels
  • Local expanders
  • Relaxed locally correctable codes

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Brief announcement: Relaxed locally correctable codes in computationally bounded channels'. Together they form a unique fingerprint.

Cite this