Circuit complexity: Difference between revisions

Revision as of 18:45, 7 July 2023

Revision as of 18:47, 7 July 2023

Line 78:

<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=Steven |author-last2=Rudich |author-link2=Steven 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 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⁰ |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>