Abstract
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 1–δ fraction of inputs by any deterministic time T and space S algorithm, where δ ≤ 1/t for some t. Then, for t-step walks w=(v 1,..., v t ) in some explicit d-regular expander graph on 2n vertices, the function g’(w) \(\underset{=}{\rm def}\) g(v1...g(v t )cannot be computed on more than 1–Ω(tδ) fraction of inputs by any deterministic time ≈ T/d t − poly(n) and space ≈ S – O(t). 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 [14]. 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 recent proof of the PCP theorem by gap amplification using expanders [4].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Bruck, J., Naor, J., Naor, M., Roth, R.: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory 38, 509–516 (1992)
Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity 3, 307–318 (1993)
Capalbo, M.R., Reingold, O., Vadhan, S., Wigderson, A.: Randomness conductors and constant-degree lossless expanders. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 659–668 (2002)
Dinur, I.: The PCP theorem by gap amplification. Electronic Colloquium on Computational Complexity, TR05-046 (2005)
Goldreich, O., Nisan, N., Wigderson, A.: On Yao’s XOR-Lemma. Electronic Colloquium on Computational Complexity, TR95-050 (1995)
Guruswami, V., Indyk, P.: Expander-based constructions of efficiently decodable codes. In: Proceedings of the Forty-Second Annual IEEE Symposium on Foundations of Computer Science, pp. 658–667 (2001)
Guruswami, V., Indyk, P.: Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 812–821 (2002)
Guruswami, V., Indyk, P.: Linear-time encodable and list decodable codes. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 126–135 (2003)
Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: Proceedings of the Thirty-Sixth Annual IEEE Symposium on Foundations of Computer Science, pp. 538–545 (1995)
Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220–229 (1997)
Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7(4), 357–363 (1987)
Nisan, N., Wigderson, A.: Hardness vs. randomness. Journal of Computer and System Sciences 49, 149–167 (1994)
Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics 155(1), 157–187 (2002)
Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory 42(6), 1723–1732 (1996)
Trevisan, L.: List-decoding using the XOR lemma. In: Proceedings of the Forty-Fourth Annual IEEE Symposium on Foundations of Computer Science, pp. 126–135 (2003)
Yao, A.C.: Theory and applications of trapdoor functions. In: Proceedings of the Twenty-Third Annual IEEE Symposium on Foundations of Computer Science, pp. 80–91 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guruswami, V., Kabanets, V. (2006). Hardness Amplification Via Space-Efficient Direct Products. In: Correa, J.R., Hevia, A., Kiwi, M. (eds) LATIN 2006: Theoretical Informatics. LATIN 2006. Lecture Notes in Computer Science, vol 3887. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11682462_52
Download citation
DOI: https://doi.org/10.1007/11682462_52
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32755-4
Online ISBN: 978-3-540-32756-1
eBook Packages: Computer ScienceComputer Science (R0)