Lower bounds for linear locally decodable codes and private information retrieval

Oded Goldreich, Howard Karloff, Leonard J. Schulman and Luca Trevisan
Computational Complexity
Issue Volume 15, Number 3 / October, 2006
Pages 263-296
http://dx.doi.org/10.1007/s00037-006-0216-3

CCC 2002 (Conference on Computational Complexity) の論文のジャーナル版。

2つの構造のサイズに関する下界。
1つめは線形locally decodable codeについて。
これはn個の文字をm個の文字に変換する符号化方式で、
符号語が壊れても、符号語の高々2個の文字を(乱数で選んで)読むことで、全体を正しく復元できる(確率が高い)、というものである。
そのような符号語の長さmに関する下界としていままではnの線形関数より少し大きいものしか知られていなかったが (Katz and Trevisan 2000)、この論文ではそれをnの指数関数に改善している。
かなり大幅な改善である。
証明は「いつものように」extremal combinatoricsのような雰囲気を漂わせてるように見える。

もう1つの構造はprivate information retrieval schemeというもので、それに対するquery sizeの下界を導出している。
これはlocally decodable codeとの関係を示すことで得られている。