Hardness Amplification Via Space-efficient Direct Products

摘要

We prove a version of the derandomized Direct Product Lemma for deterministic space-bounded algorithms. Suppose a Boolean function g : {0,1}~n → {0,1} cannot be computed on more than a fraction 1 - δ of inputs by any deterministic time T and space S algorithm, where δ ≤ 1/t for some t. Then for i-step walks w = (v_1,…, v_t) in some explicit d-regular expander graph on 2~n vertices, the function g'(w) =~(def) (g(v_1), …,g(v_t)) cannot be computed on more than a fraction 1 - Ω(tδ) of inputs by any deterministic time ≈ T/d~t - poly(n) and space ≈ S - O(t) algorithm. As an application, by iterating this construction, we get a deterministic linear-space "worst-case to constant average-case" hardness amplification reduction, as well as a family of logspace encodable/decodable error-correcting codes that can correct up to a constant fraction of errors. Logspace encodable/decodable codes (with linear-time encoding and decoding) were previously constructed by Spielman (1996). Our codes have weaker parameters (encoding length is polynomial, rather than linear), but have a conceptually simpler construction. The proof of our Direct Product lemma is inspired by Dinur's remarkable proof of the PCP theorem by gap amplification using expanders (Dinur 2006).