Circuit complexity: Difference between revisions

Revision as of 17:44, 13 February 2024

Revision as of 20:25, 24 February 2024

Line 76:

{{reflist|refs=

<ref name="Sipser_1997">{{cite book |author-last=Sipser |author-first=Michael |author-link=Michael Sipser |date=1997 |title=Introduction to the theory of computation |publication-place=Boston, USA |edition=1 |isbn= |publisher=PWS Publishing Company |page=324}}</ref>

<ref name="Ajtai-Komlós-Szemerédi_1983">{{cite book

<ref name="Ajtai-Komlós-Szemerédi_1983">{{cite book |author-last1=Ajtai |author-first1=Miklós |author-link1=Miklós Ajtai |author-last2=Komlós |author-first2=János |author-last3=Szemerédi |author-first3=Endre |title=An 0(n log n) sorting network |journal=STOC '83 Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing |pages=1–9 |date=1983 |isbn=978-0-89791-099-6}}</ref>

| last1 = Ajtai | first1 = Miklós | author1-link = Miklós Ajtai

| last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)

| last3 = Szemerédi | first3 = Endre | author3-link = Endre Szemerédi

| contribution = An <math>O(n\log n)</math> sorting network

| doi = 10.1145/800061.808726

| pages = 1–9

| publisher = Association for Computing Machinery

| title = Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA

| year = 1983}}</ref>

<ref name="Ajtai_1983">{{cite journal |author-first=Miklós |author-last=Ajtai |author-link=Miklós Ajtai |title=<math>\Sigma^1_1</math>-formulae on finite structures |journal=Annals of Pure and Applied Logic |date=1983 |volume=24 |pages=1–24 |doi=10.1016/0168-0072(83)90038-6|doi-access= }}</ref>

<ref name="Furst-Saxe-Sipser_1984">{{cite journal |author-last1=Furst |author-first1=Merrick L. |author-last2=Saxe |author-first2=James Benjamin |author-link2=James Benjamin Saxe |author-last3=Sipser |author-first3=Michael Fredric |author-link3=Michael Fredric Sipser |doi=10.1007/BF01744431 |issue=1 |journal=[[Mathematical Systems Theory]] |mr=738749 |pages=13–27 |title=Parity, circuits, and the polynomial-time hierarchy |volume=17 |date=1984|s2cid=6306235 }}</ref>

Line 86 ⟶ 95:

<ref name="Hesse_2001">{{cite conference |author-first=William |author-last=Hesse |title=Division is in uniform TC⁰ |date=2001 |pages=104–114 |book-title=Proceedings of the 28th International Colloquium on Automata, Languages and Programming |publisher=[[Springer Verlag]]}}</ref>

<ref name="Raz-McKenzie_1999">{{cite journal |author-first1=Ran |author-last1=Raz |author-link1=Ran Raz |author-first2=Pierre |author-last2=McKenzie |title=Separation of the monotone NC hierarchy |journal=[[Combinatorica]] |volume=19 |number=3 |date=1999 |pages=403–435 |doi=10.1007/s004930050062}}</ref>

<ref name="Allender_1997">{{cite book

<ref name="Allender_1997">{{cite web |url=http://ftp.cs.rutgers.edu/pub/allender/fsttcs.pdf |title=Circuit Complexity before the Dawn of the New Millennium |date=1997 |editor-first=Eric Warren |editor-last=Allender |editor-link=Eric Warren Allender }}{{Dead link|date=December 2023 |bot=InternetArchiveBot |fix-attempted=yes }} [http://ftp.cs.rutgers.edu/pub/allender/fsttcs.96.slides.ps] {{Webarchive|url=https://web.archive.org/web/20160303221037/http://ftp.cs.rutgers.edu/pub/allender/fsttcs.96.slides.ps |date=2016-03-03 }} (NB. A 1997 survey of the field by Eric Allender.)</ref>

| last = Allender | first = Eric | author-link = Eric Allender

<ref name="Shannon_1949">{{cite journal |author-last=Shannon |author-first=Claude Elwood |author-link=Claude Elwood Shannon |title=The synthesis of two-terminal switching circuits |journal=[[Bell System Technical Journal]] |date=1949 |volume=28| number=1 |pages=59–98 |doi=10.1002/j.1538-7305.1949.tb03624.x}}</ref>

| editor1-last = Chandru | editor1-first = Vijay

| editor2-last = Vinay | editor2-first = V.

| contribution = Circuit complexity before the dawn of the new millennium

| doi = 10.1007/3-540-62034-6_33

| pages = 1–18

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Foundations of Software Technology and Theoretical Computer Science, 16th Conference, Hyderabad, India, December 18–20, 1996, Proceedings

| volume = 1180

| year = 1996}}</ref><ref name="Shannon_1949">{{cite journal |author-last=Shannon |author-first=Claude Elwood |author-link=Claude Elwood Shannon |title=The synthesis of two-terminal switching circuits |journal=[[Bell System Technical Journal]] |date=1949 |volume=28| number=1 |pages=59–98 |doi=10.1002/j.1538-7305.1949.tb03624.x}}</ref>

<ref name="Håstad_1987">{{cite book |author-first=Johan Torkel |author-last=Håstad |author-link=Johan Torkel Håstad |title=Computational limitations of small depth circuits |date=1987 |type=Ph.D. thesis |publisher=Massachusetts Institute of Technology |url=http://www.nada.kth.se/~johanh/thesis.pdf}}</ref>

<ref name="Razborov_1985">{{cite journal |author-first=Aleksandr Aleksandrovich |author-last=Razborov |author-link=Aleksandr Aleksandrovich Razborov |title=Lower bounds on the monotone complexity of some Boolean functions |date=1985 |journal=[[Soviet Mathematics - Doklady]] |issn=0197-6788 |volume=31 |pages=354–357}}</ref>