Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval
Wehner, Stephanie, Ronald de Wolf · 2004
Abstract. We prove new lower bounds for locally decodable codes and private information retrieval. We show that a 2-query LDC encoding nbit strings over an ℓ-bit alphabet, where the decoder � only � uses b bits ��of each queried position, needs code length m = exp