Circuit complexity: Difference between revisions

Revision as of 11:02, 27 March 2021

Revision as of 11:22, 27 March 2021

Line 72:

{{reflist|refs=

<ref name="Sipser_1997">{{cite book |author-last3=Sipser |author-first3=Michael |author-link3=Michael Sipser |date=1997 |title=Introduction to the theory of computation |publication-place=Boston, USA |publisher=PWS Pub. Co. |page=324}}</ref>

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

<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}}</ref>

<ref name="Furst-Saxe-Sipser_1984">{{cite journal |author-last1=Furst |author-first1=Merrick L. |author-last2=Saxe |author-first2=James B.Benjamin |author-link2=James B.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=Ryan |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=V. |author-last2=Impagliazzo |author-first2=R. |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=AlexanderAleksandr Aleksandrovich |author-last1=Razborov |author-link1=Aleksandr Aleksandrovich Razborov |author-first2=Stephen |author-last2=Rudich |title=Natural proofs |journal=[[Journal of Computer and System Sciences]] |volume=55 |pages=24–35 |date=1997}}</ref>

<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016">{{cite news |author-first1=Marco |author-last1=Carmosino |author-first2=Russell |author-last2=Impagliazzo |author-first3=Valentine |author-last3=Kabanets |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⁰ |date=2001 |pages=104–114 |book-title=Proc. 28th International Colloquium on Automata, Languages and Programming |publisher=Springer}}</ref>

<ref name="Raz-McKenzie_1999">{{cite journal |author-first1=Ran |author-last1=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 |editor-last=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 E.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 |author-last=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=AlexanderAleksandr A.Aleksandrovich |author-last=Razborov |author-link=AlexanderAleksandr Aleksandrovich Razborov |title=Lower bounds on the monotone complexity of some Boolean functions |date=1985 |journal=[[Soviet Mathematics of the USSR,- Doklady]] |issn=0197-6788 |volume=31 |pages=354–357}}</ref>

<ref name="Rossman_2008">{{cite conference |author-first=Benjamin |author-last=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=ACM[[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=Proc. 19th Annual ACM Symposium on Theory of Computing |publisher=ACM[[Association for Computing Machinery]] |doi=10.1145/28395.28404}}</ref>

<ref name="Alon-Boppana_1987">{{cite journal |author-first1=Noga |author-last1=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>

}}