On uniform amplification of hardness in NP

ABSTRACT

We continue the study of amplification of average-case complexity within NP, and we focus on the uniform case.We prove that if every problem in NP admits an efficient uniform algorithm that (averaged over random inputs and over the internal coin tosses of the algorithm) succeeds with probability at least 1 ⁄ 2 +1 (log n )α, then for every problem in NP there is an efficient uniform algorithm that succeeds with probability at least 1 - 1 poly(n). Above, α > 0 is an absolute constant.Previously, Trevisan (FOCS'03) presented a similar redution between success 3⁄4 + 1 (log n) and 1 - 1 (log n)α Stronger reductions, due to O'Donnell (STOC'02) and Healy, Vadhan and Viola (FOCS'04) are known in the non-uniform case.

REFERENCES

• 1: Shai Ben-David , Benny Chor , Oded Goldreich , Michael Luby, On the theory of average case complexity, Journal of Computer and System Sciences, v.44 n.2, p.193-219, April 1992 [doi>10.1016/0022-0000(92)90019-F]
• 2: 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
• 3: Dan Boneh , Richard J. Lipton, Amplification of weak learning under the uniform distribution, Proceedings of the sixth annual conference on Computational learning theory, p.347-351, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168372]
• 4: Goldreich, O., Nisan, N., and Wigderson, A. On Yao's XOR lemma. Tech. Rep. TR95-50, Electronic Colloquium on Computational Complexity, 1995.
• 5: Alexander Healy , Salil Vadhan , Emanuele Viola, Using nondeterminism to amplify hardness, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007389]
• 6: 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
• 7: R. Impagliazzo, A personal view of average-case complexity, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.134, June 19-22, 1995
• 8: Impagliazzo, R. Hardness as randomness: a survey of universal derandomization. In Proceedings of the International Congress of Mathematicians (2002), vol. 3, pp. 659--672.
• 9: Impagliazzo, R., and Levin, L. No better ways to generate hard NP instances than picking uniformly at random. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (1990), pp. 812--821.
• 10: 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]
• 11: Leonid A. Levin, One-way functions and Pseudorandom generators, Combinatorica, v.7 n.4, p.357-363, Dec, 1987 [doi>10.1007/BF02579323]
• 12: 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]
• 13: 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]
• 14: Spielman, D. Linear time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory 42, 6 (1996), 1723--1732.
• 15: 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]
• 16: 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
• 17: 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
• 18: Viola, E. Hardness vs. randomness within alternating time. In Proceedings of the 18th IEEE Conference on Computational Complexity (2003).
• 19: Yao, A. Theory and applications of trapdoor functions. In Proceedings of the 23th IEEE Symposium on Foundations of Computer Science (1982), pp. 80--91.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Theory

Keywords:
amplification of hardness, average-case complexity