Content deleted Content added
Matthiaspaul (talk | contribs) improved refs |
Matthiaspaul (talk | contribs) →References: improved refs |
||
Line 76:
<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}}</ref>
<ref name="Santhanam_2007">{{cite conference |author-last=Santhanam |author-first=Rahul |url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.1811 |title=Circuit lower bounds for Merlin-Arthur classes |book-title=STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing |date=2007 |pages=275–283 |doi=10.1145/1250790.1250832 |citeseerx=10.1.1.92.4422}}</ref>
<ref name="Williams_2011">{{cite conference |author-last=Williams |author-first=Richard Ryan |author-link=Richard Ryan Williams |title=Non-Uniform ACC Circuit Lower Bounds |url=http://www.stanford.edu/~rrwill/acc-lbs.pdf |doi=10.1109/CCC.2011.36 |date=2011 |book-title=CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity |pages=115–125}}</ref>
<ref name="Kabanets-Impagliazzo_2004">{{cite journal |author-last1=Kabanets |author-first1=Valentine |author-link1=:d:Q102244985 |author-last2=Impagliazzo |author-first2=Russell Graham |author-link3=Russell Graham Impagliazzo |journal=Computational Complexity |doi=10.1007/s00037-004-0182-6 |title=Derandomizing polynomial identity tests means proving circuit lower bounds |pages=1–46 |volume=13 |number=1 |date=2004}}</ref>
<ref name="Razborov-Rudich_1997">{{cite news |author-first1=Aleksandr Aleksandrovich |author-last1=Razborov |author-link1=Aleksandr Aleksandrovich Razborov |author-first2=
<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016">{{cite news |author-first1=Marco |author-last1=Carmosino |author-first2=Russell Graham |author-last2=Impagliazzo |author-link2=Russell Graham Impagliazzo |author-first3=Valentine |author-last3=Kabanets |author-link3=:d:Q102244985 |author-first4=Antonina |author-last4=Kolokolova |title=Learning algorithms from natural proofs |journal=Computational Complexity Conference |date=2016}}</ref>
<ref name="Hesse_2001">{{cite conference |author-first=William |author-last=Hesse |title=Division is in uniform TC<sup>0</sup> |date=2001 |pages=104–114 |book-title=Proc. 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 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}} [http://ftp.cs.rutgers.edu/pub/allender/fsttcs.96.slides.ps] (NB. A 1997 survey of the field by Eric Allender.)</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>
<ref name="Rossman_2008">{{cite conference |author-first=Benjamin E. |author-last=Rossman |author-link=Benjamin E. Rossman |title=On the constant-depth complexity of k-clique |date=2008 |pages=721–730 |book-title=STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing |publisher=[[Association for Computing Machinery]] |doi=10.1145/1374376.1374480}}</ref>
<ref name="Smolensky_1987">{{cite conference |author-first=Roman |author-last=Smolensky |title=Algebraic methods in the theory of lower bounds for Boolean circuit complexity |date=1987 |pages=77–82 |book-title=Proceedings 19th Annual ACM Symposium on Theory of Computing |publisher=[[Association for Computing Machinery]] |doi=10.1145/28395.28404}}</ref>
<ref name="Alon-Boppana_1987">{{cite journal |author-first1=Noga |author-last1=Alon |author-link1=Noga Alon |author-first2=Ravi B. |author-last2=Boppana |title=The monotone circuit complexity of Boolean functions |journal=[[Combinatorica]] |volume=7 |date=1987 |number=1 |pages=1–22 |doi=10.1007/bf02579196 |citeseerx=10.1.1.300.9623}}</ref>
}}
| |||