Average-case Complexity - Literature

Literature

The literature of average case complexity includes the following work:

  • Franco, John (1986), "On the probabilistic performance of algorithms for the satisfiability problem", Information Processing Letters 23 (2): 103–106, doi:10.1016/0020-0190(86)90051-7.
  • Levin, Leonid (1986), "Average case complete problems", SIAM Journal on Computing 15 (1): 285–286, doi:10.1137/0215020.
  • Flajolet, Philippe; Vitter, J. S. (August 1987), Average-case analysis of algorithms and data structures, Tech. Report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France.
  • Gurevich, Yuri; Shelah, Saharon (1987), "Expected computation time for Hamiltonian path problem", SIAM Journal on Computing 16 (3): 486–502, doi:10.1137/0216034.
  • Ben-David, Shai; Chor, Benny; Goldreich, Oded; Luby, Michael (1989), "On the theory of average case complexity", Proc. 21st Annual Symposium on Theory of Computing, Association for Computing Machinery, pp. 204–216.
  • Gurevich, Yuri (1991), "Average case completeness", Journal of Computer and`System Sciences 42 (3): 346–398, doi:10.1016/0022-0000(91)90007-R. See also 1989 draft.
  • Selman, B.; Mitchell, D.; Levesque, H. (1992), "Hard and easy distributions of SAT problems", Proc. 10th National Conference on Artificial Intelligence, pp. 459–465.
  • Schuler, Rainer; Yamakami, Tomoyuki (1992), "Structural average case complexity", Proc. Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, 652, Springer-Verlag, pp. 128–139.
  • Reischuk, Rüdiger; Schindelhauer, Christian (1993), "Precise average case complexity", Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science, pp. 650–661.
  • Venkatesan, R.; Rajagopalan, S. (1992), "Average case intractability of matrix and Diophantine problems", Proc. 24th Annual Symposium on Theory of Computing, Association for Computing Machinery, pp. 632–642.
  • Cox, Jim; Ericson, Lars; Mishra, Bud (1995), The average case complexity of multilevel syllogistic, Technical Report TR1995-711, New York University Computer Science Department, http://www.cs.nyu.edu/csweb/Research/TechReports/TR1995-711/TR1995-711.pdf.
  • Impagliazzo, Russell (April 17, 1995), A personal view of average-case complexity, University of California, San Diego, http://www-cse.ucsd.edu/~russell/average.ps.
  • Paul E. Black, "Θ", in Dictionary of Algorithms and Data StructuresPaul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.Retrieved Feb. 20/09.
  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing.

Read more about this topic:  Average-case Complexity

Famous quotes containing the word literature:

    “From the point of view of literature Mr. Kipling is a genius who drops his aspirates. From the point of view of life, he is a reporter who knows vulgarity better than any one has ever known it.”
    —Oscar Wilde (1854–1900)

    “Nothing could be more inappropriate to American literature than its English source since the Americans are not British in sensibility.”
    —Wallace Stevens (1879–1955)

    “A people’s literature is the great textbook for real knowledge of them. The writings of the day show the quality of the people as no historical reconstruction can.”
    —Edith Hamilton (1867–1963)