4
$\begingroup$

Are there known locally decodable erasure codes with
linear codeword length and $\:n^{o(1)}\:$ query complexity?

According to pages 1 and 4 of this link (which annoying does not give its own date,
though it cites references from 2011), locally decodable (error-correcting) codes
with linear codeword length are only known with query complexity $n^{\epsilon}$ for $\: \epsilon > 0 \;$.
i.e., Does considering erasure codes instead change that?

Such a code could be used for showing that a data host has random access to a given file.

$\endgroup$
4
$\begingroup$

Locally decodable codes and locally decodable erasure codes are qualitatively equivalent. Both imply $\Omega(m)$ many disjoint $q$-tuples from which one can recover a given message coordinate, where $m$ is the codeword length and $q$ is the query complexity. A formal argument appears in Section 3.4 of Kerenidis and de Wolf's paper.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy