zbMATH — the first resource for mathematics

Notes on Levin’s theory of average-case complexity. (English) Zbl 1343.68111
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 233-247 (2011).
Summary: In [SIAM J. Comput. 15, 285–286 (1986; Zbl 0589.68032)] L. A. Levin initiated a theory of average-case complexity. We provide an exposition of the basic definitions suggested by Levin, and discuss some of the considerations underlying these definitions.
For the entire collection see [Zbl 1220.68005].

68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDF BibTeX Cite
Full Text: DOI
[1] Ben-David, S., Chor, B., Goldreich, O., Luby, M.: On the Theory of Average Case Complexity. Journal of Computer and system Sciences 44(2), 193–219 (1992) · Zbl 0762.68027
[2] Cook, S.A.: The Complexity of Theorem Proving Procedures. In: Proc. 3rd ACM Symp. on Theory of Computing, pp. 151–158 (1971)
[3] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979) · Zbl 0411.68039
[4] Goldreich, O.: Towards a Theory of Average Case Complexity (a survey). TR-531, Computer Science Department, Technion, Haifa, Israel (March 1988)
[5] Goldreich, O.: Foundation of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001) · Zbl 1007.94016
[6] Goldreich, O.: Foundation of Cryptography: Basic Applications. Cambridge University Press, Cambridge (2004) · Zbl 1068.94011
[7] Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008) · Zbl 1154.68056
[8] Goldreich, O.: Average Case Complexity, Revisited. In: Goldreich, O., et al. (eds.) Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 424–452. Springer, Heidelberg (2011) · Zbl 1343.68114
[9] Gurevich, Y.: Complete and Incomplete Randomized NP Problems. In: Proc. of the 28th IEEE Symp. on Foundation of Computer Science, pp. 111–117 (1987)
[10] Gurevich, Y.: Matrix Decomposition Problem is Complete for the Average Case. In: Proc. of the 31st IEEE Symp. on Foundation of Computer Science, pp. 802–811 (1990)
[11] Gurevich, Y., McCauley, D.: Average Case Complete Problems (1987) (preprint)
[12] Hartmanis, J., Stearns, R.E.: On the Computational Complexity of of Algorithms. Transactions of the AMS 117, 285–306 (1965) · Zbl 0131.15404
[13] Impagliazzo, R., Levin, L.A.: No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. In: Proc. of the 31st IEEE Symp. on Foundation of Computer Science, pp. 812–821 (1990)
[14] Johnson, D.S.: The NP-Complete Column – an ongoing guide. Jour. of Algorithms 4, 284–299 (1984) · Zbl 0546.68025
[15] Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
[16] Karp, R.M.: Probabilistic Analysis of Algorithms. (1986) (manuscript)
[17] Levin, L.A.: Universal Search Problems. Problemy Peredaci Informacii 9, 115–116 (1973); Translated in problems of Information Transmission 9, 265–266 · Zbl 0313.02026
[18] Levin, L.A.: Average Case Complete Problems. SIAM Jour. of Computing 15, 285–286 (1986); Extended abstract appeared In: 16th STOC (1984) · Zbl 0589.68032
[19] Levin, L.A.: One-Way Function and Pseudorandom Generators. In: Proc. 17th ACM Symp. on Theory of Computing, pp. 363–365 (1985)
[20] Levin, L.A.: Homogeneous Measures and Polynomial Time Invariants. In: Proc. 29th IEEE Symp. on Foundations of Computer Science, pp. 36–41 (1988)
[21] Livne, N.: All Natural NPC Problems Have Average-Case Complete Versions. Computational Complexity (2006) (to appear); Preliminary version in ECCC, TR06-122 (2006)
[22] Venkatesan, R., Levin, L.A.: Random Instances of a Graph Coloring Problem are Hard. In: Proc. 20th ACM Symp. on Theory of Computing, pp. 217–222 (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.