Using nondeterminism to amplify hardness

ABSTRACT

We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (STOC '02). We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a function f′ such that any circuit of size s′(n)=s(√n)^Ω(1) fails to compute f′ on a 1/2 - 1/s′(n) fraction of inputs. In particular, 1. If s(n)=n^ω(1), we amplify to hardness 1/2-1/n^ω(1). 2. If s(n)=2^nω(1), we amplify to hardness 1/2-1/2^nΩ(1). 3. If s(n)=2⁽ⁿ⁾, we amplify to hardness 1/2-1/2 ^Ω(sqrtn).These improve the results of O'Donnell, which only amplified to 1/2-1/√n. O'Donnell also proved that no construction of a certain general form could amplify beyond 1/2-1/n. We bypass this barrier by using both derandomization and nondeterminism in the construction of f′.We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for "black-box" hardness amplification procedures (such as ours).

REFERENCES

• 1: Ian Anderson. Combinatorics of finite sets. Dover Publications Inc., Mineola, NY, 2002. Corrected reprint of the 1989 edition.
• 2: László Babai, Lance Fortnow, and Carsten Lund. Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1):3--40, 1991.
• 3: Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
• 4: Michael Ben-Or and Nathan Linial. Collective coin-flipping. In Silvio Micali, editor, Randomness and Computation, pages 91--115. Academic Press, New York, 1990.
• 5: Andrej Bogdanov , Luca Trevisan, On Worst-Case to Average-Case Reductions for NP Problems, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.308, October 11-14, 2003
• 6: Jin-Yi Cai, A. Pavan, and D. Sivakumar. On the hardness of the permanent. In 16th International Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Trier, Germany, March 4--6 1999. Springer-Verlag.
• 7: Uriel Feige , Carsten Lund, On the hardness of computing the permanent of random matrices, Computational Complexity, v.6 n.2, p.101-132, 1996/1997 [doi>10.1007/BF01262928]
• 8: Joan Feigenbaum , Lance Fortnow, Random-self-reducibility of complete sets, SIAM Journal on Computing, v.22 n.5, p.994-1005, Oct. 1993 [doi>10.1137/0222061]
• 9: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 10: Oded Goldreich, Noam Nisan, and Avi Wigderson. On Yao's XOR lemma. Technical Report TR95--050, Electronic Colloquium on Computational Complexity, March 1995. http://www. eccc. uni-trier. de/eccc.
• 11: R. Impagliazzo, Hard-core distributions for somewhat hard problems, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.538, October 23-25, 1995
• 12: Russell Impagliazzo , Noam Nisan , Avi Wigderson, Pseudorandomness for network algorithms, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.356-364, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195190]
• 13: Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
• 14: R. Impagliazzo , A. Wigderson, Randomness vs. Time: De-Randomization under a Uniform Assumption, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.734, November 08-11, 1998
• 15: Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on Boolean functions (extended abstract). In Proceedings of 29th FOCS, pages 68--80, White Plains, New York, 24--26 October 1988. IEEE.
• 16: Adam R. Klivans , Rocco A. Servedio, Boosting and Hard-Core Set Construction, Machine Learning, v.51 n.3, p.217-238, June 2003 [doi>10.1023/A:1022949332276]
• 17: Richard Lipton. New directions in testing. In Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, 1989.
• 18: Elchanan Mossel , Ryan O'Donnell, On the noise sensitivity of monotone functions, Random Structures & Algorithms, v.23 n.3, p.333-350, October 2003 [doi>10.1002/rsa.10097]
• 19: Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12, 1992.
• 20: Noam Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63--70, 1991.
• 21: Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
• 22: Ryan O'Donnell, Hardness amplification within NP, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510015]
• 23: Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR lemma, Journal of Computer and System Sciences, v.62 n.2, p.236-266, March 2001 [doi>10.1006/jcss.2000.1730]
• 24: Luca Trevisan, List-Decoding Using The XOR Lemma, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.126, October 11-14, 2003
• 25: Luca Trevisan , Salil Vadhan, Pseudorandomness and Average-Case Complexity via Uniform Reductions, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.129, May 21-24, 2002
• 26: Emanuele Viola. The complexity of constructing pseudorandom generators from hard functions. Technical report, Electronic Colloquium on Computational Complexity, 2004. http://www. eccc. uni-trier. de/eccc. Preliminary version titled 'Hardness vs. Randomness within Alternating Time', in Eighteenth Annual IEEE Conference on Computational Complexity.
• 27: Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In Proceedings of 23rd FOCS, pages 80--91, Chicago, Illinois, 3--5 November 1982. IEEE.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Theory

Keywords:
average-case complexity, hardness amplification, noise stability, pseudorandom generators for space-bounded computation