License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.106
URN: urn:nbn:de:0030-drops-91102
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9110/
Go to the corresponding LIPIcs Volume Portal

Blocki, Jeremiah ; Gandikota, Venkata ; Grigorescu, Elena ; Zhou, Samson

Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels

pdf-format:
LIPIcs-ICALP-2018-106.pdf (0.3 MB)

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.

BibTeX - Entry

@InProceedings{blocki_et_al:LIPIcs:2018:9110,
  author =	{Jeremiah Blocki and Venkata Gandikota and Elena Grigorescu and Samson Zhou},
  title =	{{Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{106:1--106:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9110},
  URN =		{urn:nbn:de:0030-drops-91102},
  doi =		{10.4230/LIPIcs.ICALP.2018.106},
  annote =	{Keywords: Relaxed locally correctable codes, computationally bounded channels, local expanders}
}

Keywords: Relaxed locally correctable codes, computationally bounded channels, local expanders
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI