Average-case complexity: Difference between revisions

Revision as of 21:47, 26 November 2008

Revision as of 08:01, 10 February 2009

Line 10:

The literature of average case complexity includes the following work:

*{{citation

* John Franco. On the probabilistic performance of algorithms for the satisfiability problem. Information Processing Letters, 3:103–106, 1986.

| last = Franco | first = John

* [[Leonid Levin]]. Average case complete problems. SIAM J. Comput., 15:285–286, 1986.

| doi = 10.1016/0020-0190(86)90051-7

* [[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.

| issue = 2

* [[Yuri Gurevich]] and Saharon Shelah. Expected computation time for [[Hamiltonian path problem]]. SIAM Journal on Computing, volume 16, issue 3, June 1897, pages 486-502. ISSN: 0097-5397.

| journal = Information Processing Letters

* 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.

| pages = 103–106

* [[Yuri Gurevich]]. Average case completeness. Journal of Computer and`System Sciences, 42:346–398, 1991. See also [http://research.microsoft.com/~gurevich/Opera/76.pdf 1989 draft].

| title = On the probabilistic performance of algorithms for the satisfiability problem

* 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.

| volume = 23

* 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.

| year = 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.

*{{citation

* R. Venkatesan and S. Rajagopalan. Average case intractability of matrix and Diophantine problems. In 24th Annual ACM STOC, pages 632–642, May 1992.

| last = Levin | first = Leonid | author-link = Leonid Levin

* [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]

| doi = 10.1137/0215020

* [[Russell Impagliazzo]], [http://www-cse.ucsd.edu/~russell/average.ps "A personal view of average-case complexity", UC San Diego, April 17, 1995]

| issue = 1

| journal = SIAM Journal on Computing

| pages = 285–286

| title = Average case complete problems

| volume = 15

| year = 1986}}.

*{{citation

| last1 = Flajolet | first1 = Philippe | author1-link = Philippe Flajolet

| last2 = Vitter | first2 = J. S. | author2-link = Jeffrey Vitter

| date = August 1987

| publisher = Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France

| series = Tech. Report

| title = Average-case analysis of algorithms and data structures}}.

*{{citation

| last1 = Gurevich | first1 = Yuri | author1-link = Yuri Gurevich

| last2 = Shelah | first2 = Saharon

| doi = 10.1137/0216034

| issue = 3

| journal = SIAM Journal on Computing

| pages = 486–502

| title = Expected computation time for [[Hamiltonian path problem]]

| volume = 16

| year = 1987}}.

*{{citation

| last1 = Ben-David | first1 = Shai

| last2 = Chor | first2 = Benny

| last3 = Goldreich | first3 = Oded | author3-link = Oded Goldreich

| last4 = Luby | first4 = Michael | author4-link = Michael Luby

| contribution = On the theory of average case complexity

| pages = 204–216

| publisher = [[Association for Computing Machinery]]

| title = [[Symposium on Theory of Computing|Proc. 21st Annual Symposium on Theory of Computing]]

| year = 1989}}.

*{{citation

| last = Gurevich | first = Yuri | author-link = Yuri Gurevich

| doi = 10.1016/0022-0000(91)90007-R

| issue = 3

| journal = Journal of Computer and`System Sciences

| pages = 346–398

| title = Average case completeness

| volume = 42

| year = 1991}}. See also [http://research.microsoft.com/~gurevich/Opera/76.pdf 1989 draft].

*{{citation

| last1 = Selman | first1 = B.

| last2 = Mitchell | first2 = D.

| last3 = Levesque | first3 = H.

| contribution = Hard and easy distributions of SAT problems

| pages = 459–465

| title = Proc. 10th National Conference on Artificial Intelligence

| year = 1992}}.

*{{citation

| last1 = Schuler | first1 = Rainer

| last2 = Yamakami | first2 = Tomoyuki

| contribution = Structural average case complexity

| pages = 128–139

| publisher = Springer-Verlag

| series = Lecture Notes in Computer Science

| title = Proc. Foundations of Software Technology and Theoretical Computer Science

| volume = 652

| year = 1992}}.

*{{citation

| last1 = Reischuk | first1 = Rüdiger

| last2 = Schindelhauer | first2 = Christian

| contribution = Precise average case complexity

| pages = 650–661

| title = Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science

| year = 1993}}.

*{{citation

| last1 = Venkatesan | first1 = R.

| last2 = Rajagopalan | first2 = S.

| contribution = Average case intractability of matrix and Diophantine problems

| pages = 632–642

| publisher = [[Association for Computing Machinery]]

| title = [[Symposium on Theory of Computing|Proc. 24th Annual Symposium on Theory of Computing]]

| year = 1992}}.

*{{citation

| last1 = Cox | first1 = Jim

| last2 = Ericson | first2 = Lars

| last3 = Mishra | first3 = Bud

| doi = 10.1.1.36.3850

| publisher = New York University

| title = The average case complexity of multilevel syllogistic

| year = 1995}}.

*{{citation

| last = Impagliazzo | first = Russell | author-link = Russell Impagliazzo

| date = April 17, 1995

| publisher = [[University of California, San Diego]]

| title = A personal view of average-case complexity

| url = http://www-cse.ucsd.edu/~russell/average.ps}}.

==See also==