ECCC-Report TR01-080https://eccc.weizmann.ac.il/report/2001/080Comments and Revisions published for TR01-080en-usSun, 17 Mar 2002 00:00:00 +0200
Revision 3
| Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval Revision of: TR01-080 |
Oded Goldreich,
Howard Karloff,
Leonard J. Schulman,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2001/080#revision3
We prove that if a linear error correcting code
$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can
be probabilistically reconstructed by looking at two entries of a
corrupted codeword, then $m = 2^{\Omega(n)}$. We also present
several extensions of this result.
We show a reduction from the complexity of one-round,
information-theoretic Private Information Retrieval Systems (with
two servers) to Locally Decodable Codes, and conclude that if all
the servers' answers are linear combinations of the database
content, then $t = \Omega(n/2^a)$, where $t$ is the length of the
user's query and $a$ is the length of the servers' answers.
Actually, $2^a$ can be replaced by $O(a^k)$, where $k$ is the
number of bit locations in the answer that are actually
inspected in the reconstruction.
Sun, 17 Mar 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2001/080#revision3
Revision 1
| |
Oded Goldreich,
Howard Karloff,
Leonard J. Schulman,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2001/080#revision1Sun, 17 Mar 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2001/080#revision1
Revision 2
| |
Oded Goldreich,
Howard Karloff,
Leonard J. Schulman,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2001/080#revision2Sun, 17 Mar 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2001/080#revision2
Paper TR01-080
| Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval |
Oded Goldreich,
Howard Karloff,
Leonard Schulman,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2001/080
We prove that if a linear error correcting code
$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can
be probabilistically reconstructed by looking at two entries of a
corrupted codeword, then $m = 2^{\Omega(n)}$. We also present
several extensions of this result.
We show a reduction from the complexity of one-round,
information-theoretic Private Information Retrieval Systems (with
two servers) to Locally Decodable Codes, and conclude that if all
the servers' answers are linear combinations of the database
content, then $t = \Omega(n/2^a)$, where $t$ is the length of the
user's query and $a$ is the length of the servers' answers.
Actually, $2^a$ can be replaced by $O(a^k)$, where $k$ is the
number of bit locations in the answer that are actually
inspected in the reconstruction.
Wed, 14 Nov 2001 09:44:14 +0200https://eccc.weizmann.ac.il/report/2001/080