Approximate list-decoding of direct product codes and uniform hardness amplification

Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets

Abstract

We consider the problem of approximately locally list-decoding direct product codes. For a parameter k, the k-wise direct product encoding of an N-bit message msg is an Nk-length string over the alphabet {0,1}k indexed by k-tuples (i1,...,ik) in {1,...,N}k so that the symbol at position (i1,...,ik) of the codeword is msg(i1) ... msg(ik). Such codes arise naturally in the context of hardness amplification of Boolean functions via the Direct Product Lemma (and closely related Yao's XOR Lemma), where typically k<< N (e.g., k= polylog N).

We describe an efficient randomized algorithm for approximate local list-decoding of direct product codes. Given access to a word which agrees with the k-wise direct product encoding of some message msg in at least an ε fraction of positions, our algorithm outputs a list of poly(1/ε) Boolean circuits computing N-bit strings (viewed as truth tables of (log N)-variable Boolean functions) such that at least one of them agrees with msg in at least 1-δ fraction of positions, for δ = O(k-0.1), provided that ε= Ω(poly(1/k)); the running time of the algorithm is polynomial in log N and 1/ε. When ε> e-kα for a certain constant α>0, we get a randomized approximate list-decoding algorithm that runs in time quasi-polynomial in 1/ε (i.e., in time (1/ε)polylog 1/ε).

By concatenating the k-wise direct product codes with Hadamard codes, we obtain locally list-decodable codes over the binary alphabet, which can be efficiently approximately list-decoded from fewer than 1/2- ε fraction of corruptions as long as ε = Ω(poly 1/k). As an immediate application, we get uniform hardness amplification for PNP||, the class of languages reducible to NP through one round of parallel oracle queries: If there is a language in PNP|| that cannot be decided by any BPP algorithm on more that 1-1/nΩ(1) fraction of inputs, then there is another language in PNP|| that cannot be decided by any BPP algorithm on more than 1/2+1/nω(1) fraction of inputs.

Versions