Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets · SIAM Journal on Computing · 2009
Given a message $msg\in\{0,1\}^N$, its k-wise direct product encoding is the sequence of k-tuples $(msg(i_1),\dots,msg(i_k))$ over all possible k-tuples of indices $(i_1,\dots,i_k)\in\{1,\dots,N\}^k$. We give an efficient randomized algorithm for approximate local list-decoding of direct product codes. That is, given oracle access to a word which agrees with a k-wise direct product encoding of some message $msg\in\{0,1\}^N$ in at least $\epsilon\geqslant{poly}(1/k)$ fraction of positions, our algorithm outputs a list of ${poly}(1/\epsilon)$ strings that contains at least one string $msg'$ which is equal to $msg$ in all but at most $k^{-\Omega(1)}$ fraction of positions. The decoding is local in that our algorithm outputs a list of Boolean circuits so that the jth bit of the ith output string can be computed by running the ith circuit on input j. The running time of the algorithm is polynomial in $\log N$ and $1/\epsilon$. In general, when $\epsilon>e^{-k^{\alpha}}$ for a sufficiently small constant $\alpha>0$, we get a randomized approximate list-decoding algorithm that runs in time quasi-polynomial in $1/\epsilon$, i.e., $(1/\epsilon)^{{poly}\log1/\epsilon}$. As an application of our decoding algorithm, we get uniform hardness amplification for ${P}^{{NP}_{\parallel}}$, the class of languages reducible to ${NP}$ through one round of parallel oracle queries: If there is a language in ${P}^{{NP}_{\parallel}}$ that cannot be decided by any ${BPP}$ algorithm on more than $1-1/n^{\Omega(1)}$ fraction of inputs, then there is another language in ${P}^{{NP}_{\parallel}}$ that cannot be decided by any ${BPP}$ algorithm on more than $1/2+1/n^{\omega(1)}$ fraction of inputs.