Revision as of 02:45, 4 August 2008 edit Michael Hardy (talk \| contribs) Administrators 210,596 edits Please. What would you _expect_ a page titled "expected" to be? It's a disambiguation page. ← Previous edit		Revision as of 22:47, 13 August 2008 edit undo Erxnmedia (talk \| contribs) Autopatrolled, Extended confirmed users 3,864 edits Put in date order and add ref Next edit →
Line 4: The literature of average case complexity includes the following work: * Shai Ben-David, Benny Chor, [[Oded Goldreich]], and [[Michael Luby]]. On the theory of average case complexity. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 204–216. ACM, 1989.▼ * B. Selman D. Mitchell and H. Levesque. Hard and easy distributions of SAT problems. In Proceedings of the 10th National Conference on Artificial Intelligence, pages 459–465, 1992.▼ * John Franco. On the probabilistic performance of algorithms for the satisfiability problem. Information Processing Letters, 3:103–106, 1986. * [[Leonid Levin]]. Average case complete problems. SIAM J. Comput., 15:285–286, 1986.▼ * [[Philippe Flajolet]] and [[Jeffrey Vitter\|J.S. Vitter]]. Average-case analysis of algorithms and data structures. Technical report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France, August 1987. ▲* Shai Ben-David, Benny Chor, [[Oded Goldreich]], and [[Michael Luby]]. On the theory of average case complexity. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 204–216. ACM, 1989. * [[Yuri Gurevich]]. Average case completeness. Journal of Computer and`System Sciences, 42:346–398, 1991. ▲* B. Selman D. Mitchell and H. Levesque. Hard and easy distributions of SAT problems. In Proceedings of the 10th National Conference on Artificial Intelligence, pages 459–465, 1992. ▲* [[Leonid Levin]]. Average case complete problems. SIAM J. Comput., 15:285–286, 1986. * Rüdiger Reischuk and Christian Schindelhauer. Precise average case complexity. In 10th Annual Symposium on Theoretical Aspects of Computer Science, pages 650–661, 1993.▼ * Rainer Schuler and Tomoyuki Yamakami. Structural average case complexity. In Foundations of Software Technology and Theoretical Computer Science, pages 128–139. Springer-Verlag Lecture Notes in Computer Science #652, 1992. ▲* Rüdiger Reischuk and Christian Schindelhauer. Precise average case complexity. In 10th Annual Symposium on Theoretical Aspects of Computer Science, pages 650–661, 1993. * R. Venkatesan and S. Rajagopalan. Average case intractability of matrix and Diophantine problems. In 24th Annual ACM STOC, pages 632–642, May 1992. * [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.3850 Jim Cox, Lars Ericson, Bud Mishra. "The average case complexity of multilevel syllogistic", New York University, 1995] * [http://www-cse.ucsd.edu/~russell/average.ps Russell Impagliazzo, "A personal view of average-case complexity", UC San Diego, April 17, 1995] ==See also==

Average-case complexity: Difference between revisions