Revision as of 20:38, 21 May 2025 edit Cosmia Nebula (talk \| contribs) Extended confirmed users 11,297 edits →Further reading: more citations Tag: 2017 wikitext editor ← Previous edit		Revision as of 20:42, 21 May 2025 edit undo Cosmia Nebula (talk \| contribs) Extended confirmed users 11,297 edits →Further reading: one more. Also, removed Papadimitriou, Christos H. Computational Complexity, which contains exactly 1 page talking about average-case complexity! Tag: 2017 wikitext editor Next edit →
Line 106: Pedagogical presentations: * {{Cite journal \|last=Impagliazzo \|first=R. \|date=1995 \|title=A personal view of average-case complexity \|url=http://ieeexplore.ieee.org/document/514853/ \|publisher=IEEE Comput. Soc. Press \|pages=134–147 \|doi=10.1109/SCT.1995.514853 \|isbn=978-0-8186-7052-7}} * {{cite book \|last1=Arora \|first1=Sanjeev \|title=Computational Complexity: A Modern Approach \|last2=Barak \|first2=Boaz \|date=2009 \|publisher=Cambridge University Press \|___location=Cambridge ; New York \|chapter=18. Average case complexity: Levin’s theory}}▼ * {{cite book \|last1=Wang \|first1=Jie \|url=https://www.cs.uml.edu/~wang/acc-forum/avgcomp.pdf \|title=Complexity Theory: Retrospective II \|date=1997 \|publisher=Springer Science & Business Media \|editor-last1=Hemaspaandra \|editor-first1=Lane A. \|volume=2 \|pages=295–328 \|chapter=Average-case computational complexity theory \|editor-last2=Selman \|editor-first2=Alan L.}} * {{Citation \|last=Goldreich \|first=Oded \|title=Average Case Complexity, Revisited \|date=2011 \|work=Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation \|volume=6650 \|pages=422–450 \|editor-last=Goldreich \|editor-first=Oded \|url=https://www.wisdom.weizmann.ac.il/~oded/COL/aver.pdf \|place=Berlin, Heidelberg \|publisher=Springer Berlin Heidelberg \|doi=10.1007/978-3-642-22670-0_29 \|isbn=978-3-642-22669-4}} ▲* {{cite book \|last1=Arora \|first1=Sanjeev \|title=Computational Complexity: A Modern Approach \|last2=Barak \|first2=Boaz \|date=2009 \|publisher=Cambridge University Press \|___location=Cambridge ; New York \|chapter=18. Average case complexity: Levin’s theory}} The literature of average case complexity includes the following work: Line 208 ⟶ 209: \| url = http://www.cs.nyu.edu/csweb/Research/TechReports/TR1995-711/TR1995-711.pdf \| 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}}.~~ *Christos Papadimitriou (1994). Computational Complexity. Addison-Wesley. [[Category:Randomized algorithms]]

Average-case complexity: Difference between revisions