Elena Grigorescu
Relaxed Locally Correctable Codes in Computationally Bounded Channels

Abstract: Locally correctable codes for the Hamming channel exhibit dramatic tradeoffs between their information rate and the locality of the correcting algorithm. We construct  ``relaxed'' versions of locally correctable codes,  for computationally bounded, yet adversarial channels, under the assumption that collision-resistant hash functions exist. Specifically, we build 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.

-
Joint work with Jeremiah Blocki, Venkata Gandikota, Samson Zhou.