Content deleted Content added
→History: mention Shannon |
→References: include missing references |
||
Line 35:
==References==
*{{cite journal|first=Miklós|last=Ajtai|authorlink=Miklós Ajtai|title=<math>\Sigma^1_1</math>-formulae on finite structures|journal=Annals of Pure and Applied Logic|year=1983|volume=24|pages=1–24}}
*{{cite journal|first1=Noga|last1=Alon|first2=Ravi B.|last2=Boppana|title=The monotone circuit complexity of Boolean functions|journal=Combinatorica|volume=7|year=1987|number=1|pages=1–22}}
*{{cite journal|first1=Merrick L.|last1=Furst|first2=James B.|last2=Saxe|first3=Michael|last3=Sipser|title=Parity, circuits, and the polynomial-time hierarchy|journal=Mathematical Systems Theory|volume=17|number=1|pages=13–27|year=1984}}
*{{citation|first=Johan|last=Håstad|title=Computational limitations of small depth circuits|year=1987|publisher=Ph.D. thesis, Massachusetts Institute of Technology|postscript=.}}
*{{cite conference|first=William|last=Hesse|title=Division is in uniform TC<sup>0</sup>|year=2001|pages=104–114|booktitle=Proc. 28th International Colloquium on Automata, Languages and Programming|publisher=Springer}}
*{{cite journal|first1=Ran|last1=Raz|first2=Pierre|last2=McKenzie|title=Separation of the monotone NC hierarchy|journal=Combinatorica|volume=19|number=3|year=1999|pages=403–435}}
*{{cite journal|first=Alexander A.|last=Razborov|authorlink=Alexander Razborov|title=Lower bounds on the monotone complexity of some Boolean functions|year=1985|journal=Mathematics of the USSR, Doklady|volume=31|pages=354–357}}
*{{cite journal|last=Shannon|first=Claude E.|authorlink=Claude Shannon|title=The synthesis of two-terminal switching circuits|journal=Bell System Technical Journal|year=1949|volume=28|number=1|pages=59–98}}
*{{cite conference|first=Roman|last=Smolensky|title = Algebraic methods in the theory of lower bounds for Boolean circuit complexity|year=1987|pages=77–82|booktitle=Proc. 19th Annual ACM Symposium on Theory of Computing|publisher=ACM}}
*{{cite book|title=Introduction to Circuit Complexity: a Uniform Approach|last=Vollmer|first=Heribert|publisher=[[Springer Verlag]]|date=1999|isbn=3-540-64310-9}}▼
*{{cite book
|last = Wegener
Line 43 ⟶ 53:
|year = 1987
|isbn = 3-519-02107-2}} At the time an influental textbook on the subject, commonly known as the "Blue Book". Also available for [http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ download (PDF)] at the [[Electronic Colloquium on Computational Complexity]].
▲*{{cite book|title=Introduction to Circuit Complexity: a Uniform Approach|last=Vollmer|first=Heribert|publisher=[[Springer Verlag]]|date=1999|isbn=3-540-64310-9}}
*[http://www.math.tau.ac.il/~zwick/scribe-boolean.html Lecture notes for a course of Uri Zwick on circuit complexity]
*[http://ftp.cs.rutgers.edu/pub/allender/fsttcs.pdf ''Circuit Complexity before the Dawn of the New Millennium''], a 1997 survey of the field by Eric Allender [http://ftp.cs.rutgers.edu/pub/allender/fsttcs.96.slides.ps slides].
| |||