Abstract
A fundamental goal of computational complexity (and foundations of cryptography) is to find a polynomial-time samplable distribution (e.g., the uniform distribution) and a language in NTIME(f(n)) for some polynomial function f, such that the language is hard on the average with respect to this distribution, given that NP is worst-case hard (i.e. NP ≠ P, or \({\rm NP} \not \subseteq {\rm BPP}\)). Currently, no such result is known even if we relax the language to be in nondeterministic sub-exponential time. There has been a long line of research trying to explain our failure in proving such worst-case/average-case connections [FF93,Vio03,BT03,AGGM06]. The bottom line of this research is essentially that (under plausible assumptions) non-adaptive Turing reductions cannot prove such results.
In this paper we revisit the problem. Our first observation is that the above mentioned negative arguments extend to a non-standard notion of average-case complexity, in which the distribution on the inputs with respect to which we measure the average-case complexity of the language, is only samplable in super-polynomial time. The significance of this result stems from the fact that in this non-standard setting,[GSTS05] did show a worst-case/average-case connection. In other words, their techniques give a way to bypass the impossibility arguments. By taking a closer look at the proof of [GSTS05], we discover that the worst-case/average-case connection is proven by a reduction that ”almost” falls under the category ruled out by the negative result. This gives rise to an intriguing new notion of (almost black-box) reductions.
After extending the negative results to the non-standard average-case setting of [GSTS05], we ask whether their positive result can be extended to the standard setting, to prove some new worst-case/average-case connections. While we can not do that unconditionally, we are able to show that under a mild derandomization assumption, the worst-case hardness of NP implies the average-case hardness of NTIME(f(n)) (under the uniform distribution) where f is computable in quasi-polynomial time.
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
Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on NP-hardness. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 701–710. ACM Press, New York (2006)
Atserias, A.: Distinguishing SAT from polynomial-size circuits through black-box queries. In: Proceedings of the 21th Annual IEEE Conference on Computational Complexity, pp. 88–95. IEEE Computer Society Press, Los Alamitos (2006)
Barak, B.: How to go beyond black-box simulation barrier. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 106–115. IEEE Computer Society Press, Los Alamitos (2001)
Ben-David, S., Chor, B., Goldreich, O., Luby, M.: On the theory of average case complexity. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 379–386. ACM Press, New York (1990)
Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential simulation unless Exptime has publishable proofs. Computational Complexity 3, 307–318 (1993)
Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 308–317. IEEE Computer Society Press, Los Alamitos (2003)
Dubrov, B., Ishai, Y.: On the randomness complexity of efficient sampling. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 711–720. ACM Press, New York (2006)
Feigenbaum, J., Fortnow, L.: Random-self-reducibility of complete sets. SIAM Journal on Computing 22, 994–1005 (1993)
Gutfreund, D., Shaltiel, R., Ta-Shma, A.: if NP languages are hard in the worst-case then it is easy to find their hard instances. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 243–257. IEEE Computer Society Press, Los Alamitos (2005)
Håstad, J., Impagliazzo, R., Levin, L., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing 28(4), 1364–1396 (1999)
Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp. 230–235. IEEE Computer Society Press, Los Alamitos (1989)
Impagliazzo, R., Levin, L.: No better ways of finding hard NP-problems than picking uniformly at random. In: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pp. 812–821. IEEE Computer Society Press, Los Alamitos (1990)
Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of the 10th Annual Conference on Structure in Complexity Theory, pp. 134–147 (1995)
Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 220–229. ACM Press, New York (1997)
Impagliazzo, R., Wigderson, A.: Randomness vs. time: de-randomization under a uniform assumption. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 734–743. IEEE Computer Society Press, Los Alamitos (1998)
Kabanets, V.: Easiness assumptions and hardness tests: Trading time for zero error. Journal of Computer and System Sciences 63(2), 236–252 (2001)
Levin, L.: Average case complete problems. SIAM Journal on Computing 15(1), 285–286 (1986)
Nisan, N., Wigderson, A.: Hardness vs. randomness. Journal of Computer and System Sciences 49, 149–167 (1994)
Trevisan, L.: On uniform amplification of hardness in NP. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 31–38. ACM Press, New York (2005)
Trevisan, L., Vadhan, S.: Pseudorandomness and average-case complexity via uniform reductions. In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, pp. 129–138. IEEE Computer Society Press, Los Alamitos (2002)
Viola, E.: Hardness vs. randomness within alternating time. In: Proceedings of the 18th Annual IEEE Conference on Computational Complexity, pp. 53–62. IEEE Computer Society Press, Los Alamitos (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gutfreund, D., Ta-Shma, A. (2007). Worst-Case to Average-Case Reductions Revisited. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2007 2007. Lecture Notes in Computer Science, vol 4627. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74208-1_41
Download citation
DOI: https://doi.org/10.1007/978-3-540-74208-1_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74207-4
Online ISBN: 978-3-540-74208-1
eBook Packages: Computer ScienceComputer Science (R0)