Difference between revisions of "Complexity Zoo References"

From Complexity Zoo
Jump to navigation Jump to search
(→‎C: Added CGQ+24)
 
(74 intermediate revisions by 17 users not shown)
Line 78: Line 78:
 
PDQP/qpoly = ALL,
 
PDQP/qpoly = ALL,
 
arXiv:[https://arxiv.org/abs/1805.08577 1805.08577].
 
arXiv:[https://arxiv.org/abs/1805.08577 1805.08577].
 +
 +
<span id="aboe08" style="color:maroon">[ABOE08]</span>
 +
D. Aharonov, M. Ben-Or, E. Eban.
 +
Interactive Proofs for Quantum Computations,
 +
arXiv:[https://arxiv.org/abs/0810.5375 0810.5375].
  
 
<span id="ak06" style="color:maroon">[AK06]</span>
 
<span id="ak06" style="color:maroon">[AK06]</span>
Line 138: Line 143:
 
See also "A compendium of NP optimization problems" (P. Crescenzi and V. Kann, eds.),
 
See also "A compendium of NP optimization problems" (P. Crescenzi and V. Kann, eds.),
 
[http://www.nada.kth.se/~viggo/wwwcompendium/ http://www.nada.kth.se/~viggo/wwwcompendium/].
 
[http://www.nada.kth.se/~viggo/wwwcompendium/ http://www.nada.kth.se/~viggo/wwwcompendium/].
 +
 +
<span id="acjr21" style="color:maroon">[ACJ+21]</span>
 +
M. Arenas, L. A. Croquevielle, R. Jayaram, and C. Riveros. #NFA admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes.
 +
<i>Journal of the ACM</i> 68(6):48:1-48:40, 2021.
  
 
<span id="adh97" style="color:maroon">[ADH97]</span>
 
<span id="adh97" style="color:maroon">[ADH97]</span>
Line 328: Line 337:
 
<i>ACM Transactions on Algorithms (TALG)</i> 2(2): 153–177, 2006.
 
<i>ACM Transactions on Algorithms (TALG)</i> 2(2): 153–177, 2006.
 
[http://dx.doi.org/10.1145/1150334.1150336 doi:10.1145/1150334.1150336]
 
[http://dx.doi.org/10.1145/1150334.1150336 doi:10.1145/1150334.1150336]
 +
 +
<span id="ani+23" style="color:maroon">[Ani+23]</span>
 +
Joshua Ani et al.
 +
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines. 2023.
 +
arxiv: [https://arxiv.org/abs/2306.01193]
  
 
<span id="an02" style="color:maroon">[AN02]</span>
 
<span id="an02" style="color:maroon">[AN02]</span>
Line 455: Line 469:
 
The quantum challenge to structural complexity theory.
 
The quantum challenge to structural complexity theory.
 
Proceedings of Structure in Complexity Theory, 1992, 132--137.
 
Proceedings of Structure in Complexity Theory, 1992, 132--137.
 +
[https://doi.ieeecomputersociety.org/10.1109/SCT.1992.215388 DOI]
  
 
<span id="bbb97" style="color:maroon">[BBB+97]</span>
 
<span id="bbb97" style="color:maroon">[BBB+97]</span>
Line 496: Line 511:
 
<i>Journal of Computer and System Sciences</i> 44(2):193-219, 1992.
 
<i>Journal of Computer and System Sciences</i> 44(2):193-219, 1992.
 
[http://www.cs.technion.ac.il/~shai/aver.pdf http://www.cs.technion.ac.il/~shai/aver.pdf]
 
[http://www.cs.technion.ac.il/~shai/aver.pdf http://www.cs.technion.ac.il/~shai/aver.pdf]
 +
 +
<span id="bckls14" style="color:maroon">[BCK+14]</span>
 +
H. Buhrman, R. Cleve, M. Koucky, B. Loff, and F. Speelman.
 +
Computing with a full memory: catalytic space,
 +
<i>Symposium on the Theory of Computing (STOC)</i> 857-866, 2014.
  
 
<span id="bcs97" style="color:maroon">[BCS+97]</span>
 
<span id="bcs97" style="color:maroon">[BCS+97]</span>
Line 511: Line 531:
 
Parallel computations for well-endowed rings and space-bounded probabilistic machines,
 
Parallel computations for well-endowed rings and space-bounded probabilistic machines,
 
<i>Information and Control</i> 58:113-136, 1983.
 
<i>Information and Control</i> 58:113-136, 1983.
 +
 +
<span id="bchtv17" style="color:maroon">[BCHTV17]</span>
 +
A. Bouland, L. Chen, D. Holden, J. Thaler, and P. N. Vasudevan.
 +
On the Power of Statistical Zero Knowledge,
 +
<i>Foundations of Computer Science</i>, pp. 708-719, 2017.
 +
arXiv:[https://arxiv.org/pdf/1609.02888].
  
 
<span id="bcy11" style="color:maroon">[BCY11]</span>
 
<span id="bcy11" style="color:maroon">[BCY11]</span>
Line 800: Line 826:
 
B. Borchert and F. Stephan.
 
B. Borchert and F. Stephan.
 
Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.
 
Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.
−
MLQ Math. Log. Q. 46 (2000), no. 4, 489--504
+
MLQ Math. Log. Q. 46 (2000), no. 4, 489--504, 2000. Also Proc. 5th Kurt Gödel Colloq. KGS 1997, Springer LNCS 1289, pp. 114-127.
−
[http://math.uni-heidelberg.de/logic/bb/papers/Rice.ps http://math.uni-heidelberg.de/logic/bb/papers/Rice.ps]
+
[https://doi.org/10.1002/1521-3870(200010)46:4%3C489::AID-MALQ489%3E3.0.CO;2-F MLQ] [https://doi.org/10.1007/3-540-63385-5_37 KGS 1997]
  
 
<span id="bs90" style="color:maroon">[BS90]</span>
 
<span id="bs90" style="color:maroon">[BS90]</span>
Line 850: Line 876:
 
  |link=http://math.ucsd.edu/~sbuss/ResearchWeb/Boolean3/index.html
 
  |link=http://math.ucsd.edu/~sbuss/ResearchWeb/Boolean3/index.html
 
}}
 
}}
 +
 +
<span id="buss17" style="color:maroon">[Buss17]</span>
 +
S. Buss.
 +
Uniform Proofs of ACC Representations,
 +
<i>Archive for Mathematical Logic</i> 56(5–6):639–669, 2017.
  
 
<span id="bv97" style="color:maroon">[BV97]</span>
 
<span id="bv97" style="color:maroon">[BV97]</span>
Line 890: Line 921:
 
Lecture Notes in Computer Science, vol 247, p148-158, 1987.
 
Lecture Notes in Computer Science, vol 247, p148-158, 1987.
  
−
<span id="can96" style="color:maroon">[Can96]</span>
+
<span id="cch01" style="color:maroon">[CCH+01]</span>
−
R. Canetti.
+
J.-Y. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara.
−
More on BPP and the polynomial-time hierarchy,
+
Some Karp-Lipton-type theorems based on S<sub>2</sub>,
−
<i>Information Processing Letters</i> 57:237-241, 1996.
+
University of Rochester Computer Science Technical Report TR-759, November 2001.
  
 
<span id="cc93" style="color:maroon">[CC93]</span>
 
<span id="cc93" style="color:maroon">[CC93]</span>
Line 905: Line 936:
 
<i>Journal of Computer and System Sciences</i> 54(3):465-474, 1997.
 
<i>Journal of Computer and System Sciences</i> 54(3):465-474, 1997.
  
−
<span id="cs12" style="color:maroon">[CS12]</span>
+
<span id="cf91" style="color:maroon">[CF91]</span>
−
André Chailloux and Or Sattath.
+
J.-Y. Cai and M. Furst.
−
The Complexity of the Separable Hamiltonian Problem,
+
PSPACE survives constant-width bottlenecks,
−
<i>Proceedings of the 2012 IEEE Annual Conference on Computational Complexity (CCC)</i>, pp. 32-41, 2012. [https://arxiv.org/abs/1111.5247 arXiv: 1111.5247].
+
<i>International Journal of Foundations of Computer Science</i> 2(1):67-76, 1991.
 +
 
 +
<span id="co22" style="color:maroon">[CO22]</span>
 +
Wojciech Czerwiński and Łukasz Orlikowski
 +
Reachability in vector addition systems is Ackermann-complete,
 +
<i>Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science</i>, pages 1229–1240, 2022
 +
arXiv: [https://arxiv.org/abs/2104.13866]
  
−
<span id="ccd03" style="color:maroon">[CCD+03]</span>
+
<span id="can96" style="color:maroon">[Can96]</span>
−
A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman.
+
R. Canetti.
−
Exponential algorithmic speedup by quantum walk,
+
More on BPP and the polynomial-time hierarchy,
−
<i>Proceedings of ACM Symposium on Theory of Computing</i>, pp. 59-68, 2003.
+
<i>Information Processing Letters</i> 57:237-241, 1996.
−
arXiv:[http://arxiv.org/abs/quant-ph/0209131 quant-ph/0209131].
 
  
 
<span id="ccg94" style="color:maroon">[CCG+94]</span>
 
<span id="ccg94" style="color:maroon">[CCG+94]</span>
Line 921: Line 957:
 
<i>Journal of Computer and System Sciences</i> 49(1):24-39, 1994.
 
<i>Journal of Computer and System Sciences</i> 49(1):24-39, 1994.
  
−
<span id="cch01" style="color:maroon">[CCH+01]</span>
+
<span id="cgqtz24" style="color:maroon">[CGQ+24]</span>
−
J.-Y. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara.
+
Z. Chen, J. A. Grochow, Y. Qiao, G. Tang, and C. Zhang.
−
Some Karp-Lipton-type theorems based on S<sub>2</sub>,
+
On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups.
−
University of Rochester Computer Science Technical Report TR-759, November 2001.
+
<i>Proc. ITCS '24</i> [https://doi.org/10.4230/LIPIcs.ITCS.2024.31 doi:10.4230/LIPIcs.ITCS.2024.31]
  
−
<span id="cd05" style="color:maroon">[CD05]</span>
+
<span id="cs12" style="color:maroon">[CS12]</span>
−
X. Chen and X. Deng
+
André Chailloux and Or Sattath.
−
3-NASH is PPAD-Complete,
+
The Complexity of the Separable Hamiltonian Problem,
−
ECCC [http://eccc.uni-trier.de/eccc-reports/2005/TR05-134/ TR05-134].
+
<i>Proceedings of the 2012 IEEE Annual Conference on Computational Complexity (CCC)</i>, pp. 32-41, 2012. [https://arxiv.org/abs/1111.5247 arXiv: 1111.5247].
 +
 
 +
<span id="ctw13" style="color:maroon">[CTW13]</span>
 +
A. Chattopadhyay, J. Tor&aacute;n, F. Wagner.
 +
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism
 +
<i>ACM Transactions on Computation Theory</i> Volume 5, Issue 4, November 2013, pp.1--13. [https://doi.org/10.1145/2540088]
 +
 
 +
<span id="cw22" style="color:maroon">[CW22]</span>
 +
B. Chapman and R. Williams.
 +
Smaller ACC0 Circuits for Symmetric Functions,
 +
<i>13th Innovations in Theoretical Computer Science Conference (ITCS 2022)</i>, pp. 38:1--38:19, 2022. [https://arxiv.org/abs/2107.04706  arXiv:2107.04706], [https://drops.dagstuhl.de/opus/volltexte/2022/15634  LIPIcs-ITCS-2022-38].
  
 
<span id="che16" style="color:maroon">[Che16]</span>
 
<span id="che16" style="color:maroon">[Che16]</span>
Line 935: Line 981:
 
A Note on Oracle Separations for BQP,
 
A Note on Oracle Separations for BQP,
 
arXiv:[http://arxiv.org/abs/1605.00619 1605.00619].
 
arXiv:[http://arxiv.org/abs/1605.00619 1605.00619].
 +
 +
<span id="cd05" style="color:maroon">[CD05]</span>
 +
X. Chen and X. Deng
 +
3-NASH is PPAD-Complete,
 +
ECCC [http://eccc.uni-trier.de/eccc-reports/2005/TR05-134/ TR05-134].
 +
 +
<span id="ccd03" style="color:maroon">[CCD+03]</span>
 +
A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman.
 +
Exponential algorithmic speedup by quantum walk,
 +
<i>Proceedings of ACM Symposium on Theory of Computing</i>, pp. 59-68, 2003.
 +
arXiv:[http://arxiv.org/abs/quant-ph/0209131 quant-ph/0209131].
  
 
<span id="cdl01" style="color:maroon">[CDL01]</span>
 
<span id="cdl01" style="color:maroon">[CDL01]</span>
Line 940: Line 997:
 
Division in logspace-uniform NC<sub>1</sub>,
 
Division in logspace-uniform NC<sub>1</sub>,
 
<i>Theoretical Informatics and Applications</i> 35(3):259, 2001.
 
<i>Theoretical Informatics and Applications</i> 35(3):259, 2001.
−
 
−
<span id="cf91" style="color:maroon">[CF91]</span>
 
−
J.-Y. Cai and M. Furst.
 
−
PSPACE survives constant-width bottlenecks,
 
−
<i>International Journal of Foundations of Computer Science</i> 2(1):67-76, 1991.
 
  
 
{{Reference
 
{{Reference
Line 1,026: Line 1,078:
 
On pseudorandom generators in NC<sup>0</sup>,
 
On pseudorandom generators in NC<sup>0</sup>,
 
<i>Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS)</i>, pp. 272-284, 2001.
 
<i>Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS)</i>, pp. 272-284, 2001.
 +
 +
<span id="cm16" style="color:maroon">[CM16]</span>
 +
T. Cubitt and A. Montanaro.
 +
Complexity Classification of Local Hamiltonian Problems.
 +
<i>SIAM Journal on Computing</i> 45:2, 2016.
 +
doi:[https://epubs.siam.org/doi/abs/10.1137/140998287 10.1137/140998287].
 +
 +
<span id="cmp18" style="color:maroon">[CMP18]</span>
 +
T. Cubitt, A. Montanaro, and S. Piddock.
 +
Universal quantum Hamiltonians.
 +
<i>PNAS</i> 115:38, 2018.
 +
doi:[https://www.pnas.org/doi/full/10.1073/pnas.1804949115 10.1073/pnas.1804949115].
  
 
{{Reference
 
{{Reference
Line 1,151: Line 1,215:
 
<span id="dam90" style="color:maroon">[Dam90]</span>
 
<span id="dam90" style="color:maroon">[Dam90]</span>
 
C. Damm.
 
C. Damm.
−
Problems complete for L,
+
Problems complete for ⊕L,
 
<i>Information Processing Letters</i> 36:247-250, 1990.
 
<i>Information Processing Letters</i> 36:247-250, 1990.
 +
[https://doi.org/10.1016/0020-0190(90)90150-V doi:10.1016/0020-0190(90)90150-V]
 +
 +
<span id="dam91" style="color:maroon">[Dam91]</span>
 +
C. Damm.
 +
DET=L<sup>(#L)</sup>,
 +
Technical Report Informatik-Preprint 8, Fachbereich Informatik der Humboldt–Universit ̈at zu Berlin, 1991.
  
 
<span id="dc89" style="color:maroon">[DC89]</span>
 
<span id="dc89" style="color:maroon">[DC89]</span>
Line 1,158: Line 1,228:
 
Complexity theory of parallel time and hardware,
 
Complexity theory of parallel time and hardware,
 
<i>Information and Computation</i> 80:205-226, 1989.
 
<i>Information and Computation</i> 80:205-226, 1989.
 +
[https://doi.org/10.1016/0890-5401(89)90009-6 doi:10.1016/0890-5401(89)90009-6]
  
 
<span id="ddp98" style="color:maroon">[DDP+98]</span>
 
<span id="ddp98" style="color:maroon">[DDP+98]</span>
Line 1,163: Line 1,234:
 
Image density is complete for non-interactive SZK,
 
Image density is complete for non-interactive SZK,
 
<i>Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP)</i>, Lecture Notes in Computer Science, pp. 784-795, 1998.
 
<i>Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP)</i>, Lecture Notes in Computer Science, pp. 784-795, 1998.
 +
[https://doi.org/10.1007/BFb0055102 doi:10.1007/BFb0055102]
 
(Note: Some results in the paper were later retracted.)
 
(Note: Some results in the paper were later retracted.)
  
Line 1,168: Line 1,240:
 
M. I. Dekhtyar.
 
M. I. Dekhtyar.
 
On the relativization of deterministic and nondeterministic complexity classes,
 
On the relativization of deterministic and nondeterministic complexity classes,
−
<i>Mathematical Foundations of Computer Science</i>, pp. 255-259, Springer LNCS 45, 1976.
+
<i>Mathematical Foundations of Computer Science</i> (MFCS '76), pp. 255-259, Springer LNCS 45, 1976.
 +
[https://doi.org/10.1007/3-540-07854-1_183 doi:10.1007/3-540-07854-1_183]
 +
 
 +
<span id="dgpv20" style="color:maroon">[DGPV20]</span>
 +
P. Dixon, S. Gayen, A. Pavan, N. V. Vinodchandran.
 +
Perfect Zero Knowledge: New Upperbounds and Relativized Separations,
 +
<i>Theory of Cryptography Conference</i> (TCC '20), pp. 768, 2020.
 +
ePrint:[https://eprint.iacr.org/2020/768]
 +
[https://doi.org/10.1007/978-3-030-64375-1_24 doi:10.1007/978-3-030-64375-1_24]
  
 
<span id="df97" style="color:maroon">[DF97]</span>
 
<span id="df97" style="color:maroon">[DF97]</span>
Line 1,174: Line 1,254:
 
Threshold dominating sets and an improved characterization of W[2],
 
Threshold dominating sets and an improved characterization of W[2],
 
<i>Theoretical Computer Science</i> 189, 1997.
 
<i>Theoretical Computer Science</i> 189, 1997.
 +
[https://doi.org/10.1016/S0304-3975(97)00101-1 doi:10.1016/S0304-3975(97)00101-1]
  
 
<span id="df99" style="color:maroon">[DF99]</span>
 
<span id="df99" style="color:maroon">[DF99]</span>
Line 1,179: Line 1,260:
 
<i>Parameterized Complexity</i>,
 
<i>Parameterized Complexity</i>,
 
Springer-Verlag Monographs in Computer Science, 1999.
 
Springer-Verlag Monographs in Computer Science, 1999.
 +
[https://doi.org/10.1007/978-1-4612-0515-9 doi:10.1007/978-1-4612-0515-9]
  
 
<span id="dft96" style="color:maroon">[DFT96]</span>
 
<span id="dft96" style="color:maroon">[DFT96]</span>
Line 1,184: Line 1,266:
 
On the parameteric complexity of relational database queries and a sharper characterization of W[1],
 
On the parameteric complexity of relational database queries and a sharper characterization of W[1],
 
<i>Combinatorics, Complexity, and Logic</i>, Proceedings of DMTCS'96, Springer-Verlag, pp. 194-213, 1996.
 
<i>Combinatorics, Complexity, and Logic</i>, Proceedings of DMTCS'96, Springer-Verlag, pp. 194-213, 1996.
 +
[http://mrfellows.net/papers/C33-relationaldatabase.ps Author's website version]
  
 
<span id="dft98" style="color:maroon">[DFT96]</span>
 
<span id="dft98" style="color:maroon">[DFT96]</span>
 
R. G. Downey, M. R. Fellows, and U. Taylor.
 
R. G. Downey, M. R. Fellows, and U. Taylor.
−
Parameterized circuit complexity and the W
+
Parameterized circuit complexity and the W hierarchy.
−
hierarchy.
 
 
<i>Theoret. Computer Sci.</i>, 191(1–2):97–115, January 1998.
 
<i>Theoret. Computer Sci.</i>, 191(1–2):97–115, January 1998.
 +
[https://doi.org/10.1016/S0304-3975(96)00317-9 doi:10.1016/S0304-3975(96)00317-9]
  
 
<span id="dgp05" style="color:maroon">[DGP05]</span>
 
<span id="dgp05" style="color:maroon">[DGP05]</span>
 
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou
 
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou
−
The Complexity of Computing a Nash Equilibrium, online: [http://www.cs.berkeley.edu/~christos/papers/ppad.ps ppad.ps], sep. 2005.
+
The Complexity of Computing a Nash Equilibrium,
 +
<i>SIAM J. Comput.</i> 39(1):195-259, 2009.
 +
[https://doi.org/10.1137/070699652 doi:10.1137/070699652]
 +
Originally appeared in [https://doi.org/10.1145/1132516.1132527 STOC 2006], [https://people.csail.mit.edu/costis/simplified.pdf Author's website conference version].
  
 
<span id="dhi02" style="color:maroon">[DHI02]</span>
 
<span id="dhi02" style="color:maroon">[DHI02]</span>
 
W. van Dam, S. Hallgren, and L. Ip.
 
W. van Dam, S. Hallgren, and L. Ip.
 
Quantum algorithms for hidden shift problems,
 
Quantum algorithms for hidden shift problems,
−
arXiv:[http://arxiv.org/abs/quant-ph/0211140 quant-ph/0211140], 2002.
+
<i>SIAM J. Comput.</i> 36(3):763-778, 2006.
 +
[https://doi.org/10.1137/S009753970343141X doi:10.1137/S009753970343141X]
 +
Originally appeared on arXiv:[http://arxiv.org/abs/quant-ph/0211140 quant-ph/0211140] and SODA 2003.
  
 
<span id="dp05" style="color:maroon">[DP05]</span>
 
<span id="dp05" style="color:maroon">[DP05]</span>
−
C. Daskalakis and C. H. Papadimitriou
+
C. Daskalakis and C. H. Papadimitriou.
−
The Complexity of Computing a Nash Equilibrium, online: [http://www.cs.berkeley.edu/~christos/papers/3players.pdf 3players.pdf], nov. 2005.
+
Three-player games are hard,
 +
ECCC [https://eccc.weizmann.ac.il//eccc-reports/2005/TR05-139/ TR05-139], 2005.
  
−
{{Reference-ECCC
+
<span id="DP08" style="color:maroon">[DP08]</span>
−
    |tag=DP08 |year=2008 |date=Feb 28 |eccc-num=TR08-014
+
M. David and T. Pitassi.
−
    |authors=M. David and T. Pitassi
+
Separating NOF communication complexity classes RP and NP.
−
    |title=Separating NOF communication complexity classes RP and NP
+
ECCC [https://eccc.weizmann.ac.il/eccc-reports/2008/TR08-014/index.html TR08-014] and arXiv:[https://doi.org/10.48550/arXiv.0802.3860 0802.3860 [cs.CC]], 2008.
−
}}
 
  
 
<span id="dw86" style="color:maroon">[DW86]</span>
 
<span id="dw86" style="color:maroon">[DW86]</span>
Line 1,214: Line 1,302:
 
Membership for growing context-sensitive grammars is polynomial,
 
Membership for growing context-sensitive grammars is polynomial,
 
<i>Journal of Computer and System Sciences</i> 33:456-472, 1986.
 
<i>Journal of Computer and System Sciences</i> 33:456-472, 1986.
 +
[https://doi.org/10.1016/0022-0000(86)90062-0 doi:10.1016/0022-0000(86)90062-0]
 +
Originally appeared in [https://doi.org/10.1007/BFb0022661 CAAP 1986]
  
 
===== E =====
 
===== E =====
Line 1,221: Line 1,311:
 
Paths, trees, and flowers,
 
Paths, trees, and flowers,
 
<i>Canadian Journal of Mathematics</i> 17(3):449-467, 1965.
 
<i>Canadian Journal of Mathematics</i> 17(3):449-467, 1965.
 +
[https://doi.org/10.4153/CJM-1965-045-4 doi:10.4153/CJM-1965-045-4]
  
 
<span id="ey07" style="color:maroon">[EY07]</span>
 
<span id="ey07" style="color:maroon">[EY07]</span>
 
K. Etessami and M. Yannakakis.
 
K. Etessami and M. Yannakakis.
 
On the Complexity of Nash Equilibria and Other Fixed Points.
 
On the Complexity of Nash Equilibria and Other Fixed Points.
−
Proceedings IEEE FOCS '07. SIAM J. Comput. 2010. doi:10.1137/080720826
+
<i>SIAM J. Comput.</i> 2010.  
 +
[https://doi.org/10.1137/080720826 doi:10.1137/080720826]
 +
Originally appeared in [https://doi.org/10.1109/FOCS.2007.39 FOCS 2007].
 +
[https://homepages.inf.ed.ac.uk/kousha/nash_focs07_full_j_spec_issue_sub.pdf Author's website version]
  
 
===== F =====
 
===== F =====
Line 1,231: Line 1,325:
 
<span id="fag73" style="color:maroon">[Fag73]</span>
 
<span id="fag73" style="color:maroon">[Fag73]</span>
 
R. Fagin.
 
R. Fagin.
−
Contributions to the Model Theory of Finite Strucutres,
+
Contributions to the Model Theory of Finite Structures,
 
<i>Ph.D. Thesis (1973), U.C. Berkeley</i>
 
<i>Ph.D. Thesis (1973), U.C. Berkeley</i>
  
Line 1,238: Line 1,332:
 
Generalized first-order spectra and polynomial-time recognizable sets,
 
Generalized first-order spectra and polynomial-time recognizable sets,
 
<i>Complexity of Computation</i> (R. M. Karp, ed.), SIAM-AMS Proceedings Vol. 7, 1974.
 
<i>Complexity of Computation</i> (R. M. Karp, ed.), SIAM-AMS Proceedings Vol. 7, 1974.
 +
[https://www.researchgate.net/publication/242608657_Generalized_first-order_spectra_and_polynomial_time_recognizable_sets Author's uploaded copy]
  
 
<span id="fen02" style="color:maroon">[Fen02]</span>
 
<span id="fen02" style="color:maroon">[Fen02]</span>
Line 1,243: Line 1,338:
 
PP-lowness and a simple definition of AWPP,
 
PP-lowness and a simple definition of AWPP,
 
<i>Theory Comput. Syst.</i> 36 (2003), no. 2, 199--212.
 
<i>Theory Comput. Syst.</i> 36 (2003), no. 2, 199--212.
 +
[https://doi.org/10.1007/s00224-002-1089-8 doi:10.1007/s00224-002-1089-8]
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2002/TR02-036/ TR02-036].
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2002/TR02-036/ TR02-036].
  
Line 1,252: Line 1,348:
 
S. Fenner, L. Fortnow, S. Kurtz, and L. Li.
 
S. Fenner, L. Fortnow, S. Kurtz, and L. Li.
 
An oracle builder's toolkit,
 
An oracle builder's toolkit,
−
<i>Proceedings of Structure in Complexity Theory</i>, pages 120-131, 1993.
+
<i>Inform. Comput.</i> 182(2):95-136, 2003.
−
[http://people.cs.uchicago.edu/~fortnow/papers/obt.ps http://people.cs.uchicago.edu/~fortnow/papers/obt.ps].
+
[https://doi.org/10.1016/S0890-5401(03)00018-X doi:10.1016/S0890-5401(03)00018-X]
 +
Originally appeared in [https://doi.org/10.1109/SCT.1993.336534 <i>Structure in Complexity Theory</i>, pages 120-131, 1993].
 +
[https://lance.fortnow.com/papers/files/obt.pdf Author's website version].
  
 
<span id="ffk94" style="color:maroon">[FFK94]</span>
 
<span id="ffk94" style="color:maroon">[FFK94]</span>
Line 1,259: Line 1,357:
 
Gap-definable counting classes,
 
Gap-definable counting classes,
 
<i>Journal of Computer and System Sciences</i> 48(1):116-148, 1994.
 
<i>Journal of Computer and System Sciences</i> 48(1):116-148, 1994.
−
[http://people.cs.uchicago.edu/~fortnow/papers/gaps.ps http://people.cs.uchicago.edu/~fortnow/papers/gaps.ps].
+
[https://doi.org/10.1016/S0022-0000(05)80024-8 doi:10.1016/S0022-0000(05)80024-8].
 +
Originally appeared in [https://doi.org/10.1109/SCT.1991.160241 <i>Structure in Complexity Theory</i>, 1991].
 +
[https://lance.fortnow.com/papers/files/gaps.pdf Author's website version].
  
 
<span id="fg02" style="color:maroon">[FG02]</span>
 
<span id="fg02" style="color:maroon">[FG02]</span>
 
J. Flum and M. Grohe.
 
J. Flum and M. Grohe.
 
The parameterized complexity of counting problems,
 
The parameterized complexity of counting problems,
−
<i>Proceedings of IEEE FOCS'2002</i>, 2002.
+
<i>SIAM J. Comput.</i> 33(4):892-922, 2004. [https://doi.org/10.1137/S0097539703427203 doi:10.1137/S0097539703427203]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.2002.1181978 FOCS '02].
  
 
<span id="fgh98" style="color:maroon">[FGH+98]</span>
 
<span id="fgh98" style="color:maroon">[FGH+98]</span>
Line 1,276: Line 1,377:
 
Approximating clique is almost NP-complete,
 
Approximating clique is almost NP-complete,
 
<i>Proceedings of IEEE FOCS'91</i>, pp. 2-12, 1991.
 
<i>Proceedings of IEEE FOCS'91</i>, pp. 2-12, 1991.
 +
[https://doi.org/10.1109/SFCS.1991.185341 doi:10.1109/SFCS.1991.185341]
  
 
<span id="fgmsz89" style="color:maroon">[FGM+89]</span>
 
<span id="fgmsz89" style="color:maroon">[FGM+89]</span>
Line 1,294: Line 1,396:
 
NP with small advice,
 
NP with small advice,
 
<i>Proceedings of IEEE Complexity'2005</i>, pp. 228-234, 2005.
 
<i>Proceedings of IEEE Complexity'2005</i>, pp. 228-234, 2005.
−
[http://people.cs.uchicago.edu/~fortnow/papers/fk.ps http://people.cs.uchicago.edu/~fortnow/papers/fk.ps].
+
[https://doi.org/10.1109/CCC.2005.15 doi:10.1109/CCC.2005.15]
 +
[https://lance.fortnow.com/papers/files/fk.pdf Author's website version].
  
 
<span id="fk97" style="color:maroon">[FK97]</span>
 
<span id="fk97" style="color:maroon">[FK97]</span>
Line 1,300: Line 1,403:
 
Limited versus polynomial nondeterminism,
 
Limited versus polynomial nondeterminism,
 
<i>Chicago Journal of Theoretical Computer Science</i> Article 1, 1997.
 
<i>Chicago Journal of Theoretical Computer Science</i> Article 1, 1997.
 +
[http://dx.doi.org/10.4086/cjtcs.1997.001 doi:10.4086/cjtcs.1997.001]
  
 
<span id="fk97b" style="color:maroon">[FK97b]</span>
 
<span id="fk97b" style="color:maroon">[FK97b]</span>
Line 1,305: Line 1,409:
 
Making games short,
 
Making games short,
 
<i>Proceedings of ACM STOC'1997</i>, pp. 506-516, 1997.
 
<i>Proceedings of ACM STOC'1997</i>, pp. 506-516, 1997.
 +
[https://doi.org/10.1145/258533.258644 doi:10.1145/258533.258644]
  
 
<span id="fmf16" style="color:maroon">[FMF16]</span>
 
<span id="fmf16" style="color:maroon">[FMF16]</span>
Line 1,310: Line 1,415:
 
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3,
 
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3,
 
<i>Theoretical Computer Science</i> 618, 2016.
 
<i>Theoretical Computer Science</i> 618, 2016.
 +
[https://doi.org/10.1016/j.tcs.2016.01.027 doi:10.1016/j.tcs.2016.01.027]
 
arXiv:[https://arxiv.org/abs/1312.2086 cs.CC/1312.2086].
 
arXiv:[https://arxiv.org/abs/1312.2086 cs.CC/1312.2086].
  
Line 1,316: Line 1,422:
 
The role of relativization in complexity theory,
 
The role of relativization in complexity theory,
 
<i>Bulletin of the EATCS</i> 52, February 1994.
 
<i>Bulletin of the EATCS</i> 52, February 1994.
−
[http://people.cs.uchicago.edu/~fortnow/papers/relative.ps http://people.cs.uchicago.edu/~fortnow/papers/relative.ps].
+
[https://lance.fortnow.com/papers/files/relative.pdf Author's website version].
  
 
<span id="for02" style="color:maroon">[For02]</span>
 
<span id="for02" style="color:maroon">[For02]</span>
Line 1,322: Line 1,428:
 
A linear lower bound on the unbounded error probabilistic communication complexity,
 
A linear lower bound on the unbounded error probabilistic communication complexity,
 
<i>Journal of Computer and System Sciences</i> 65(4):612-625, 2002.
 
<i>Journal of Computer and System Sciences</i> 65(4):612-625, 2002.
 +
[https://doi.org/10.1016/S0022-0000(02)00019-3 doi:10.1016/S0022-0000(02)00019-3]
 +
Originally appeared in [https://doi.org/10.1109/CCC.2001.933877 CCC '01]
  
 
<span id="fr74" style="color:maroon">[FR74]</span>
 
<span id="fr74" style="color:maroon">[FR74]</span>
Line 1,327: Line 1,435:
 
Super-exponential complexity of Presburger arithmetic,
 
Super-exponential complexity of Presburger arithmetic,
 
<i>Complexity of Computation</i> (R. M. Karp, ed.), SIAM-AMS Symposium on Applied Mathematics, 1974.
 
<i>Complexity of Computation</i> (R. M. Karp, ed.), SIAM-AMS Symposium on Applied Mathematics, 1974.
 +
Reprinted in 1998 at [https://doi.org/10.1007/978-3-7091-9459-1_5 doi:10.1007/978-3-7091-9459-1_5].
 +
Preliminary version [https://dspace.mit.edu/bitstream/handle/1721.1/148872/MIT-LCS-TM-043.pdf?sequence=1 MIT Project MAC Tech Report].
 +
 +
 +
<span id="fr96" style="color:maroon">[FR96]</span>
 +
L. Fortnow and N. Reingold.
 +
PP is closed under truth-table reductions,
 +
<i>Information and Computation</i> 124(1):1–6, 1996.
 +
[http://doi.org/10.1006/inco.1996.0001 doi:10.1006/inco.1996.0001]
  
 
<span id="fr98" style="color:maroon">[FR98]</span>
 
<span id="fr98" style="color:maroon">[FR98]</span>
 
L. Fortnow and J. D. Rogers.
 
L. Fortnow and J. D. Rogers.
 
Complexity limitations on quantum computation,
 
Complexity limitations on quantum computation,
−
<i>Proceedings of IEEE Complexity'98</i>, pp. 202-209, 1998.
+
<i>J. Comput. Syst. Sci.</i> 59(2): 240–252. 1999. Special issue for selected papers from the 13th IEEE Conference on Computational Complexity.
 +
Originally appeared in CCC '98.
 
arXiv:[http://arxiv.org/abs/cs.CC/9811023 cs.CC/9811023].
 
arXiv:[http://arxiv.org/abs/cs.CC/9811023 cs.CC/9811023].
 +
 +
<span id="fr21" style="color:maroon">[FR21]</span>
 +
B. Fefferman and Z. Remscrim.
 +
Eliminating intermediate measurements in space-bounded Quantum computation,
 +
<i>Proceedings of ACM STOC'2021</i>, pp. 1343–1356, 2021.
 +
arXiv:[http://arxiv.org/abs/2006.03530 cs.CC/2006.03530].
  
 
<span id="fri57" style="color:maroon">[Fri57]</span>
 
<span id="fri57" style="color:maroon">[Fri57]</span>
Line 1,338: Line 1,462:
 
Two recursively enumerable sets of incomparable degrees of unsolvability,
 
Two recursively enumerable sets of incomparable degrees of unsolvability,
 
<i>Proceedings of the National Academy of Sciences</i>, 43:236-238, 1957.
 
<i>Proceedings of the National Academy of Sciences</i>, 43:236-238, 1957.
−
[http://www.pubmedcentral.nih.gov/picrender.fcgi?artid=528418&amp;blobtype=pdf http://www.pubmedcentral.nih.gov/picrender.fcgi?artid=528418&amp;blobtype=pdf].
+
[https://doi.org/10.1073/pnas.43.2.236 doi:10.1073/pnas.43.2.236].
  
 
<span id="frs88" style="color:maroon">[FRS88]</span>
 
<span id="frs88" style="color:maroon">[FRS88]</span>
 
L. Fortnow, J. Rompel, and M. Sipser.
 
L. Fortnow, J. Rompel, and M. Sipser.
 
On the power of multiprover interactive protocols,
 
On the power of multiprover interactive protocols,
−
<i>Proceedings of IEEE Complexity'88</i>, 1988.
+
<i>Theoret. Comput. Sci.</i> 134(2):545-557, 1994.
−
[http://people.cs.uchicago.edu/~fortnow/papers/mip.ps http://people.cs.uchicago.edu/~fortnow/papers/mip.ps].
+
[https://doi.org/10.1016/0304-3975(94)90251-8 doi:10.1016/0304-3975(94)90251-8]
 +
Originally appeared in [https://doi.org/10.1109/SCT.1988.5275 Complexity '88]
 +
[https://lance.fortnow.com/papers/files/mip.pdf Author's website version].
  
 
<span id="fs04" style="color:maroon">[FS04]</span>
 
<span id="fs04" style="color:maroon">[FS04]</span>
Line 1,350: Line 1,476:
 
Hierarchy theorems for probabilistic polynomial time,
 
Hierarchy theorems for probabilistic polynomial time,
 
<i>Proceedings of IEEE FOCS'2004</i>, 2004.
 
<i>Proceedings of IEEE FOCS'2004</i>, 2004.
−
[http://people.cs.uchicago.edu/~fortnow/papers/probhier.ps http://people.cs.uchicago.edu/~fortnow/papers/probhier.ps].
+
[http://doi.org/10.1109/FOCS.2004.33 doi:10.1109/FOCS.2004.33]
 +
[https://lance.fortnow.com/papers/files/probhier.pdf Author's website version]
  
 
<span id="fs88" style="color:maroon">[FS88]</span>
 
<span id="fs88" style="color:maroon">[FS88]</span>
Line 1,356: Line 1,483:
 
Are there interactive protocols for co-NP languages?
 
Are there interactive protocols for co-NP languages?
 
Inform. Process. Lett. 28 (1988), no. 5, 249--251.
 
Inform. Process. Lett. 28 (1988), no. 5, 249--251.
−
[http://cs-www.uchicago.edu/~fortnow/papers/conpipl.ps http://cs-www.uchicago.edu/~fortnow/papers/conpipl.ps]
+
[http://doi.org/10.1016/0020-0190(88)90199-8 doi:10.1016/0020-0190(88)90199-8]
 +
[https://lance.fortnow.com/papers/files/conpipl.pdf Author's website version]
  
 
<span id="fss84" style="color:maroon">[FSS84]</span>
 
<span id="fss84" style="color:maroon">[FSS84]</span>
Line 1,362: Line 1,490:
 
Parity, circuits, and the polynomial hierarchy,
 
Parity, circuits, and the polynomial hierarchy,
 
<i>Mathematical Systems Theory</i> 17:13-27, 1984.
 
<i>Mathematical Systems Theory</i> 17:13-27, 1984.
 +
[https://doi.org/10.1007/BF01744431 doi:10.1007/BF01744431]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1981.35 FOCS '81].
 +
 +
<span id="fsw09" style="color:maroon">[FSW09]</span>
 +
L. Fortnow, R. Santhanam and R. Williams.
 +
Fixed-Polynomial Size Circuit Bounds,
 +
<i>Poceedings of the 24th Annual IEEE Conference on Computational Complexity</i>, pp. 19-26, 2009.
 +
[https://doi.org/10.1109/CCC.2009.21 doi:CCC.2009.21]
 +
[https://people.csail.mit.edu/rrw/circuit.pdf Author's website version].
  
 
<span id="fur07" style="color:maroon">[Fur07]</span>
 
<span id="fur07" style="color:maroon">[Fur07]</span>
 
M. Furer.
 
M. Furer.
−
Fast Integer Multiplication,
+
Faster Integer Multiplication,
−
STOC, 2007.
+
<i>Proc. ACM STOC 2007</i>, pp. 57-66.
 +
[https://doi.org/10.1145/1250790.1250800 doi:10.1145/1250790.1250800]
  
 
<span id="fv93" style="color:maroon">[FV93]</span>
 
<span id="fv93" style="color:maroon">[FV93]</span>
Line 1,427: Line 1,565:
 
Extended abstract appeared in <i>Proceeedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP)</i>, pages 387-398, Springer, 2012.
 
Extended abstract appeared in <i>Proceeedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP)</i>, pages 387-398, Springer, 2012.
  
−
<span id="gsssy18" style="color:maroon">[GSSSY18]</span>
+
<span id="gkm15" style="color:maroon">[GKM15]</span>
−
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka.
+
V. Girard, M. Koucky, and P. McKenzie.
−
Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2),
+
Nonuniform catalytic space and the direct sum for space,
−
<i>Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)</i>, pages 58:1-58:16, LIPIcs, 2018.
+
ECCC [https://eccc.weizmann.ac.il/report/2015/138/]
 +
 
 +
<span id="gkr15" style="color:maroon">[GKR15]</span>
 +
S. Goldwasser, Y. Kalai, and G. Rothblum.
 +
Delegating Computation: Interactive Proofs for Muggles,
 +
<i>Journal of the ACM</i> 62(4), 2015
  
 
<span id="gkr95" style="color:maroon">[GKR+95]</span>
 
<span id="gkr95" style="color:maroon">[GKR+95]</span>
Line 1,452: Line 1,595:
 
Rectangles Are Nonnegative Juntas,
 
Rectangles Are Nonnegative Juntas,
 
<i>Proceedings of ACM STOC'15</i>, pp. 257-266, 2015.
 
<i>Proceedings of ACM STOC'15</i>, pp. 257-266, 2015.
 +
 +
<span id="glv24" style="color:maroon">[GLV24]</span>
 +
K. Gajulapalli, Z. Li, I. Volkovich
 +
Oblivious Classes Revisited: Lower Bounds and Hierarchies,
 +
ECCC [https://eccc.weizmann.ac.il/report/2024/049/]
 +
 +
<span id="gm15" style="color:maroon">[GM15]</span>
 +
O. Goldreich and O. Meir.
 +
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly,
 +
<i>Transactions on Computation Theory</i> 7(4): 16, 2015.
 +
[https://eccc.weizmann.ac.il/report/2011/023/ https://eccc.weizmann.ac.il/report/2011/023/]
  
 
<span id="gmr89" style="color:maroon">[GMR89]</span>
 
<span id="gmr89" style="color:maroon">[GMR89]</span>
Line 1,519: Line 1,673:
 
<span id="gq19" style="color:maroon">[GQ19]</span>
 
<span id="gq19" style="color:maroon">[GQ19]</span>
 
J. A. Grochow and Y. Qiao.
 
J. A. Grochow and Y. Qiao.
−
Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions,
+
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness,
−
arXiv:[https://arxiv.org/abs/1907.00309 1907.00309], 2019.
+
<i>SIAM J. Comput.</i> 52(2):568-617, 2023 [https://doi.org/10.1137/21M1441110 doi:10.1137/21M1441110].
 +
Originally appeared in [https://doi.org/10.4230/LIPIcs.ITCS.2021.31 ITCS '21] and arXiv:[https://arxiv.org/abs/1907.00309 1907.00309].
 +
 
 +
<span id="gq21" style="color:maroon">[GQ21]</span>
 +
J. A. Grochow and Y. Qiao.
 +
On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors,
 +
<i>ACM Trans. Comput. Theory</i> 16(1):2:1-2:39. [https://doi.org/10.1145/3625308 doi:10.1145/3625308].
 +
Originally appeared in [https://doi.org/10.4230/LIPIcs.CCC.2021.16 CCC '21].
  
 
<span id="gra92" style="color:maroon">[Grä92]</span>
 
<span id="gra92" style="color:maroon">[Grä92]</span>
Line 1,588: Line 1,749:
 
Disjoint NP-pairs,
 
Disjoint NP-pairs,
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-011/ TR03-011], 2003.
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-011/ TR03-011], 2003.
 +
 +
<span id="gsssy18" style="color:maroon">[GSSSY18]</span>
 +
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka.
 +
Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2),
 +
<i>Computational Complexity</i> 31, 13, 2022.
 +
doi:[https://doi.org/10.1007/s00037-022-00231-8 10.1007/s00037-022-00231-8].
  
 
<span id="gst03" style="color:maroon">[GST03]</span>
 
<span id="gst03" style="color:maroon">[GST03]</span>
Line 1,671: Line 1,838:
 
<span id="gy16" style="color:maroon">[GY16]</span>
 
<span id="gy16" style="color:maroon">[GY16]</span>
 
S. Gharibian, and J. Yirka.
 
S. Gharibian, and J. Yirka.
−
The complexity of estimating local physical quantities,  
+
The complexity of simulating local measurements on quantum systems,
−
arXiv:[http://arxiv.org/abs/1606.05626 quant-ph/1606.05626], 2016.
+
<i>Quantum</i> 3, pp. 189, 2019.
 +
doi:[https://doi.org/10.22331/q-2019-09-30-189 10.22331/q-2019-09-30-189].
 +
 
 +
<span id="gy24" style="color:maroon">[GY24]</span>
 +
S. Grewal, and J. Yirka.
 +
The Entangled Quantum Polynomial Hierarchy Collapses,  
 +
arXiv:[https://arxiv.org/abs/2401.01453 quant-ph/2401.01453], 2024.
  
 
<span id="gz97" style="color:maroon">[GZ97]</span>
 
<span id="gz97" style="color:maroon">[GZ97]</span>
Line 1,678: Line 1,851:
 
Another proof that BPP subseteq PH (and more),
 
Another proof that BPP subseteq PH (and more),
 
ECCC [http://eccc.uni-trier.de/eccc-reports/1997/TR97-045/ TR97-045].
 
ECCC [http://eccc.uni-trier.de/eccc-reports/1997/TR97-045/ TR97-045].
 +
 +
 +
<span id="ghj22" style="color:maroon">[GHJ+22]</span>
 +
M. Göös, A. Hollender, S. Jain, G. Maystre, W. Pires, R. Robere, R. Tao
 +
Separations in Proof Complexity and TFNP,
 +
ECCC [https://eccc.weizmann.ac.il/report/2022/058/#revision1 TR22-058].
  
 
===== H =====
 
===== H =====
Line 1,884: Line 2,063:
 
Oracles for structural properties: the isomorphism problem and public-key cryptography,
 
Oracles for structural properties: the isomorphism problem and public-key cryptography,
 
<i>Journal of Computer and System Sciences</i> 44(2):287-301, 1992.
 
<i>Journal of Computer and System Sciences</i> 44(2):287-301, 1992.
 +
 +
<span id="hs05" style="color:maroon">[HS05]</span>
 +
P. Høyer and R. Špalek.
 +
Qauntum fan-out is powerful,
 +
<i>Theory of computing</i> (1)1:81-103, 2005.
  
 
<span id="ht03" style="color:maroon">[HT03]</span>
 
<span id="ht03" style="color:maroon">[HT03]</span>
Line 1,908: Line 2,092:
 
A note concerning nondeterministic tape complexities,
 
A note concerning nondeterministic tape complexities,
 
<i>Journal of the ACM</i> 4:608-612, 1972.
 
<i>Journal of the ACM</i> 4:608-612, 1972.
 +
[https://doi.org/10.1145/321724.321727 doi:10.1145/321724.321727]
  
 
<span id="ikw01" style="color:maroon">[IKW01]</span>
 
<span id="ikw01" style="color:maroon">[IKW01]</span>
 
R. Impagliazzo, V. Kabanets, and A. Wigderson.
 
R. Impagliazzo, V. Kabanets, and A. Wigderson.
 
In search of an easy witness: exponential time vs. probabilistic polynomial time,
 
In search of an easy witness: exponential time vs. probabilistic polynomial time,
−
<i>Proceedings of IEEE Complexity'2001</i>, 2001.
+
<i>J. Comput. Syst. Sci.</i>, 2002.
−
[http://www.cs.sfu.ca/~kabanets/papers/exp_journal.ps.gz http://www.cs.sfu.ca/~kabanets/papers/exp_journal.ps.gz]
+
[https://doi.org/10.1016/S0022-0000(02)00024-7 doi:10.1016/S0022-0000(02)00024-7]
 +
Originally appearing in [https://doi.org/10.1109/CCC.2001.933865 IEEE CCC 2001].
 +
[https://www.cs.sfu.ca/~kabanets/Research/ikw.html Author's website version]
  
 
<span id="il90" style="color:maroon">[IL90]</span>
 
<span id="il90" style="color:maroon">[IL90]</span>
Line 1,919: Line 2,106:
 
No better ways to generate hard NP instances than picking uniformly at random,
 
No better ways to generate hard NP instances than picking uniformly at random,
 
<i>Proceedings of IEEE FOCS'90</i>, pp. 812-821, 1990.
 
<i>Proceedings of IEEE FOCS'90</i>, pp. 812-821, 1990.
 +
[https://doi.org/10.1109/FSCS.1990.89604 doi:10.1109/FSCS.1990.89604]
  
−
{{Reference
+
<span id="IM03" style="color:maroon">[IM03]</span>
−
    |tag=IM03
+
R. Impagliazzo and P. Moser.
−
    |title=A zero one law for RP
+
A zero-one law for RP and derandomization of AM if NP is not small,
−
    |authors=R. Impagliazzo and P. Moser
+
<i>Information and Computation</i> 207(7):787-792, 2009.
−
    |journal=Proceedings of the 18th Conference on Computational Complexity
+
[https://doi.org/10.1016/j.ic.2009.02.002 doi:10.1016/j.ic.2009.02.002]
−
    |srcdetail=48-52. IEEE Computer Society Press, 2003
+
Originally appeared as "A zero one law for RP" in [https://doi.org/10.1109/CCC.2003.1214409 IEEE CCC 2003].
−
}}
 
  
−
{{Reference
+
<span id="Imp95" style="color:maroon">[Imp95]</span>
−
    |tag=Imp95
+
R. Impagliazzo.
−
    |title=A personal view of average-case complexity
+
A personal view of average-case complexity,
−
    |authors=R. Impagliazzo
+
<i>Proceedings of the 10th Conference on Structure in Complexity Theory</i>, 134-147, 1995.
−
    |journal=Proceedings of the 10th Conference on Structure in Complexity Theory
+
[https://doi.ieeecomputersociety.org/10.1109/SCT.1995.514853 doi:10.1109/SCT.1995.514853]
−
    |srcdetail=134-147. IEEE Computer Society Press, 1995
+
[https://cseweb.ucsd.edu/~russell/average.ps Author's website version]
−
}}
 
  
 
<span id="imm82" style="color:maroon">[Imm82]</span>
 
<span id="imm82" style="color:maroon">[Imm82]</span>
 
N. Immerman.
 
N. Immerman.
 
Relational queries computable in in polynomial time.
 
Relational queries computable in in polynomial time.
−
<i>14th ACM STOC Symp. (1987), 86-104</i>
+
<i>Information and Control</i> 68(1-3):86-104, 1986.
−
 
+
[https://doi.org/10.1016/S0019-9958(86)80029-8 doi:10.1016/S0019-9958(86)80029-8]
 +
Originally appeared in [https://doi.org/10.1145/800070.802187 STOC 1982].
 +
[https://people.cs.umass.edu/~immerman/pub/RelationalQueriesSTOC82.pdf Author's website conference version]
  
 
<span id="imm83" style="color:maroon">[Imm83]</span>
 
<span id="imm83" style="color:maroon">[Imm83]</span>
 
N. Immerman.
 
N. Immerman.
 
Languages That Capture Complexity Classes
 
Languages That Capture Complexity Classes
−
<i>15th ACM STOC Symp. (1983), 347-354</i>
+
<i>SIAM J. Comput.</i>, 16(4):760-778, 1986.
−
[http://www.cs.umass.edu/~immerman/pub/capture.pdf]
+
[https://doi.org/10.1137/0216051 doi:10.1137/0216051]
 +
Originally appeared as "Languages Which Capture Complexity Classes" in [https://doi.org/10.1145/800061.808765 STOC 1983].
 +
[https://people.cs.umass.edu/~immerman/pub/capture.pdf Author's website version]
  
 
<span id="imm88" style="color:maroon">[Imm88]</span>
 
<span id="imm88" style="color:maroon">[Imm88]</span>
Line 1,952: Line 2,142:
 
Nondeterministic space is closed under complement,
 
Nondeterministic space is closed under complement,
 
<i>SIAM Journal on Computing</i>, 17:935-938, 1988.
 
<i>SIAM Journal on Computing</i>, 17:935-938, 1988.
 +
[https://doi.org/10.1137/0217058 doi:10.1137/0217058]
 +
Originally appeared in [https://doi.org/10.1109/SCT.1988.5270 SCT 1988]
 +
[https://people.cs.umass.edu/~immerman/pub/space.pdf Author's website version]
  
 
<span id="imm89" style="color:maroon">[Imm89]</span>
 
<span id="imm89" style="color:maroon">[Imm89]</span>
Line 1,957: Line 2,150:
 
Expressibility and Parallel Complexity
 
Expressibility and Parallel Complexity
 
<i>SIAM Journal on Computing</i>, 18:625-638, 1989.
 
<i>SIAM Journal on Computing</i>, 18:625-638, 1989.
−
[http://www.cs.umass.edu/~immerman/pub/parallel.pdf]
+
[https://doi.org/10.1137/0218043 doi:10.1137/0218043]
 +
[https://people.cs.umass.edu/~immerman/pub/parallel.pdf Author's website version]
  
 
<span id="imm98" style="color:maroon">[Imm98]</span>
 
<span id="imm98" style="color:maroon">[Imm98]</span>
Line 1,963: Line 2,157:
 
<i>Descriptive Complexity</i>,
 
<i>Descriptive Complexity</i>,
 
Springer Graduate Texts in Computer Science, 1998.
 
Springer Graduate Texts in Computer Science, 1998.
 +
[https://doi.org/10.1007/978-1-4612-0539-5 doi:10.1007/978-1-4612-0539-5]
  
 
<span id="imp02" style="color:maroon">[Imp02]</span>
 
<span id="imp02" style="color:maroon">[Imp02]</span>
Line 1,974: Line 2,169:
 
Efficient cryptographic schemes provably as secure as subset sum,
 
Efficient cryptographic schemes provably as secure as subset sum,
 
<i>Journal of Cryptology</i> 9(4):199-216, 1996.
 
<i>Journal of Cryptology</i> 9(4):199-216, 1996.
−
[http://www.wisdom.weizmann.ac.il/~naor/PAPERS/subset.ps.gz http://www.wisdom.weizmann.ac.il/~naor/PAPERS/subset.ps.gz]
+
[https://doi.org/10.1007/BF00189260 doi:10.1007/BF00189260]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1989.63484 FOCS 1989 (technically SFCS)].
 +
[https://cseweb.ucsd.edu/~russell/moni.ps Author's website version]
  
 
<span id="ipz01" style="color:maroon">[IPZ01]</span>
 
<span id="ipz01" style="color:maroon">[IPZ01]</span>
Line 1,980: Line 2,177:
 
Which problems have strongly exponential complexity,
 
Which problems have strongly exponential complexity,
 
<i>Journal of Computer and System Sciences</i> 63(4):512-530, 2001.
 
<i>Journal of Computer and System Sciences</i> 63(4):512-530, 2001.
−
[http://cm.bell-labs.com/cm/ms/who/francis/papers/focs98-subexp.pdf http://cm.bell-labs.com/cm/ms/who/francis/papers/focs98-subexp.pdf].
+
[https://doi.org/10.1006/jcss.2001.1774 doi:10.1006/jcss.2001.1774]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1998.743516 SFCS 1998].
 +
[https://cseweb.ucsd.edu/~russell/ipz.pdf Author's website journal version]
  
 
<span id="is91" style="color:maroon">[IS91]</span>
 
<span id="is91" style="color:maroon">[IS91]</span>
Line 1,991: Line 2,190:
 
Decision versus search problems in super-polynomial time,
 
Decision versus search problems in super-polynomial time,
 
in <i>Proceedings of IEEE FOCS 1989</i>, pp. 222-227, 1989.
 
in <i>Proceedings of IEEE FOCS 1989</i>, pp. 222-227, 1989.
 +
[https://doi.org/10.1109/SFCS.1989.63482 doi:SFCS.1989.63482]
  
 
<span id="ito10" style="color:maroon">[Ito10]</span>
 
<span id="ito10" style="color:maroon">[Ito10]</span>
 
T. Ito
 
T. Ito
 
Polynomial-Space Approximation of No-Signaling Provers, in
 
Polynomial-Space Approximation of No-Signaling Provers, in
−
<i>Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)</i>, 2010, pp. 140-151
+
<i>Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)</i>, 2010, pp. 140-151.
 +
[https://doi.org/10.1007/978-3-642-14165-2_13 doi:10.1007/978-3-642-14165-2_13]
 
arXiv:[https://arxiv.org/abs/0908.2363 0908.2363].
 
arXiv:[https://arxiv.org/abs/0908.2363 0908.2363].
  
Line 2,002: Line 2,203:
 
A multi-prover interactive proof for NEXP sound against entangled provers,
 
A multi-prover interactive proof for NEXP sound against entangled provers,
 
to appear in <i>Proceedings of IEEE FOCS 2012</i>
 
to appear in <i>Proceedings of IEEE FOCS 2012</i>
 +
[https://doi.org/10.1109/FOCS.2012.11 doi:10.1109/FOCS.2012.11]
 
arXiv:[http://arxiv.org/abs/1207.0550 1207.0550].
 
arXiv:[http://arxiv.org/abs/1207.0550 1207.0550].
  
Line 2,008: Line 2,210:
 
P=BPP if E requires exponential circuits: derandomizing the XOR lemma,
 
P=BPP if E requires exponential circuits: derandomizing the XOR lemma,
 
<i>Proceedings of ACM STOC'97</i>, pp. 220-229, 1997.
 
<i>Proceedings of ACM STOC'97</i>, pp. 220-229, 1997.
 +
[https://doi.org/10.1145/258533.258590 doi:10.1145/258533.258590]
 +
[https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IMPAGLIAZZO/XOR/draft1.ps Author's website version]
  
 
===== J =====
 
===== J =====
Line 2,020: Line 2,224:
 
Approximate counting in bounded arithmetic,
 
Approximate counting in bounded arithmetic,
 
''Journal of Symbolic Logic'' 72(3):959–993, 2007.
 
''Journal of Symbolic Logic'' 72(3):959–993, 2007.
 +
[https://www.jstor.org/stable/27588579 Available on JSTOR]
  
 
<span id="jer12" style="color:maroon">[Jeř12]</span>
 
<span id="jer12" style="color:maroon">[Jeř12]</span>
Line 2,025: Line 2,230:
 
Integer factoring and modular square roots,
 
Integer factoring and modular square roots,
 
''Journal of Computer and System Sciences'' 82(2):380–394, 2016.
 
''Journal of Computer and System Sciences'' 82(2):380–394, 2016.
 +
[https://doi.org/10.1016/j.jcss.2015.08.001 doi:10.1016/j.jcss.2015.08.001]
 
arXiv:[http://arxiv.org/abs/1207.5220 1207.5220]
 
arXiv:[http://arxiv.org/abs/1207.5220 1207.5220]
  
Line 2,030: Line 2,236:
 
R. Jain, Z. Ji, S. Upadhyay, and J. Watrous.
 
R. Jain, Z. Ji, S. Upadhyay, and J. Watrous.
 
QIP = PSPACE,
 
QIP = PSPACE,
−
arXiv:[http://arxiv.org/abs/0907.4737 0907.4737], 2009.
+
<i>J. ACM</i> 58(6):1-27, 2011.
 +
[https://doi.org/10.1145/2049697.2049704 doi:10.1145/2049697.2049704]
 +
arXiv:[http://arxiv.org/abs/0907.4737 0907.4737].
  
 
<span id="jks02" style="color:maroon">[JKS02]</span>
 
<span id="jks02" style="color:maroon">[JKS02]</span>
Line 2,036: Line 2,244:
 
Learnability beyond AC<sup>0</sup>,
 
Learnability beyond AC<sup>0</sup>,
 
<i>Proceedings of ACM STOC'2002</i>, pp. 776-784, 2002.
 
<i>Proceedings of ACM STOC'2002</i>, pp. 776-784, 2002.
 +
[https://doi.org/10.1145/509907.510018 doi:10.1145/509907.510018]
 +
[http://www.cs.columbia.edu/~rocco/papers/stoc02.html Author's website version]
  
 
<span id="jl95" style="color:maroon">[JL95]</span>
 
<span id="jl95" style="color:maroon">[JL95]</span>
Line 2,041: Line 2,251:
 
The complexity and distribution of hard problems,
 
The complexity and distribution of hard problems,
 
<i>SIAM Journal on Computing</i> 24(2):279-295, 1995.
 
<i>SIAM Journal on Computing</i> 24(2):279-295, 1995.
−
[http://www.cs.iastate.edu/~lutz/%3DPAPERS/cdhp.ps http://www.cs.iastate.edu/~lutz/%3DPAPERS/cdhp.ps]
+
[https://doi.org/10.1137/S0097539792238133 doi:10.1137/S0097539792238133]
 +
[https://jacklutz.com/=PAPERS/cdhp.pdf Author's website version]
  
 
<span id="joh90" style="color:maroon">[Joh90]</span>
 
<span id="joh90" style="color:maroon">[Joh90]</span>
Line 2,050: Line 2,261:
 
<span id="jon98" style="color:maroon">[Jon98]</span>
 
<span id="jon98" style="color:maroon">[Jon98]</span>
 
N. D. Jones.
 
N. D. Jones.
−
Logspace and Ptime Characteried by Programming Languages,
+
LOGSPACE and PTIME Characteried by Programming Languages,
−
[ftp://ftp.diku.dk/pub/diku/semantics/papers/D-398.ps.gz]
+
<i>Theoret. Comput. Sci.</i> 228(1-2):151-174, 1999.
 +
[https://doi.org/10.1016/S0304-3975(98)00357-0 doi:10.1016/S0304-3975(98)00357-0]
 +
[https://core.ac.uk/download/pdf/82651296.pdf https://core.ac.uk/download/pdf/82651296.pdf]
  
 
<span id="jpy88" style="color:maroon">[JPY88]</span>
 
<span id="jpy88" style="color:maroon">[JPY88]</span>
Line 2,057: Line 2,270:
 
How easy is local search?,
 
How easy is local search?,
 
<i>Journal of Computer and System Sciences</i> 37:79-100, 1988.
 
<i>Journal of Computer and System Sciences</i> 37:79-100, 1988.
 +
[https://doi.org/10.1016/0022-0000(88)90046-3 DOI:10.1016/0022-0000(88)90046-3]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1985.31 FOCS 1985].
  
 
<span id="jsv01" style="color:maroon">[JSV01]</span>
 
<span id="jsv01" style="color:maroon">[JSV01]</span>
 
M. Jerrum, A. Sinclair, and E. Vigoda.
 
M. Jerrum, A. Sinclair, and E. Vigoda.
 
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,
 
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,
−
<i>Proceedings of ACM STOC'2001</i>, pp. 712-721, 2001.
+
<i>J. ACM</i> 51(4):671-697, 2004.
−
ECCC [http://eccc.uni-trier.de/eccc-reports/2000/TR00-079/ TR00-079].
+
[https://doi.org/10.1145/1008731.1008738 doi:10.1145/1008731.1008738]
 +
Originally appeared in [https://doi.org/10.1145/380752.380877 STOC 2001]
 +
, ECCC [http://eccc.uni-trier.de/eccc-reports/2000/TR00-079/ TR00-079].
  
 
<span id="jun85" style="color:maroon">[Jun85]</span>
 
<span id="jun85" style="color:maroon">[Jun85]</span>
Line 2,068: Line 2,285:
 
On probabilistic time and space,
 
On probabilistic time and space,
 
<i>Proceedings of 12th International Colloquium on Automata, Languages, and Programming (ICALP)</i>, Lecture Notes in Computer Science, 194:310-317, 1985.
 
<i>Proceedings of 12th International Colloquium on Automata, Languages, and Programming (ICALP)</i>, Lecture Notes in Computer Science, 194:310-317, 1985.
 +
[https://doi.org/10.1007/BFb0015756 doi:10.1007/BFb0015756]
  
 
<span id="jw04" style="color:maroon">[JW04]</span>
 
<span id="jw04" style="color:maroon">[JW04]</span>
Line 2,079: Line 2,297:
 
Parallel approximation of non-interactive zero-sum quantum games,
 
Parallel approximation of non-interactive zero-sum quantum games,
 
<i>Proceedings of the 24th Annual IEEE Conference on Computational Complexity</i>, pages 243–253, 2009.
 
<i>Proceedings of the 24th Annual IEEE Conference on Computational Complexity</i>, pages 243–253, 2009.
 +
[https://doi.org/10.1109/CCC.2009.26 doi:10.1109/CCC.2009.26]
 
arXiv:[http://arxiv.org/abs/0808.2775 0808.2775 [quant-ph]].
 
arXiv:[http://arxiv.org/abs/0808.2775 0808.2775 [quant-ph]].
  
Line 2,090: Line 2,309:
 
On generating all maximal independent sets,
 
On generating all maximal independent sets,
 
<i>Information Processing Letters</i> 27(3):119-123, 1988.
 
<i>Information Processing Letters</i> 27(3):119-123, 1988.
 +
[https://doi.org/10.1016/0020-0190(88)90065-8 doi:10.1016/0020-0190(88)90065-8]
  
 
===== K =====
 
===== K =====
Line 2,131: Line 2,351:
 
V. Kabanets and R. Impagliazzo.
 
V. Kabanets and R. Impagliazzo.
 
Derandomizing polynomial identity tests means proving circuit lower bounds,
 
Derandomizing polynomial identity tests means proving circuit lower bounds,
−
ECCC [http://eccc.uni-trier.de/eccc-reports/2002/TR02-055/ TR02-055], 2002.
+
<i>Computational Complexity</i> 13:1–46, 2004.
 +
[https://doi.org/10.1007/s00037-004-0182-6 DOI:10.1007/s00037-004-0182-6],
 +
https://www.cs.sfu.ca/~kabanets/Research/poly.html
  
 
<span id="kkr04" style="color:maroon">[KKR04]</span>
 
<span id="kkr04" style="color:maroon">[KKR04]</span>
Line 2,237: Line 2,459:
 
Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations,
 
Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations,
 
<i>J. Symb. Log.</i>, 54:1063-79, 1989.
 
<i>J. Symb. Log.</i>, 54:1063-79, 1989.
 +
 +
<span id="kptwy24" style="color:maroon">[KPTWY24]</span>
 +
J. Kallaugher, O. Parekh, K. Thompson, Y. Wang, and J. Yirka.
 +
Complexity Classification of Product State Problems for Local Hamiltonians.
 +
arXiv:[https://arxiv.org/abs/2401.06725 2401.06725], 2024.
  
 
<span id="kr03" style="color:maroon">[KR03]</span>
 
<span id="kr03" style="color:maroon">[KR03]</span>
Line 2,392: Line 2,619:
 
On the structure of polynomial time reducibility,
 
On the structure of polynomial time reducibility,
 
<i>Journal of the ACM</i> 22:155-171, 1975.
 
<i>Journal of the ACM</i> 22:155-171, 1975.
 +
[https://doi.org/10.1145/321864.321877 doi:10.1145/321864.321877]
  
 
<span id="lau83" style="color:maroon">[Lau83]</span>
 
<span id="lau83" style="color:maroon">[Lau83]</span>
Line 2,397: Line 2,625:
 
BPP and the polynomial time hierarchy,
 
BPP and the polynomial time hierarchy,
 
<i>Information Processing Letters</i> 17:215-218, 1983.
 
<i>Information Processing Letters</i> 17:215-218, 1983.
 +
[https://doi.org/10.1016/0020-0190(83)90044-3 doi:10.1016/0020-0190(83)90044-3]
  
 
<span id="lee02" style="color:maroon">[Lee02]</span>
 
<span id="lee02" style="color:maroon">[Lee02]</span>
 
T. Lee.
 
T. Lee.
 
Arithmetical definability over finite structures,
 
Arithmetical definability over finite structures,
−
Mathematical Logic Quarterly, Vol. 49(4), 2003.  
+
<i>Mathematical Logic Quarterly</i>, Vol. 49(4), 2003.  
−
[http://www.lri.fr/~lee/arith.pdf http://www.lri.fr/~lee/arith.pdf].
+
[https://doi.org/10.1002/malq.200310041 doi:10.1002/malq.200310041]
 +
[http://www1.cs.columbia.edu/~tl2383/arith.pdf Author's webpage version]
 +
 
 +
<span id="ler22" style="color:maroon">[Ler22]</span>
 +
Jérôme Leroux
 +
The Reachability Problem for Petri Nets is Not Primitive Recursive,
 +
<i>Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science</i>, Pages 1241–1252, 2022
 +
arXiv: [https://arxiv.org/abs/2104.12695]
  
 
<span id="lev73" style="color:maroon">[Lev73]</span>
 
<span id="lev73" style="color:maroon">[Lev73]</span>
 
L. A. Levin.
 
L. A. Levin.
−
Universal search problems (in Russian),
+
Universal sequential search problems (in Russian),
 
<i>Problemy Peredachi Informatsii</i> 9(3):265-266, 1973.
 
<i>Problemy Peredachi Informatsii</i> 9(3):265-266, 1973.
 +
[http://mi.mathnet.ru/ppi914  http://mi.mathnet.ru/ppi914]
 +
English translation digitally available in Trakhtenbrot "A survey of Russian approaches to <i>perebor</i> (brute-force search) algorithms", <i> Ann. Hist. Comput.</i> 6(4):384-400, 1984, [https://doi.org/10.1109/MAHC.1984.10036 doi:10.1109/MAHC.1984.10036].
  
 
<span id="lev86" style="color:maroon">[Lev86]</span>
 
<span id="lev86" style="color:maroon">[Lev86]</span>
Line 2,413: Line 2,651:
 
Average case complete problems,
 
Average case complete problems,
 
<i>SIAM Journal on Computing</i>, 15:285-286, 1986.
 
<i>SIAM Journal on Computing</i>, 15:285-286, 1986.
 +
[https://doi.org/10.1137/0215020 doi:10.1137/0215020]
  
 
<span id="lfk90" style="color:maroon">[LFK+90]</span>
 
<span id="lfk90" style="color:maroon">[LFK+90]</span>
 
C. Lund, L. Fortnow, H. Karloff, and N. Nisan.
 
C. Lund, L. Fortnow, H. Karloff, and N. Nisan.
 
Algebraic methods for interactive proofs,
 
Algebraic methods for interactive proofs,
−
<i>Proceedings of IEEE FOCS'90</i>, pp. 1-10, 1990.
+
<i>J. ACM</i>, 39(4):859-868, 1992.
−
[http://people.cs.uchicago.edu/~fortnow/papers/ip.ps http://people.cs.uchicago.edu/~fortnow/papers/ip.ps]
+
[https://doi.org/10.1145/146585.146605 doi:10.1145/146585.146605]
 +
Originally appeared in [https://doi.org/10.1109/FSCS.1990.89518 FOCS 1990]
 +
[https://lance.fortnow.com/papers/files/ip.pdf Authors' webpage version]
  
 
<span id="li93" style="color:maroon">[Li93]</span>
 
<span id="li93" style="color:maroon">[Li93]</span>
Line 2,424: Line 2,665:
 
<i>On the Counting Functions</i>,
 
<i>On the Counting Functions</i>,
 
PhD thesis, University of Chicago, 1993.
 
PhD thesis, University of Chicago, 1993.
 +
[http://newtraell.cs.uchicago.edu/files/tr_authentic/TR-93-12.ps http://newtraell.cs.uchicago.edu/files/tr_authentic/TR-93-12.ps]
 +
 +
<span id="li23" style="color:maroon">[Li23]</span>
 +
Z. Li.
 +
<i>Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform</i>,
 +
Electronic Colloquium on Computational Complexity (ECCC), 2023
 +
[https://eccc.weizmann.ac.il/report/2023/156/ ECCC Version]
  
−
{{Reference
+
<span id="LiRe93" style="color:maroon">[LiRe93]</span>
−
|tag=LiRe93
+
M. Liskiewicz, R. Reischuk.
−
|authors=M. Liskiewicz, R. Reischuk
+
The complexity world below logarithmic space,
−
|title=The complexity world below logarithmic space
+
<i>Proceedings of the Structure in Complexity Theory Conference</i>, 64-78, 1993.
−
|journal=Proceedings of the Structure in Complexity Theory Conference
+
[https://doi.org/10.1109/SCT.1994.315816 doi:10.1109/SCT.1994.315816]
−
|srcdetail=1993, 64-78
+
[http://www.tcs.uni-luebeck.de/downloads/papers/1995/A9507.ps Author's webpage version]
−
}}
 
  
 
<span id="li11" style="color:maroon">[Li11]</span>
 
<span id="li11" style="color:maroon">[Li11]</span>
 
Y. D. Li.
 
Y. D. Li.
 
BQP and PPAD,
 
BQP and PPAD,
−
<i>Electronic Colloquium on Computational Complexity</i> TR11-103, 2011.
+
<i>Electronic Colloquium on Computational Complexity</i> [https://eccc.weizmann.ac.il/report/2011/103/ TR11-103], 2011.
 +
arXiv:[https://arxiv.org/abs/1108.0223 1108.0223 [cs.CC]]
  
 
<span id="ll76" style="color:maroon">[LL76]</span>
 
<span id="ll76" style="color:maroon">[LL76]</span>
Line 2,442: Line 2,690:
 
Relativization of questions about log space computability,
 
Relativization of questions about log space computability,
 
<i>Mathematical Systems Theory</i> 10:19-32, 1976.
 
<i>Mathematical Systems Theory</i> 10:19-32, 1976.
 +
[https://doi.org/10.1007/BF01683260 doi:10.1007/BF01683260]
  
 
<span id="lmn93" style="color:maroon">[LMN93]</span>
 
<span id="lmn93" style="color:maroon">[LMN93]</span>
Line 2,447: Line 2,696:
 
Constant depth circuits, Fourier transform, and learnability,
 
Constant depth circuits, Fourier transform, and learnability,
 
<i>Journal of the ACM</i> 40(3):607-620, 1993.
 
<i>Journal of the ACM</i> 40(3):607-620, 1993.
 +
[https://doi.org/10.1145/174130.174138 doi:10.1145/174130.174138]
 +
 +
<span id="lmsv01" style="color:maroon">[LMSV01]</span>
 +
C. Lautemann, P. McKenzie, T. Schwentick, H. Vollmer.
 +
The Descriptive Complexity Approach to LOGCFL.
 +
<i>J. Comput. Syst. Sci.</i> 62(4):629-652.
 +
[https://doi.org/10.1006/jcss.2000.1742 doi:10.1006/jcss.2000.1742]
  
 
<span id="lmt97" style="color:maroon">[LMT97]</span>
 
<span id="lmt97" style="color:maroon">[LMT97]</span>
 
K. Lange, P. McKenzie, and A. Tapp.
 
K. Lange, P. McKenzie, and A. Tapp.
 
Reversible space equals deterministic space (extended abstract),
 
Reversible space equals deterministic space (extended abstract),
−
<i>Proceedings of IEEE FOCS'97</i>, pp. 45-50, 1997.
+
<i>Journal of Computer and System Sciences</i>, 60(2):354-367, 2000.
 +
[https://doi.org/10.1006/jcss.1999.1672 doi:10.1006/jcss.1999.1672]
 +
Originally appeared in [https://doi.org/10.1109/CCC.1997.612299 CCC 1997]
  
 
<span id="lp82" style="color:maroon">[LP82]</span>
 
<span id="lp82" style="color:maroon">[LP82]</span>
Line 2,457: Line 2,715:
 
Symmetric space-bounded computation,
 
Symmetric space-bounded computation,
 
<i>Theoretical Computer Science</i> 19:161-187, 1982.
 
<i>Theoretical Computer Science</i> 19:161-187, 1982.
 +
[https://doi.org/10.1016/0304-3975(82)90058-5 doi:10.1016/0304-3975(82)90058-5]
  
 
<span id="ls74" style="color:maroon">[LS74]</span>
 
<span id="ls74" style="color:maroon">[LS74]</span>
 
E. A. Lamagna and J. E. Savage
 
E. A. Lamagna and J. E. Savage
 
Combinational complexity of some monotone functions,
 
Combinational complexity of some monotone functions,
−
<i>FOCS</i> 140-44, 1974.
+
<i>FOCS (previously SWAT)</i> 140-44, 1974.
 +
[https://doi.org/10.1109/SWAT.1974.9 doi:10.1109/SWAT.1974.9]
  
 
<span id="lut91" style="color:maroon">[Lut91]</span>
 
<span id="lut91" style="color:maroon">[Lut91]</span>
Line 2,467: Line 2,727:
 
An upward measure separation theorem,
 
An upward measure separation theorem,
 
<i>Theoretical Computer Science</i> 81:127-135, 1991.
 
<i>Theoretical Computer Science</i> 81:127-135, 1991.
 +
[https://doi.org/10.1016/0304-3975(91)90320-2 doi:10.1016/0304-3975(91)90320-2]
 +
[https://jacklutz.com/=PAPERS/ums.pdf Author's webpage version]
  
−
{{Reference
+
<span id="Lut93" style="color:maroon">[Lut93]</span>
−
    |tag=Lut93
+
J. H. Lutz.
−
    |authors=J. H. Lutz
+
The quantitative structure of exponential time,
−
    |title=The quantitative structure of exponential time
+
<i>Proc. 8th Structure in Complexity Theory Conference</i>, 158-175, 1993.
−
    |journal=Proc. 8th Structure in Complexity Theory Conference
+
[https://doi.org/10.1109/SCT.1993.336530 doi:10.1109/SCT.1993.336530]
−
    |srcdetail=(IEEE Comput. Soc. Press, 1993) 158-175
+
See also version in <i>Complexity Theory Retrospective II</i>, Springer, 1998.
−
}}[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.1845&rep=rep1&type=pdf]
 
  
 
<span id="lv97" style="color:maroon">[LV97]</span>
 
<span id="lv97" style="color:maroon">[LV97]</span>
 
M. Li and P. Vit&aacute;nyi.
 
M. Li and P. Vit&aacute;nyi.
 
<i>An Introduction to Kolmogorov Complexity and Its Applications</i> (second edition),
 
<i>An Introduction to Kolmogorov Complexity and Its Applications</i> (second edition),
−
Springer, 1997.
+
Springer, 1997. [https://doi.org/10.1007/978-0-387-49820-1 doi:10.1007/978-0-387-49820-1]
  
 
===== M =====
 
===== M =====
 +
<span id="mv97" style="color:maroon">[MV97]</span>
 +
Meena Mahajan and V. Vinay.
 +
Determinant: Combinatorics, Algorithms, and Complexity,
 +
<i>Chicago J. Theoret. Comput. Sci.</i>, Article 5, 1997. [http://dx.doi.org/10.4086/cjtcs.1997.005 doi:10.4086/cjtcs.1997.005]
  
 
<span id="m08" style="color:maroon">[M08]</span>
 
<span id="m08" style="color:maroon">[M08]</span>
 
L. Malka.
 
L. Malka.
−
How to achieve perfect simulation, and a complete problem for non-interactive perfect zero-knowledge. <i>IACR 5th Theory of Cryptography Conference (TCC)</i>, 2008.
+
How to achieve perfect simulation, and a complete problem for non-interactive perfect zero-knowledge.  
−
[http://www.cs.uvic.ca/~liorma/publications/NIZK9.pdf].
+
<i>J. Cryptology</i> 28:533-550, 2015.
 +
[https://doi.org/10.1007/s00145-013-9165-6 doi:10.1007/s00145-013-9165-6]
 +
Originally appeared in TCC 2008
 +
[https://www.lior.ca/publications/NIZK9.pdf Author's website version].
 +
 
 +
<span id="mah18" style="color:maroon">[Mah18]</span>
 +
U. Mahadev.
 +
Classical Verification of Quantum Computations,
 +
arXiv:[https://arxiv.org/abs/1804.01082 abs/1804.01082].
  
 
<span id="mah82" style="color:maroon">[Mah82]</span>
 
<span id="mah82" style="color:maroon">[Mah82]</span>
Line 2,492: Line 2,765:
 
Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis,
 
Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis,
 
<i>Journal of Computer and System Sciences</i> 25:130-143, 1982.
 
<i>Journal of Computer and System Sciences</i> 25:130-143, 1982.
 +
[https://doi.org/10.1016/0022-0000(82)90002-2 doi:10.1016/0022-0000(82)90002-2]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1980.40 FOCS 1980]
  
 
<span id="may94" style="color:maroon">[May94]</span>
 
<span id="may94" style="color:maroon">[May94]</span>
Line 2,497: Line 2,772:
 
Almost every set in exponential time is P-bi-immune,
 
Almost every set in exponential time is P-bi-immune,
 
<i>Theoretical Computer Science</i> 136(2):487-506, 1994.
 
<i>Theoretical Computer Science</i> 136(2):487-506, 1994.
 +
[https://doi.org/10.1016/0304-3975(94)00023-C doi:10.1016/0304-3975(94)00023-C]
 +
Originally appeared in [https://doi.org/10.1007/3-540-55808-X_38 MFCS 1992]
  
 
<span id="may94b" style="color:maroon">[May94b]</span>
 
<span id="may94b" style="color:maroon">[May94b]</span>
Line 2,502: Line 2,779:
 
<i>Contributions to the study of resource-bounded measure</i>,
 
<i>Contributions to the study of resource-bounded measure</i>,
 
PhD thesis, Universitat Politecnica de Catalunya, 1994.
 
PhD thesis, Universitat Politecnica de Catalunya, 1994.
 +
Available [https://eccc.weizmann.ac.il/static/books/Contributions_to_the_Study_of_Resource_Bounded_Measure/ on ECCC].
  
 
<span id="ms89" style="color:maroon">[MS89]</span>
 
<span id="ms89" style="color:maroon">[MS89]</span>
 
E. W. Mayr and A. Subramanian.  
 
E. W. Mayr and A. Subramanian.  
−
The complexity of circuit value and network stability, Proceedings of the Fourth Annual Conference on <i>Structure in Complexity Theory</i>, pp.114-123, 1989.
+
The complexity of circuit value and network stability,  
 +
<i>J. Comput. Syst. Sci.</i> 44(2):302-323, 1992.
 +
[https://doi.org/10.1016/0022-0000(92)90024-D doi:10.1016/0022-0000(92)90024-D]
 +
Originally appeared [https://doi.org/10.1109/SCT.1989.41817 in Complexity '89].
 +
Stanford technical report [http://i.stanford.edu/pub/cstr/reports/cs/tr/89/1278/CS-TR-89-1278.pdf STAN-CS-89-1278]
  
 
<span id="mc00" style="color:maroon">[MC00]</span>
 
<span id="mc00" style="color:maroon">[MC00]</span>
Line 2,511: Line 2,793:
 
Quantum automata and quantum grammars,
 
Quantum automata and quantum grammars,
 
<i>Theoretical Computer Science</i> 237:275-306, 2000.
 
<i>Theoretical Computer Science</i> 237:275-306, 2000.
 +
[https://doi.org/10.1016/S0304-3975(98)00191-1 doi:10.1016/S0304-3975(98)00191-1]
 +
Preprint available as arXiv:[https://arxiv.org/abs/quant-ph/9707031 quant-ph/9707031].
  
−
{{Reference
+
<span id="Mel00" style="color:maroon">[Mel00]</span>
−
    |tag=Mel00
+
D. van Melkebeek.
−
    |authors=D. Melkebeek
+
The zero-one law holds for BPP,
−
    |title=The zero-one law holds for BPP
+
<i>Theoretical Computer Science</i> 244(1-2):283-288, 2000.
−
    |journal=Theoretical Computer Science
+
[https://doi.org/10.1016/S0304-3975(00)00191-2 doi:10.1016/S0304-3975(00)00191-2]
−
    |srcdetail=Volume 244, Issues 1-2, 6 August 2000, Pages 283-288
 
−
}}
 
  
 
<span id="mes99" style="color:maroon">[Mes99]</span>
 
<span id="mes99" style="color:maroon">[Mes99]</span>
 
J. Messner.
 
J. Messner.
 
On optimal algorithms and optimal proof systems,
 
On optimal algorithms and optimal proof systems,
−
<i>Lecture Notes in Computer Science</i> 1563:541-550, 1999.
+
STACS, <i>Lecture Notes in Computer Science</i> 1563:541-550, 1999.
 +
[https://doi.org/10.1007/3-540-49116-3_51 doi:10.1007/3-540-49116-3_51]
  
 
<span id="mil76" style="color:maroon">[Mil76]</span>
 
<span id="mil76" style="color:maroon">[Mil76]</span>
Line 2,529: Line 2,812:
 
Riemann's hypothesis and tests for primality,
 
Riemann's hypothesis and tests for primality,
 
<i>Journal of Computer and System Sciences</i>, 13:300-317, 1976.
 
<i>Journal of Computer and System Sciences</i>, 13:300-317, 1976.
 +
[https://doi.org/10.1016/S0022-0000(76)80043-8 doi:10.1016/S0022-0000(76)80043-8]
  
 
<span id="mil92" style="color:maroon">[Mil92]</span>
 
<span id="mil92" style="color:maroon">[Mil92]</span>
Line 2,534: Line 2,818:
 
Circuit depth relative to a random oracle,
 
Circuit depth relative to a random oracle,
 
<i>Information Processing Letters</i> 42(6):295-298, 1992.
 
<i>Information Processing Letters</i> 42(6):295-298, 1992.
 +
[https://doi.org/10.1016/0020-0190(92)90225-K doi:10.1016/0020-0190(92)90225-K]
  
 
<span id="mn02" style="color:maroon">[MN02]</span>
 
<span id="mn02" style="color:maroon">[MN02]</span>
Line 2,539: Line 2,824:
 
Parallel quantum computation and quantum codes,
 
Parallel quantum computation and quantum codes,
 
<i>SIAM Journal on Computing</i> 31(3):799-815, 2002.
 
<i>SIAM Journal on Computing</i> 31(3):799-815, 2002.
 +
[https://doi.org/10.1137/S0097539799355053 doi:10.1137/S0097539799355053]
 
arXiv:[http://arxiv.org/abs/quant-ph/9808027 quant-ph/9808027].
 
arXiv:[http://arxiv.org/abs/quant-ph/9808027 quant-ph/9808027].
  
Line 2,545: Line 2,831:
 
On a subclass of pseudopolynomial problems,
 
On a subclass of pseudopolynomial problems,
 
<i>Mathematical Foundations of Computer Science (MFCS'80)</i>, Springer LNCS 88, pp. 414-425, 1980.
 
<i>Mathematical Foundations of Computer Science (MFCS'80)</i>, Springer LNCS 88, pp. 414-425, 1980.
 +
[https://doi.org/10.1007/BFb0022521 doi:10.1007/BFb0022521]
  
 
<span id="moo99" style="color:maroon">[Moo99]</span>
 
<span id="moo99" style="color:maroon">[Moo99]</span>
Line 2,555: Line 2,842:
 
Classification of search problems and their definability in bounded arithmetic,
 
Classification of search problems and their definability in bounded arithmetic,
 
master's thesis, University of Toronto, 2001.
 
master's thesis, University of Toronto, 2001.
 +
[https://hdl.handle.net/1807/16458 Permalink]
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2001/TR01-082/ TR01-082].
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2001/TR01-082/ TR01-082].
  
Line 2,561: Line 2,849:
 
Bounds to complexities of networks for sorting and for switching,
 
Bounds to complexities of networks for sorting and for switching,
 
<i>Journal of the ACM</i> 22:195-201, 1975.
 
<i>Journal of the ACM</i> 22:195-201, 1975.
 +
[https://doi.org/10.1145/321879.321882 doi:10.1145/321879.321882]
  
 
<span id="mp91" style="color:maroon">[MP91]</span>
 
<span id="mp91" style="color:maroon">[MP91]</span>
Line 2,566: Line 2,855:
 
On total functions, existence theorems, and computational complexity,
 
On total functions, existence theorems, and computational complexity,
 
<i>Theoretical Computer Science</i> 81(2):317-324, 1991.
 
<i>Theoretical Computer Science</i> 81(2):317-324, 1991.
 +
[https://doi.org/10.1016/0304-3975(91)90200-L doi:10.1016/0304-3975(91)90200-L]
  
 
<span id="mr95" style="color:maroon">[MR95]</span>
 
<span id="mr95" style="color:maroon">[MR95]</span>
Line 2,576: Line 2,866:
 
Geometric complexity theory I: An approach to the P vs. NP and related problems,
 
Geometric complexity theory I: An approach to the P vs. NP and related problems,
 
<i>SIAM Journal on Computing</i> 31(2):496-526, 2002.
 
<i>SIAM Journal on Computing</i> 31(2):496-526, 2002.
 +
[https://doi.org/10.1137/S009753970038715X doi:10.1137/S009753970038715X]
  
 
<span id="muc56" style="color:maroon">[Muc56]</span>
 
<span id="muc56" style="color:maroon">[Muc56]</span>
Line 2,585: Line 2,876:
 
P. B. Miltersen and N. V. Vinodchandran.
 
P. B. Miltersen and N. V. Vinodchandran.
 
Derandomizing Arthur-Merlin games using hitting sets,
 
Derandomizing Arthur-Merlin games using hitting sets,
−
<i>Proceedings of IEEE FOCS'99</i>, pp. 71-80, 1999.
+
<i>comput. complexity</i> 14:256–279, 2005.
 +
[https://doi.org/10.1007/s00037-005-0197-7 doi:10.1007/s00037-005-0197-7]
 +
Originally appeared in [https://doi.org/10.1109/SFFCS.1999.814579 FOCS 1999]
  
 
<span id="mvv87" style="color:maroon">[MVV87]</span>
 
<span id="mvv87" style="color:maroon">[MVV87]</span>
 
K. Mulmuley, U. V. Vazirani, and V. V. Vazirani.
 
K. Mulmuley, U. V. Vazirani, and V. V. Vazirani.
 
Matching is as easy as matrix inversion,
 
Matching is as easy as matrix inversion,
−
<i>Proceedings of ACM STOC'87</i>, pp. 345-354, 1987.
+
<i>Combinatorica</i> 7:105–113, 1987.
 +
[https://doi.org/10.1007/BF02579206 doi:10.1007/BF02579206]
 +
Originally appeared in [https://doi.org/10.1145/28395.383347 STOC 1987]
 +
[https://people.eecs.berkeley.edu/~vazirani/pubs/matching.pdf Author's website conference version]
  
 
<span id="mvw99" style="color:maroon">[MVW99]</span>
 
<span id="mvw99" style="color:maroon">[MVW99]</span>
Line 2,596: Line 2,892:
 
Super-polynomial versus half-exponential circuit size in the exponential hierarchy,
 
Super-polynomial versus half-exponential circuit size in the exponential hierarchy,
 
<i>Proceedings of the 5th Annual Conference on Computing and Combinatorics (COCOON'99)</i>, pp. 210-220, Lecture Notes in Computer Science 1627, Springer-Verlag, 1999.
 
<i>Proceedings of the 5th Annual Conference on Computing and Combinatorics (COCOON'99)</i>, pp. 210-220, Lecture Notes in Computer Science 1627, Springer-Verlag, 1999.
 +
[https://doi.org/10.1007/3-540-48686-0_21 doi:10.1007/3-540-48686-0_21]
  
 
<span id="mw05" style="color:maroon">[MW05]</span>
 
<span id="mw05" style="color:maroon">[MW05]</span>
Line 2,601: Line 2,898:
 
Quantum Arthur-Merlin Games,
 
Quantum Arthur-Merlin Games,
 
<i>Computational Complexity</i>, 14(2):122-152, 2005.
 
<i>Computational Complexity</i>, 14(2):122-152, 2005.
 +
[https://doi.org/10.1007/s00037-005-0194-x doi:10.1007/s00037-005-0194-x]
 
arXiv:[http://arxiv.org/abs/cs/0506068 cs/0506068].
 
arXiv:[http://arxiv.org/abs/cs/0506068 cs/0506068].
  
Line 2,614: Line 2,912:
 
<i>Quantum Computation and Quantum Information</i>,
 
<i>Quantum Computation and Quantum Information</i>,
 
Cambridge University Press, 2000.
 
Cambridge University Press, 2000.
 +
[https://doi.org/10.1017/CBO9780511976667 doi:10.1017/CBO9780511976667]
  
 
<span id="nhk00" style="color:maroon">[NHK00]</span>
 
<span id="nhk00" style="color:maroon">[NHK00]</span>
Line 2,619: Line 2,918:
 
Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction,
 
Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction,
 
<i>Proceedings of COCOON'2000 (Computing and Combinatorics)</i>, Springer LNCS 1858, pp. 467-476, 2000.
 
<i>Proceedings of COCOON'2000 (Computing and Combinatorics)</i>, Springer LNCS 1858, pp. 467-476, 2000.
 +
[https://doi.org/10.1007/3-540-44968-X_46 doi:10.1007/3-540-44968-X_46]
  
 
<span id="nie02" style="color:maroon">[Nie02]</span>
 
<span id="nie02" style="color:maroon">[Nie02]</span>
Line 2,624: Line 2,924:
 
The Growing Context-Sensitive Languages Are the Acyclic Context-Sensitive Languages,
 
The Growing Context-Sensitive Languages Are the Acyclic Context-Sensitive Languages,
 
<i>Developments in Language Theory</i>. LNCS 2295, pp. 197-205.
 
<i>Developments in Language Theory</i>. LNCS 2295, pp. 197-205.
−
</span>
+
[https://doi.org/10.1007/3-540-46011-X_16 doi:10.1007/3-540-46011-X_16]
  
 
<span id="nis02" style="color:maroon">[Nis02]</span>
 
<span id="nis02" style="color:maroon">[Nis02]</span>
 
T. Nishino.
 
T. Nishino.
 
Mathematical models of quantum computation,
 
Mathematical models of quantum computation,
−
New Gen. Comput. 20 (2002), no 4, 317-337.
+
<i>New Gen. Comput.</i> 20 (2002), no 4, 317-337.
 +
[https://doi.org/10.1007/BF03037370 doi:10.1007/BF03037370]
  
 
<span id="nis92" style="color:maroon">[Nis92]</span>
 
<span id="nis92" style="color:maroon">[Nis92]</span>
 
N. Nisan.
 
N. Nisan.
−
RL is contained in SC,
+
RL &subseteq; SC,
−
<i>Proceedings of ACM STOC'92</i>, pp. 619-623, 1992.
+
<i>comput. complexity</i> 4:1-11, 1994.
 +
[https://doi.org/10.1007/BF01205052 doi:10.1007/BF01205052]
 +
Originally appeared in [https://doi.org/10.1145/129712.129772 STOC 1992].
 +
 
 +
<span id="nis93" style="color:maroon">[Nis93]</span>
 +
N. Nisan.
 +
On read-once vs. multiple access to randomness in logspace
 +
<i>Theoretical Computer Science</i> 107:135–144, 1993.  
 +
[https://doi.org/10.1016/0304-3975(93)90258-U 10.1016/0304-3975(93)90258-U]
 +
Originally appeared in [https://doi.org/10.1109/SCT.1990.113966 Structure in Complexity Theory Conference, 1990].
  
 
<span id="nr97" style="color:maroon">[NR97]</span>
 
<span id="nr97" style="color:maroon">[NR97]</span>
 
M. Naor and O. Reingold.
 
M. Naor and O. Reingold.
 
Number-theoretic constructions of efficient pseudorandom functions,
 
Number-theoretic constructions of efficient pseudorandom functions,
−
<i>Proceedings of IEEE FOCS'97</i>, pp. 458-467, 1997.
+
<i>Journal of the ACM</i>, 51(2):231-262, 2004.
 +
[https://doi.org/10.1145/972639.972643 doi:10.1145/972639.972643]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1997.646134 FOCS 1997].
  
 
<span id="nr98" style="color:maroon">[NR98]</span>
 
<span id="nr98" style="color:maroon">[NR98]</span>
Line 2,645: Line 2,957:
 
Unambiguous computations and locally definable acceptance types,
 
Unambiguous computations and locally definable acceptance types,
 
<i>Theoretical Computer Science</i> 194:137-161, 1998.
 
<i>Theoretical Computer Science</i> 194:137-161, 1998.
 +
[https://doi.org/10.1016/S0304-3975(97)00005-4 doi:10.1016/S0304-3975(97)00005-4]
  
 
<span id="nrr01" style="color:maroon">[NRR01]</span>
 
<span id="nrr01" style="color:maroon">[NRR01]</span>
 
M. Naor, O. Reingold, and A. Rosen.
 
M. Naor, O. Reingold, and A. Rosen.
 
Pseudo-random functions and factoring,
 
Pseudo-random functions and factoring,
 +
<i>SIAM J. Comput.</i>, 31(5):1383-1404, 2012.
 +
[https://doi.org/10.1137/S0097539701389257 doi:S0097539701389257]
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2001/TR01-064/ TR01-064].
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2001/TR01-064/ TR01-064].
  
Line 2,655: Line 2,970:
 
Average-case computations - comparing AvgP, HP, and Nearly-P,
 
Average-case computations - comparing AvgP, HP, and Nearly-P,
 
<i>Proceedings of IEEE Complexity'2005</i>, pp. 235-242, 2005.
 
<i>Proceedings of IEEE Complexity'2005</i>, pp. 235-242, 2005.
−
[http://www.thi.uni-hannover.de/forschung/publikationen/daten/ni-sc05.pdf http://www.thi.uni-hannover.de/forschung/publikationen/daten/ni-sc05.pdf].
+
[https://doi.org/10.1109/CCC.2005.4 doi:10.1109/CCC.2005.4]
  
 
<span id="nsw92" style="color:maroon">[NSW92]</span>
 
<span id="nsw92" style="color:maroon">[NSW92]</span>
Line 2,661: Line 2,976:
 
Undirected connectivity in O(log<sup>1.5</sup>n) space,
 
Undirected connectivity in O(log<sup>1.5</sup>n) space,
 
<i>Proceedings of IEEE FOCS'92</i>, pp. 24-29, 1992.
 
<i>Proceedings of IEEE FOCS'92</i>, pp. 24-29, 1992.
 +
[https://doi.org/10.1109/SFCS.1992.267822 doi:10.1109/SFCS.1992.267822]
  
 
<span id="nt95" style="color:maroon">[NT95]</span>
 
<span id="nt95" style="color:maroon">[NT95]</span>
 
N. Nisan and A. Ta-Shma.
 
N. Nisan and A. Ta-Shma.
 
Symmetric logspace is closed under complement,
 
Symmetric logspace is closed under complement,
−
<i>Proceedings of ACM STOC'95</i>, pp. 140-146, 1995.
+
<i>Chicago J. Theoret. Comput. Sci.</i>, Article 1, 1995.
−
ECCC [http://eccc.uni-trier.de/eccc-reports/1994/TR94-003/ TR94-003].
+
[http://dx.doi.org/10.4086/cjtcs.1995.001 doi:10.4086/cjtcs.1995.001]
 +
Originally appeared in [https://doi.org/10.1145/225058.225101 STOC 1995],
 +
preprint ECCC [http://eccc.uni-trier.de/eccc-reports/1994/TR94-003/ TR94-003].
  
 
<span id="nw94" style="color:maroon">[NW94]</span>
 
<span id="nw94" style="color:maroon">[NW94]</span>
Line 2,672: Line 2,990:
 
Hardness versus randomness,
 
Hardness versus randomness,
 
<i>Journal of Computer and System Sciences</i> 49:149-167, 1994.
 
<i>Journal of Computer and System Sciences</i> 49:149-167, 1994.
 +
[https://doi.org/10.1016/S0022-0000(05)80043-1 doi:10.1016/S0022-0000(05)80043-1]
 +
[https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf Author's webpage version]
  
 
<span id="ny03" style="color:maroon">[NY03]</span>
 
<span id="ny03" style="color:maroon">[NY03]</span>
 
H. Nishimura and T. Yamakami.
 
H. Nishimura and T. Yamakami.
 
Polynomial time quantum computation with advice,
 
Polynomial time quantum computation with advice,
 +
<i>Inform. Proc. Lett.</i>, 90(4):195-204, 2004.
 +
[https://doi.org/10.1016/j.ipl.2004.02.005 doi:10.1016/j.ipl.2004.02.005]
 
arXiv:[http://arxiv.org/abs/quant-ph/0305100 quant-ph/0305100],
 
arXiv:[http://arxiv.org/abs/quant-ph/0305100 quant-ph/0305100],
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-059/ TR03-059], 2003.
 
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-059/ TR03-059], 2003.
Line 2,682: Line 3,004:
 
H. Nishimura and T. Yamakami.
 
H. Nishimura and T. Yamakami.
 
An algorithmic argument for query complexity lower bounds of advised quantum computation,
 
An algorithmic argument for query complexity lower bounds of advised quantum computation,
−
arXiv:[http://arxiv.org/abs/quant-ph/0312003 quant-ph/0312003], 2003.
+
<i>MFCS</i>, pp. 827–838, 2004.
 +
[https://doi.org/10.1007/978-3-540-28629-5_65 doi:10.1007/978-3-540-28629-5_65]
 +
arXiv:[http://arxiv.org/abs/quant-ph/0312003 quant-ph/0312003]
  
 
===== O =====
 
===== O =====
Line 2,690: Line 3,014:
 
On serializable languages,
 
On serializable languages,
 
<i>International Journal of Foundations of Computer Science</i> 5(3-4):303-318, 1994.
 
<i>International Journal of Foundations of Computer Science</i> 5(3-4):303-318, 1994.
 +
[https://doi.org/10.1142/S0129054194000177 doi:10.1142/S0129054194000177]
  
 
<span id="oh93" style="color:maroon">[OH93]</span>
 
<span id="oh93" style="color:maroon">[OH93]</span>
Line 2,695: Line 3,020:
 
A complexity theory for feasible closure properties,
 
A complexity theory for feasible closure properties,
 
<i>Journal of Computer and System Sciences</i> 46(3):295-325, 1993.
 
<i>Journal of Computer and System Sciences</i> 46(3):295-325, 1993.
 +
[https://doi.org/10.1016/0022-0000(93)90006-I doi:10.1016/0022-0000(93)90006-I]
  
 
<span id="oka96" style="color:maroon">[Oka96]</span>
 
<span id="oka96" style="color:maroon">[Oka96]</span>
 
T. Okamoto.
 
T. Okamoto.
 
On relationships between statistical zero-knowledge proofs,
 
On relationships between statistical zero-knowledge proofs,
−
<i>Proceedings of ACM STOC'96</i>, 1996.
+
<i>Journal of Computer and System Sciences</i> 60(1):47-108, 2000.
 +
[https://doi.org/10.1006/jcss.1999.1664 doi:10.1006/jcss.1999.1664]
 +
Originally appeared in [https://doi.org/10.1145/237814.238016 STOC 1996].
  
 
<span id="oks94" style="color:maroon">[OKS+94]</span>
 
<span id="oks94" style="color:maroon">[OKS+94]</span>
Line 2,705: Line 3,033:
 
Instance complexity,
 
Instance complexity,
 
<i>Journal of the ACM</i> 41:96-121, 1994.
 
<i>Journal of the ACM</i> 41:96-121, 1994.
 +
[https://doi.org/10.1145/174644.174648 doi:10.1145/174644.174648]
  
 
<span id="ost91" style="color:maroon">[Ost91]</span>
 
<span id="ost91" style="color:maroon">[Ost91]</span>
Line 2,710: Line 3,039:
 
One-way functions, hard on average problems and statistical zero-knowledge proofs,
 
One-way functions, hard on average problems and statistical zero-knowledge proofs,
 
<i>Proceedings of IEEE Complexity'91</i>, pp. 51-59, 1991.
 
<i>Proceedings of IEEE Complexity'91</i>, pp. 51-59, 1991.
 +
[https://doi.org/10.1109/SCT.1991.160253 doi:10.1109/SCT.1991.160253]
 +
[https://web.cs.ucla.edu/~rafail/PUBLIC/06.pdf Author's website version]
  
 
<span id="ow93" style="color:maroon">[OW93]</span>
 
<span id="ow93" style="color:maroon">[OW93]</span>
Line 2,715: Line 3,046:
 
One-way functions are essential for non-trivial zero-knowledge,
 
One-way functions are essential for non-trivial zero-knowledge,
 
<i>Proceedings of the 2nd Israel Symposium on Theory of Computing and Systems (ISTCS-93)</i>, 1993.
 
<i>Proceedings of the 2nd Israel Symposium on Theory of Computing and Systems (ISTCS-93)</i>, 1993.
 +
[https://doi.org/10.1109/ISTCS.1993.253489 doi:10.1109/ISTCS.1993.253489]
 +
[https://web.cs.ucla.edu/~rafail/PUBLIC/14.pdf Author's website version]
  
 
===== P =====
 
===== P =====
Line 2,721: Line 3,054:
 
C. H. Papadimitriou.
 
C. H. Papadimitriou.
 
Games against nature,
 
Games against nature,
−
<i>Proceedings of IEEE FOCS'83</i>, pp. 446-450, 1983.
+
<i>J. Comput. Syst. Sci.</i> 31(2):288-301, 1985.
 +
[https://doi.org/10.1016/0022-0000(85)90045-5 doi:10.1016/0022-0000(85)90045-5]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1983.20 <i>Proceedings of IEEE FOCS'83</i>], pp. 446-450, 1983.
  
 
<span id="pap90" style="color:maroon">[Pap90]</span>
 
<span id="pap90" style="color:maroon">[Pap90]</span>
Line 2,727: Line 3,062:
 
On graph-theoretic lemmata and complexity classes,
 
On graph-theoretic lemmata and complexity classes,
 
<i>Proceedings of IEEE FOCS'90</i>, pp. 794-801, 1990.
 
<i>Proceedings of IEEE FOCS'90</i>, pp. 794-801, 1990.
 +
[https://doi.org/10.1109/FSCS.1990.89602 doi:10.1109/FSCS.1990.89602]
  
 
<span id="pap94" style="color:maroon">[Pap94]</span>
 
<span id="pap94" style="color:maroon">[Pap94]</span>
Line 2,737: Line 3,073:
 
On the complexity of the parity argument and other inefficient proofs of existence,
 
On the complexity of the parity argument and other inefficient proofs of existence,
 
<i>Journal of Computer and System Sciences</i> 48(3):498-532, 1994.
 
<i>Journal of Computer and System Sciences</i> 48(3):498-532, 1994.
 +
[https://doi.org/10.1016/S0022-0000(05)80063-7 doi:10.1016/S0022-0000(05)80063-7]
  
 
{{Reference
 
{{Reference
Line 2,744: Line 3,081:
 
     |journal=Proceedings of the 22nd Annual IEEE Conference on Computational Complexity
 
     |journal=Proceedings of the 22nd Annual IEEE Conference on Computational Complexity
 
     |srcdetail=347-357, 2007
 
     |srcdetail=347-357, 2007
 +
    |doi=10.1109/CCC.2007.20
 
}}
 
}}
 +
 +
<span id="pm15" style="color:maroon">[PM15]</span>
 +
S. Piddock and A. Montanaro.
 +
The complexity of antiferromagnetic interactions and 2D lattices.
 +
arXiv:[https://arxiv.org/abs/1506.04014 1506.04014], 2015.
  
 
<span id="pos44" style="color:maroon">[Pos44]</span>
 
<span id="pos44" style="color:maroon">[Pos44]</span>
Line 2,750: Line 3,093:
 
Recursively enumerable sets of positive integers and their decision problems,
 
Recursively enumerable sets of positive integers and their decision problems,
 
<i>Bulletin of the American Mathematical Society</i> 50:284-316, 1944.
 
<i>Bulletin of the American Mathematical Society</i> 50:284-316, 1944.
 +
[https://doi.org/10.1090/S0002-9904-1944-08111-1 doi:10.1090/S0002-9904-1944-08111-1]
  
 
<span id="pp00" style="color:maroon">[PP00]</span>
 
<span id="pp00" style="color:maroon">[PP00]</span>
Line 2,755: Line 3,099:
 
Efficient factorization with a single pure qubit and log N mixed qubits,
 
Efficient factorization with a single pure qubit and log N mixed qubits,
 
<i>Physical Review Letters</i> 85:3049, 2000.
 
<i>Physical Review Letters</i> 85:3049, 2000.
 +
[https://doi.org/10.1103/PhysRevLett.85.3049 doi:10.1103/PhysRevLett.85.3049]
 
arXiv:[http://arxiv.org/abs/quant-ph/0001066 quant-ph/0001066].
 
arXiv:[http://arxiv.org/abs/quant-ph/0001066 quant-ph/0001066].
  
Line 2,761: Line 3,106:
 
On determinism versus nondeterminism and related problems,
 
On determinism versus nondeterminism and related problems,
 
<i>Proceedings of IEEE FOCS'83</i>, pp. 429-438, 1983.
 
<i>Proceedings of IEEE FOCS'83</i>, pp. 429-438, 1983.
 +
[https://doi.org/10.1109/SFCS.1983.39 doi:10.1109/SFCS.1983.39]
  
 
<span id="pps14" style="color:maroon">[PPS14]</span>
 
<span id="pps14" style="color:maroon">[PPS14]</span>
Line 2,766: Line 3,112:
 
Overlays and limited memory communication,
 
Overlays and limited memory communication,
 
<i>Proceedings of IEEE CCC'14</i>, pp. 298-308, 2014.
 
<i>Proceedings of IEEE CCC'14</i>, pp. 298-308, 2014.
 +
[https://doi.org/10.1109/CCC.2014.37 doi:10.1109/CCC.2014.37]
  
 
<span id="pra74" style="color:maroon">[Pra74]</span>
 
<span id="pra74" style="color:maroon">[Pra74]</span>
 
V. R. Pratt.
 
V. R. Pratt.
 
The power of negative thinking in multiplying Boolean matrices,
 
The power of negative thinking in multiplying Boolean matrices,
−
<i>STOC '74: Proceedings of the sixth annual ACM Symposium on Theory of Computing</i>, 80-83, 1974.
+
[https://doi.org/10.1137/0204027 doi:10.1137/0204027]
 +
Originally appeared in [https://doi.org/10.1145/800119.803887 <i>STOC '74: Proceedings of the sixth annual ACM Symposium on Theory of Computing</i>], 80-83, 1974.
  
 
<span id="pra75" style="color:maroon">[Pra75]</span>
 
<span id="pra75" style="color:maroon">[Pra75]</span>
Line 2,776: Line 3,124:
 
Every prime has a succinct certificate,
 
Every prime has a succinct certificate,
 
<i>SIAM Journal on Computing</i>, 4:214-220, 1975.
 
<i>SIAM Journal on Computing</i>, 4:214-220, 1975.
 +
[https://doi.org/10.1137/0204018 doi:10.1137/0204018]
  
 
<span id="ps86" style="color:maroon">[PS86]</span>
 
<span id="ps86" style="color:maroon">[PS86]</span>
Line 2,781: Line 3,130:
 
Probabilistic communication complexity,
 
Probabilistic communication complexity,
 
<i>Journal of Computer and System Sciences</i>, 33(1):106-123, 1986.
 
<i>Journal of Computer and System Sciences</i>, 33(1):106-123, 1986.
 +
[https://doi.org/10.1016/0022-0000(86)90046-2 doi:10.1016/0022-0000(86)90046-2]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1984.715908 FOCS '84]
  
 
<span id="pv04" style="color:maroon">[PV04]</span>
 
<span id="pv04" style="color:maroon">[PV04]</span>
 
A. Pavan and N. V. Vinodchandran.
 
A. Pavan and N. V. Vinodchandran.
−
[http://ftp.eccc.uni-trier.de/eccc-reports/2004/TR04-053/ TR04-053].
+
Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility
 +
[https://eccc.weizmann.ac.il/report/2004/053/ ECCC TR04-053].
  
 
<span id="py84" style="color:maroon">[PY84]</span>
 
<span id="py84" style="color:maroon">[PY84]</span>
Line 2,790: Line 3,142:
 
The complexity of facets (and some facets of complexity),
 
The complexity of facets (and some facets of complexity),
 
<i>Journal of Computer and System Sciences</i> 28:244-259, 1984.
 
<i>Journal of Computer and System Sciences</i> 28:244-259, 1984.
 +
[https://doi.org/10.1016/0022-0000(84)90068-0 doi:10.1016/0022-0000(84)90068-0]
  
 
<span id="py88" style="color:maroon">[PY88]</span>
 
<span id="py88" style="color:maroon">[PY88]</span>
 
C. H. Papadimitriou and M. Yannakakis.
 
C. H. Papadimitriou and M. Yannakakis.
 
Optimization, approximation, and complexity classes,
 
Optimization, approximation, and complexity classes,
−
<i>Proceedings of ACM STOC'88</i>, pp. 229-234, 1988.
+
<i>J. Comput. Syst. Sci.</i> 43(3): 425-440 (1991)
 +
[https://doi.org/10.1016/0022-0000(91)90023-X doi:10.1016/0022-0000(91)90023-X]
 +
Originally appeared in [https://doi.org/10.1145/62212.62233 <i>Proceedings of ACM STOC'88</i>], pp. 229-234, 1988.
  
 
<span id="py96" style="color:maroon">[PY96]</span>
 
<span id="py96" style="color:maroon">[PY96]</span>
Line 2,800: Line 3,155:
 
On limited nondeterminism and the complexity of the VC dimension,
 
On limited nondeterminism and the complexity of the VC dimension,
 
<i>Journal of Computer and System Sciences</i> 53(2):161-170, 1996.
 
<i>Journal of Computer and System Sciences</i> 53(2):161-170, 1996.
 +
[https://doi.org/10.1006/jcss.1996.0058 doi:10.1006/jcss.1996.0058]
  
 
<span id="pz83" style="color:maroon">[PZ83]</span>
 
<span id="pz83" style="color:maroon">[PZ83]</span>
Line 2,805: Line 3,161:
 
Two remarks on the power of counting,
 
Two remarks on the power of counting,
 
<i>Proceedings of the 6th GI Conference in Theoretical Computer Science</i>, Lecture Notes in Computer Science Vol. 145, Springer-Verlag, pp. 269-276, 1983.
 
<i>Proceedings of the 6th GI Conference in Theoretical Computer Science</i>, Lecture Notes in Computer Science Vol. 145, Springer-Verlag, pp. 269-276, 1983.
 +
[https://doi.org/10.1007/BFb0009651 doi:10.1007/BFb0009651]
  
 
===== R =====
 
===== R =====
Line 2,814: Line 3,171:
 
ECCC [http://eccc.uni-trier.de/eccc-reports/1997/TR97-014/ TR97-014],
 
ECCC [http://eccc.uni-trier.de/eccc-reports/1997/TR97-014/ TR97-014],
 
DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1997/97-46.html TR 97-46].
 
DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1997/97-46.html TR 97-46].
 +
[https://doi.org/10.1137/S0097539798339041 doi:10.1137/S0097539798339041]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1997.646113 FOCS 1997], pp. 244-253.
  
 
<span id="rab60" style="color:maroon">[Rab60]</span>
 
<span id="rab60" style="color:maroon">[Rab60]</span>
Line 2,897: Line 3,256:
 
An average-case depth hierarchy theorem for Boolean circuits,
 
An average-case depth hierarchy theorem for Boolean circuits,
 
<i>Foundations of Computer Science (FOCS)</i>, 2015.
 
<i>Foundations of Computer Science (FOCS)</i>, 2015.
 +
 +
<span id="rg20" style="color:maroon">[RG20]</span>
 +
V. Rozhoň and M. Ghaffari.
 +
Polylogarithmic-time deterministic network decomposition and distributed derandomization,
 +
<i>Symposium on Theory of Computing (STOC)</i>, 2020.
 +
 +
<span id="rt92" style="color:maroon">[RT92]</span>
 +
J. Reif and S. Tate.
 +
On Threshold Circuits and Polynomial Computation,
 +
<i>SIAM J. Comput.</i>, 21(5) 896-908, 1992.
  
 
<span id="rt18" style="color:maroon">[RT18]</span>
 
<span id="rt18" style="color:maroon">[RT18]</span>
Line 2,982: Line 3,351:
 
A low and a high hierarchy within NP,
 
A low and a high hierarchy within NP,
 
<i>Journal of Computer and System Sciences</i> 27:14-28, 1983.
 
<i>Journal of Computer and System Sciences</i> 27:14-28, 1983.
 +
[https://doi.org/10.1016/0022-0000(83)90027-2 DOI]
  
 
<span id="sch86" style="color:maroon">[Sch86]</span>
 
<span id="sch86" style="color:maroon">[Sch86]</span>
Line 3,016: Line 3,386:
 
Separating nondeterministic time complexity classes,
 
Separating nondeterministic time complexity classes,
 
<i>Journal of the ACM</i> 25:146-167, 1978.
 
<i>Journal of the ACM</i> 25:146-167, 1978.
 +
 +
<span id="sha10" style="color:maroon">[Sha10]</span>
 +
M. Schaefer.
 +
Complexity of some geometric and topological problems,
 +
<i>Graph Drawing</i>, LNCS 5849, Springer-Verlag, 334–344, 2010.
  
 
<span id="sha90" style="color:maroon">[Sha90]</span>
 
<span id="sha90" style="color:maroon">[Sha90]</span>
Line 3,165: Line 3,540:
  
 
===== T =====
 
===== T =====
 +
 +
<span id="tak12" style="color:maroon">[Tak12]</span>
 +
Y. Takahashi. and T. Seiichiro
 +
Collapse of the hierarchy of constant-depth exact quantum circuits
 +
<i>Computational complexity</i>, 25.4:849-881, 2016.
 +
[http://dx.doi.org/10.1109/CCC.2013.25 doi:10.1109/CCC.2013.25]
 +
  
 
<span id="tan07" style="color:maroon">[Tan07]</span>
 
<span id="tan07" style="color:maroon">[Tan07]</span>
Line 3,170: Line 3,552:
 
Logspace Optimization Problems and Their Approximability Properties,
 
Logspace Optimization Problems and Their Approximability Properties,
 
<i>Theory of Computing Systems</i>, 41:327-350, 2007.
 
<i>Theory of Computing Systems</i>, 41:327-350, 2007.
 +
[https://doi.org/10.1007/s00224-007-2011-1 doi:10.1007/s00224-007-2011-1]
 +
ECCC [https://eccc.weizmann.ac.il/report/2003/077/ TR03-077]
  
 
<span id="tar88" style="color:maroon">[Tar88]</span>
 
<span id="tar88" style="color:maroon">[Tar88]</span>
Line 3,175: Line 3,559:
 
The gap between monotone and non-monotone circuit complexity is exponential,
 
The gap between monotone and non-monotone circuit complexity is exponential,
 
<i>Combinatorica</i>, 8:141-142, 1988.
 
<i>Combinatorica</i>, 8:141-142, 1988.
 +
[https://doi.org/10.1007/BF02122563 doi:10.1007/BF02122563]
 +
[https://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf Author's webpage version]
  
 
<span id="tar89" style="color:maroon">[Tar89]</span>
 
<span id="tar89" style="color:maroon">[Tar89]</span>
Line 3,180: Line 3,566:
 
Query complexity, or why is it difficult to separate NP<sup>A</sup> intersect coNP<sup>A</sup> from P<sup>A</sup> by random oracles A,
 
Query complexity, or why is it difficult to separate NP<sup>A</sup> intersect coNP<sup>A</sup> from P<sup>A</sup> by random oracles A,
 
<i>Combinatorica</i>, 9:385-392, 1989.
 
<i>Combinatorica</i>, 9:385-392, 1989.
 +
[https://doi.org/10.1007/BF02125350 doi:10.1007/BF02125350]
  
 
<span id="tha98" style="color:maroon">[Tha98]</span>
 
<span id="tha98" style="color:maroon">[Tha98]</span>
Line 3,189: Line 3,576:
 
<span id="tod89" style="color:maroon">[Tod89]</span>
 
<span id="tod89" style="color:maroon">[Tod89]</span>
 
S. Toda.
 
S. Toda.
−
On the computational power of PP and P,
+
On the computational power of PP and (+)P,
 
<i>Proceedings of IEEE FOCS'89</i>, pp. 514-519, 1989.
 
<i>Proceedings of IEEE FOCS'89</i>, pp. 514-519, 1989.
 +
[https://doi.org/10.1109/SFCS.1989.63527 doi:10.1109/SFCS.1989.63527]
 +
 +
<span id="tod91" style="color:maroon">[Tod91]</span>
 +
S. Toda.
 +
Counting problems computationally equivalent to the
 +
determinant,
 +
manuscript, 1991.
  
 
<span id="tor00" style="color:maroon">[Tor00]</span>
 
<span id="tor00" style="color:maroon">[Tor00]</span>
Line 3,196: Line 3,590:
 
On the hardness of graph isomorphism,
 
On the hardness of graph isomorphism,
 
<i>Proceedings of IEEE FOCS'2000</i>, pp. 180-186, 2000.
 
<i>Proceedings of IEEE FOCS'2000</i>, pp. 180-186, 2000.
 +
[https://doi.org/10.1109/SFCS.2000.892080 doi:10.1109/SFCS.2000.892080]
  
 
<span id="tor88" style="color:maroon">[Tor88]</span>
 
<span id="tor88" style="color:maroon">[Tor88]</span>
 
J. Tor&aacute;n.
 
J. Tor&aacute;n.
 
Structural Properties of the Counting Hierarchies,
 
Structural Properties of the Counting Hierarchies,
−
Ph.D Theis, 1988.
+
Ph.D Thesis, 1988.
 +
[http://hdl.handle.net/2117/189084 http://hdl.handle.net/2117/189084]
  
 
<span id="tor90" style="color:maroon">[Tor90]</span>
 
<span id="tor90" style="color:maroon">[Tor90]</span>
Line 3,206: Line 3,602:
 
Counting the number of solutions,
 
Counting the number of solutions,
 
<i>Proceedings of 15th Conference on Mathematical Foundations of Computer Science (MFCS)</i>, pp. 121-135, Springer-Verlag Lecture Notes in Computer Science 452, 1990.
 
<i>Proceedings of 15th Conference on Mathematical Foundations of Computer Science (MFCS)</i>, pp. 121-135, Springer-Verlag Lecture Notes in Computer Science 452, 1990.
 +
[https://doi.org/10.1007/BFb0029600 doi:10.1007/BFb0029600]
  
 
<span id="tor91" style="color:maroon">[Tor91]</span>
 
<span id="tor91" style="color:maroon">[Tor91]</span>
Line 3,211: Line 3,608:
 
Complexity classes defined by counting quantifiers,
 
Complexity classes defined by counting quantifiers,
 
<i>Journal of the ACM</i> 38:753-774, 1991.
 
<i>Journal of the ACM</i> 38:753-774, 1991.
 +
[https://doi.org/10.1145/116825.116858 doi:10.1145/116825.116858]
  
 
<span id="tur36" style="color:maroon">[Tur36]</span>
 
<span id="tur36" style="color:maroon">[Tur36]</span>
Line 3,216: Line 3,614:
 
On computable numbers, with an application to the <i>Entscheidungsproblem</i>,
 
On computable numbers, with an application to the <i>Entscheidungsproblem</i>,
 
<i>Proceedings of the London Mathematical Society</i> 2(42):230-265, 1936; 2(43):544-546, 1937.
 
<i>Proceedings of the London Mathematical Society</i> 2(42):230-265, 1936; 2(43):544-546, 1937.
 +
[https://doi.org/10.1112/plms/s2-42.1.230 doi:10.1112/plms/s2-42.1.230]
  
 
<span id="tv02" style="color:maroon">[TV02]</span>
 
<span id="tv02" style="color:maroon">[TV02]</span>
 
L. Trevisan and S. Vadhan.
 
L. Trevisan and S. Vadhan.
 
Pseudorandomness and average-case complexity via uniform reductions,
 
Pseudorandomness and average-case complexity via uniform reductions,
−
<i>Proceedings of CCC'2002</i>, pp. 129-138, 2002.
+
<i>computational complexity</i> 16:331-364, 2007. [https://doi.org/10.1007/s00037-007-0233-x doi:10.1007/s00037-007-0233-x]
 +
Originally appeared in [https://doi.org/10.1109/CCC.2002.1004348 CCC 2002]. [https://people.seas.harvard.edu/~salil/research/uniform-cc.pdf Author's webpage version]
  
 
===== U =====
 
===== U =====
Line 3,227: Line 3,627:
 
C. Umans.
 
C. Umans.
 
The minimum equivalent DNF problem and shortest implicants,
 
The minimum equivalent DNF problem and shortest implicants,
−
<i>Proceedings of IEEE FOCS'98</i>, pp. 556-563, 1998.
+
<i> J. Comput. Syst. Sci.</i> 63(4):597-611, 2001. [https://doi.org/10.1006/jcss.2001.1775 doi:10.1006/jcss.2001.1775]
 +
Originally appeared in <i>Proceedings of IEEE FOCS'98</i>, pp. 556-563, 1998. [https://doi.org/10.1109/SFCS.1998.743506 doi:10.1109/SFCS.1998.743506]
  
 
===== V =====
 
===== V =====
Line 3,234: Line 3,635:
 
S. Vadhan.
 
S. Vadhan.
 
An Unconditional Study of Computational Zero Knowledge,
 
An Unconditional Study of Computational Zero Knowledge,
−
ECCC [http://eccc.hpi-web.de/eccc-reports/2006/TR06-056/ TR06-056].
+
<i>SIAM J. Comput.</i> 36(4):1160-1214, 2006.
 +
[https://doi.org/10.1137/S0097539705447207 doi:10.1137/S0097539705447207]
 +
Originally appeared in [https://doi.org/10.1109/FOCS.2004.13 FOCS 2004]. Preprint ECCC [http://eccc.hpi-web.de/eccc-reports/2006/TR06-056/ TR06-056].
  
 
<span id="val03" style="color:maroon">[Val03]</span>
 
<span id="val03" style="color:maroon">[Val03]</span>
Line 3,240: Line 3,643:
 
Three problems in computer science,
 
Three problems in computer science,
 
<i>Journal of the ACM</i> 50(1):96-99, 2003.
 
<i>Journal of the ACM</i> 50(1):96-99, 2003.
 +
[https://doi.org/10.1145/602382.602410 doi:10.1145/602382.602410]
  
 
<span id="val76" style="color:maroon">[Val76]</span>
 
<span id="val76" style="color:maroon">[Val76]</span>
Line 3,245: Line 3,649:
 
Relative complexity of checking and evaluating,
 
Relative complexity of checking and evaluating,
 
<i>Information Processing Letters</i>, 5:20-23, 1976.
 
<i>Information Processing Letters</i>, 5:20-23, 1976.
 +
[https://doi.org/10.1016/0020-0190(76)90097-1 doi:10.1016/0020-0190(76)90097-1]
  
 
<span id="val79" style="color:maroon">[Val79]</span>
 
<span id="val79" style="color:maroon">[Val79]</span>
Line 3,250: Line 3,655:
 
The complexity of computing the permanent,
 
The complexity of computing the permanent,
 
<i>Theoretical Computer Science</i>, 8:189-201, 1979.
 
<i>Theoretical Computer Science</i>, 8:189-201, 1979.
 +
[https://doi.org/10.1016/0304-3975(79)90044-6 doi:10.1016/0304-3975(79)90044-6]
  
 
<span id="val79b" style="color:maroon">[Val79b]</span>
 
<span id="val79b" style="color:maroon">[Val79b]</span>
Line 3,255: Line 3,661:
 
Completeness classes in algebra,
 
Completeness classes in algebra,
 
<i>Proceedings of ACM STOC'79</i>, pp. 249-261, 1979.
 
<i>Proceedings of ACM STOC'79</i>, pp. 249-261, 1979.
 +
[https://doi.org/10.1145/800135.804419 doi:10.1145/800135.804419]
  
 
<span id="var82" style="color:maroon">[Var82]</span>
 
<span id="var82" style="color:maroon">[Var82]</span>
Line 3,260: Line 3,667:
 
Complexity of relational query languages,
 
Complexity of relational query languages,
 
<i>Proceedings of ACM STOC'82</i>, pp. 137-146, 1982.
 
<i>Proceedings of ACM STOC'82</i>, pp. 137-146, 1982.
 +
[https://doi.org/10.1145/800070.802186 doi:10.1145/800070.802186]
 +
[https://www.cs.rice.edu/~vardi/papers/stoc82.pdf Author's website version]
  
 
<span id="ven91" style="color:maroon">[Ven91]</span>
 
<span id="ven91" style="color:maroon">[Ven91]</span>
Line 3,265: Line 3,674:
 
Properties that characterize LOGCFL,
 
Properties that characterize LOGCFL,
 
<i>Journal of Computer and System Sciences</i> 43(2):380-404, 1991.
 
<i>Journal of Computer and System Sciences</i> 43(2):380-404, 1991.
 +
[https://doi.org/10.1016/0022-0000(91)90020-6 doi:10.1016/0022-0000(91)90020-6]
 +
Originally appeared in [https://doi.org/10.1145/28395.28411 STOC 1987]
  
 
<span id="ver92" style="color:maroon">[Ver92]</span>
 
<span id="ver92" style="color:maroon">[Ver92]</span>
Line 3,270: Line 3,681:
 
On the power of PP,
 
On the power of PP,
 
<i>Proceedings of IEEE Complexity'92</i>, pp. 138-143, 1992.
 
<i>Proceedings of IEEE Complexity'92</i>, pp. 138-143, 1992.
 +
[https://doi.org/10.1109/SCT.1992.215389 doi:10.1109/SCT.1992.215389]
  
 
<span id="ver95" style="color:maroon">[Ver95]</span>
 
<span id="ver95" style="color:maroon">[Ver95]</span>
Line 3,275: Line 3,687:
 
Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems,
 
Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems,
 
<i>Izvestiya Mathematics</i> 59(6):1103-1122, 1995.
 
<i>Izvestiya Mathematics</i> 59(6):1103-1122, 1995.
 +
[https://doi.org/10.1070/IM1995v059n06ABEH000050 doi:10.1070/IM1995v059n06ABEH000050]
  
 
<span id="vid03" style="color:maroon">[Vid03]</span>
 
<span id="vid03" style="color:maroon">[Vid03]</span>
Line 3,281: Line 3,694:
 
<i>Physical Review Letters</i> 91:147902, 2003.
 
<i>Physical Review Letters</i> 91:147902, 2003.
 
arXiv:[http://arxiv.org/abs/quant-ph/0301063 quant-ph/0301063].
 
arXiv:[http://arxiv.org/abs/quant-ph/0301063 quant-ph/0301063].
 +
[https://doi.org/10.1103/PhysRevLett.91.147902 doi:10.1103/PhysRevLett.91.147902]
 +
 +
<span id="vin91" style="color:maroon">[Vin91]</span>
 +
V. Vinay.
 +
Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits,
 +
<i>Proc. of the Sixth Annual Structure in Complexity Theory Conference</i>, pp. 270-284, 1991. [https://dx.doi.org/10.1109/SCT.1991.160269 doi:10.1109/SCT.1991.160269]
  
 
<span id="vin04" style="color:maroon">[Vin04]</span>
 
<span id="vin04" style="color:maroon">[Vin04]</span>
Line 3,286: Line 3,705:
 
Counting complexity of solvable group problems,
 
Counting complexity of solvable group problems,
 
<i>SIAM Journal on Computing</i> 33(4):852-869, 2004,
 
<i>SIAM Journal on Computing</i> 33(4):852-869, 2004,
−
[http://www.cse.unl.edu/~vinod/papers/SIAMFinal.ps http://www.cse.unl.edu/~vinod/papers/SIAMFinal.ps].
+
[https://doi.org/10.1137/S0097539703420651 doi:10.1137/S0097539703420651]
 +
[http://www.cse.unl.edu/~vinod/papers/SIAMFinal.ps Author's website version].
  
 
<span id="vin04b" style="color:maroon">[Vin04b]</span>
 
<span id="vin04b" style="color:maroon">[Vin04b]</span>
 
N. V. Vinodchandran.
 
N. V. Vinodchandran.
 
A note on the circuit complexity of PP,
 
A note on the circuit complexity of PP,
−
ECCC [http://eccc.uni-trier.de/eccc-reports/2004/TR04-056/ TR04-056], 2004.
+
<i>Theoretical Computer Science</i> 347(1-2):415-418, 2005.
 +
[https://doi.org/10.1016/j.tcs.2005.07.032 doi:10.1016/j.tcs.2005.07.032]
 +
Preprint ECCC [http://eccc.uni-trier.de/eccc-reports/2004/TR04-056/ TR04-056], 2004.
  
−
<span id="vsb83" style="color:maroon">[VSB+83]</span>
+
<span id="vol20" style="color:maroon">[Vol20]</span>
 +
I. Volkovich.
 +
The untold story of SBP,
 +
<i>Proceedings Proceedings of the 15th International Computer Science Symposium in Russia (CSR)</i>, pp. 393-405, 2020.
 +
[https://doi.org/10.1007/978-3-030-50026-9_29 doi:10.1007/978-3-030-50026-9_29]
 +
 
 +
<span id="vsb83" style="color:maroon">[VSBR83]</span>
 
L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff.
 
L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff.
 
Fast parallel computation of polynomials using few processors,
 
Fast parallel computation of polynomials using few processors,
 
<i>SIAM Journal on Computing</i> 12(4):641-644, 1983.
 
<i>SIAM Journal on Computing</i> 12(4):641-644, 1983.
 +
[https://doi.org/10.1137/0212043 doi:10.1137/0212043]
 +
Originally appeared in [https://doi.org/10.1007/3-540-10856-4_79 MFCS 1981]
  
 
<span id="vv85" style="color:maroon">[VV85]</span>
 
<span id="vv85" style="color:maroon">[VV85]</span>
 
U. V. Vazirani and V. V. Vazirani.
 
U. V. Vazirani and V. V. Vazirani.
−
Random polynomial time equals semi-random polynomial time,
+
Random polynomial time equals slightly-random polynomial time,
 
<i>Proceedings of IEEE FOCS'85</i>, pp. 417-428, 1985.
 
<i>Proceedings of IEEE FOCS'85</i>, pp. 417-428, 1985.
 +
[https://doi.org/10.1109/SFCS.1985.45 doi:10.1109/SFCS.1985.45]
  
 
<span id="vv86" style="color:maroon">[VV86]</span>
 
<span id="vv86" style="color:maroon">[VV86]</span>
Line 3,307: Line 3,738:
 
NP is as easy as detecting unique solutions,
 
NP is as easy as detecting unique solutions,
 
<i>Theoretical Computer Science</i> 47(3):85-93, 1986.
 
<i>Theoretical Computer Science</i> 47(3):85-93, 1986.
 +
[https://doi.org/10.1016/0304-3975(86)90135-0 doi:10.1016/0304-3975(86)90135-0]
 +
Originally appeared in [https://doi.org/10.1145/22145.22196 STOC 1985].
  
 
<span id="vya03" style="color:maroon">[Vya03]</span>
 
<span id="vya03" style="color:maroon">[Vya03]</span>
Line 3,318: Line 3,751:
 
K. W. Wagner.
 
K. W. Wagner.
 
The complexity of combinatorial problems with succinct input representation,
 
The complexity of combinatorial problems with succinct input representation,
−
<i>Acta Informatica</i> 23:325-356, 1986.
+
<i>Acta Informatica</i> 23:325-356, 1986.  
 +
[https://doi.org/10.1007/BF00289117 doi:10.1007/BF00289117]
  
−
<span id="wag88" style="color:maroon">[Wag88]</span>
+
<span id="wag88" style="color:maroon">[Wag90]</span>
 
K. W. Wagner.
 
K. W. Wagner.
−
Bounded query computation,
+
Bounded query classes,
−
<i>Proceedings of IEEE Complexity'88</i>, pp. 260-277, 1988.
+
<i>SIAM J. Comput.</i> 19(5): 833-846 (1990) [https://doi.org/10.1137/0219058 doi:10.1137/0219058]
 +
Originally appeared in [https://doi.org/10.1109/SCT.1988.5286 <i>Proceedings of IEEE Complexity'88</i>], pp. 260-277, 1988.
 +
 
 +
<span id="wan94" style="color:maroon">[Wan94]</span>
 +
E. Wanke.
 +
Bounded Tree-Width and LOGCFL.
 +
<i>J. Algorithms</i> 16(3):470-491. [https://doi.org/10.1006/jagm.1994.1022 doi:10.1006/jagm.1994.1022]
  
 
<span id="ww85" style="color:maroon">[WW85]</span>
 
<span id="ww85" style="color:maroon">[WW85]</span>
Line 3,329: Line 3,769:
 
On the Boolean closure of NP,
 
On the Boolean closure of NP,
 
<i>Proceedings of the International Conference on Fundamentals of Computation Theory</i>, LNCS volume 199, Springer-Verlag, pp. 485-493.
 
<i>Proceedings of the International Conference on Fundamentals of Computation Theory</i>, LNCS volume 199, Springer-Verlag, pp. 485-493.
 +
[https://doi.org/10.1007/BFb0028832 doi:10.1007/BFb0028832]
  
 
<span id="wat00" style="color:maroon">[Wat00]</span>
 
<span id="wat00" style="color:maroon">[Wat00]</span>
Line 3,335: Line 3,776:
 
<i>Proceedings of IEEE FOCS'2000</i>, pp. 537-546, 2000.
 
<i>Proceedings of IEEE FOCS'2000</i>, pp. 537-546, 2000.
 
arXiv:[http://arxiv.org/abs/cs.CC/0009002 cs.CC/0009002].
 
arXiv:[http://arxiv.org/abs/cs.CC/0009002 cs.CC/0009002].
 +
[https://doi.org/10.1109/SFCS.2000.892141 doi:10.1109/SFCS.2000.892141]
  
 
<span id="wat02" style="color:maroon">[Wat02]</span>
 
<span id="wat02" style="color:maroon">[Wat02]</span>
Line 3,341: Line 3,783:
 
to appear in <i>Proceedings of IEEE FOCS'2002</i>.
 
to appear in <i>Proceedings of IEEE FOCS'2002</i>.
 
arXiv:[http://arxiv.org/abs/quant-ph/0202111 quant-ph/0202111].
 
arXiv:[http://arxiv.org/abs/quant-ph/0202111 quant-ph/0202111].
 +
[https://doi.org/10.1109/SFCS.2002.1181970 doi:10.1109/SFCS.2002.1181970]
  
 
<span id="wat09" style="color:maroon">[Wat09]</span>
 
<span id="wat09" style="color:maroon">[Wat09]</span>
Line 3,346: Line 3,789:
 
Quantum Computational Complexity, <i>Encyclopedia of Complexity and Systems Science</i>, Springer, pp. 7174-7201, 2009.
 
Quantum Computational Complexity, <i>Encyclopedia of Complexity and Systems Science</i>, Springer, pp. 7174-7201, 2009.
 
arXiv:[http://arxiv.org/abs/0804.3401 quant-ph/0804.3401].
 
arXiv:[http://arxiv.org/abs/0804.3401 quant-ph/0804.3401].
 +
[https://doi.org/10.1007/978-0-387-30440-3_428 doi:10.1007/978-0-387-30440-3_428]
  
 
<span id="wat87" style="color:maroon">[Wat87]</span>
 
<span id="wat87" style="color:maroon">[Wat87]</span>
Line 3,351: Line 3,795:
 
Comparison of polynomial time completeness notions,
 
Comparison of polynomial time completeness notions,
 
<i>Theoretical Computer Science</i> 53:249-265, 1987.
 
<i>Theoretical Computer Science</i> 53:249-265, 1987.
 +
[https://doi.org/10.1016/0304-3975(87)90132-0 doi:10.1016/0304-3975(87)90132-0]
  
 
<span id="wat99" style="color:maroon">[Wat99]</span>
 
<span id="wat99" style="color:maroon">[Wat99]</span>
 
J. Watrous.
 
J. Watrous.
 
PSPACE has constant-round quantum interactive proof systems,
 
PSPACE has constant-round quantum interactive proof systems,
−
<i>Proceedings of IEEE FOCS'99</i>, pp. 112-119, 1999.
+
<i>Theoret. Comput. Sci</i> 292(30:575-588, 2003.
 +
Originally appeared in [https://doi.org/10.1109/SFFCS.1999.814583 <i>Proceedings of IEEE FOCS'99</i>], pp. 112-119, 1999.
 
arXiv:[http://arxiv.org/abs/cs.CC/9901015 cs.CC/9901015].
 
arXiv:[http://arxiv.org/abs/cs.CC/9901015 cs.CC/9901015].
 +
[https://doi.org/10.1016/S0304-3975(01)00375-9 doi:10.1016/S0304-3975(01)00375-9]
  
 
<span id="wat99b" style="color:maroon">[Wat99b]</span>
 
<span id="wat99b" style="color:maroon">[Wat99b]</span>
Line 3,362: Line 3,809:
 
Space-bounded quantum complexity,
 
Space-bounded quantum complexity,
 
<i>Journal of Computer and System Sciences</i> 59(2):281-326, 1999.
 
<i>Journal of Computer and System Sciences</i> 59(2):281-326, 1999.
−
[https://cs.uwaterloo.ca/~watrous/Papers/SpaceBoundedQuantumComplexity.pdf https://cs.uwaterloo.ca/~watrous/Papers/SpaceBoundedQuantumComplexity.pdf].
+
[https://doi.org/10.1006/jcss.1999.1655 doi:10.1006/jcss.1999.1655]
 +
[https://cs.uwaterloo.ca/~watrous/Papers/SpaceBoundedQuantumComplexity.pdf Author's website version].
  
 
<span id="wat15" style="color:maroon">[Wat15]</span>
 
<span id="wat15" style="color:maroon">[Wat15]</span>
Line 3,368: Line 3,816:
 
The complexity of deciding statistical properties of samplable distributions,
 
The complexity of deciding statistical properties of samplable distributions,
 
<i>Theory of Computing</i>, 11:1-34, 2015.
 
<i>Theory of Computing</i>, 11:1-34, 2015.
 +
[http://dx.doi.org/10.4086/toc.2015.v011a001 doi:10.4086/toc.2015.v011a001]
  
 
<span id="weg87" style="color:maroon">[Weg87]</span>
 
<span id="weg87" style="color:maroon">[Weg87]</span>
 
I. Wegener.
 
I. Wegener.
 
The Complexity of Boolean Functions, New York: Wiley 1987.
 
The Complexity of Boolean Functions, New York: Wiley 1987.
 +
[https://eccc.weizmann.ac.il/static/books/The_Complexity_of_Boolean_Functions/ Full book on ECCC]
  
 
<span id="weg88" style="color:maroon">[Weg88]</span>
 
<span id="weg88" style="color:maroon">[Weg88]</span>
Line 3,377: Line 3,827:
 
On the Complexity of Branching Programs and Decision Trees for Clique Functions,
 
On the Complexity of Branching Programs and Decision Trees for Clique Functions,
 
<i>Journal of the ACM</i> 35(2):461-471, 1988.
 
<i>Journal of the ACM</i> 35(2):461-471, 1988.
−
DOI:[http://doi.acm.org/10.1145/42282.46161 10.1145/42282.46161].
+
[http://doi.acm.org/10.1145/42282.46161 doi:10.1145/42282.46161].
  
 
<span id="weh06" style="color:maroon">[Weh06]</span>
 
<span id="weh06" style="color:maroon">[Weh06]</span>
Line 3,384: Line 3,834:
 
the 23rd Annual Symposium on Theoretical Aspects of Computer Science</i>, volume 3884 of <i>Lecture
 
the 23rd Annual Symposium on Theoretical Aspects of Computer Science</i>, volume 3884 of <i>Lecture
 
Notes in Computer Science</i>, pages 162–171. Springer, 2006
 
Notes in Computer Science</i>, pages 162–171. Springer, 2006
 +
[https://doi.org/10.1007/11672142_12 doi:10.1007/11672142_12]
  
 
<span id="wig06" style="color:maroon">[Wig06]</span>
 
<span id="wig06" style="color:maroon">[Wig06]</span>
Line 3,394: Line 3,845:
 
Relativized circuit complexity,
 
Relativized circuit complexity,
 
<i>Journal of Computer and System Sciences</i> 31:169-181, 1985.
 
<i>Journal of Computer and System Sciences</i> 31:169-181, 1985.
 +
[https://doi.org/10.1016/0022-0000(85)90040-6 doi:10.1016/0022-0000(85)90040-6]
  
−
<span id="wil11" style="color:maroon">[Wil11]</span>
+
<span id="wil11" style="color:maroon">[Wil14]</span>
 
R. Williams. Non-uniform ACC circuit lower bounds,
 
R. Williams. Non-uniform ACC circuit lower bounds,
−
<i>Proceedings of IEEE Conference on Computational Complexity</i> 2011.
+
<i>J. ACM</i> 61(1):2:1-2:32, 2014.
−
[http://people.csail.mit.edu/rrw/acc-lbs.pdf http://people.csail.mit.edu/rrw/acc-lbs.pdf].
+
[https://doi.org/10.1145/2559903 doi:10.1145/2559903]
 +
Originally appeared in [https://doi.org/10.1109/CCC.2011.36 <i>Proceedings of IEEE Conference on Computational Complexity</i> 2011].
 +
[https://people.csail.mit.edu/rrw/acc-lbs-journal-final.pdf Author's website version].
  
 
<span id="wol94" style="color: maroon;">[Wol94]</span>
 
<span id="wol94" style="color: maroon;">[Wol94]</span>
Line 3,404: Line 3,858:
 
Nondeterministic circuits, space complexity and quasigroups,
 
Nondeterministic circuits, space complexity and quasigroups,
 
<i>Theoretical Computer Science</i> 125:295–313, 1994.
 
<i>Theoretical Computer Science</i> 125:295–313, 1994.
 +
[https://doi.org/10.1016/0304-3975(92)00014-I doi:10.1016/0304-3975(92)00014-I]
  
−
<span id="wu18" style="color:maroon">[Wu18]</span>
+
<span id="wu18" style="color:maroon">[Wu22]</span>
 
X. Wu.
 
X. Wu.
 
A stochastic calculus approach to the oracle separation of BQP and PH,
 
A stochastic calculus approach to the oracle separation of BQP and PH,
−
ECCC [https://eccc.weizmann.ac.il/report/2018/202/ TR18-202], 2018.
+
<i>Theory of Computing</i> 18(17):1-11, 2022.
 +
[http://dx.doi.org/10.4086/toc.2022.v018a017 doi:10.4086/toc.2022.v018a017]
 +
 
 +
<span id="wkst19" style="color:maroon">[WKST19]</span>
 +
A. B. Watts, R. Kothari, L. Schaeffer, and A. Tal.
 +
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.
 +
STOC [https://dl.acm.org/doi/10.1145/3313276.3316404 doi:10.1145/3313276.3316404], 2010.
  
 
===== Y =====
 
===== Y =====
−
 
+
<span id="Yap83" style="color:maroon">[Yap83]</span>
−
{{Reference
+
C. Yap.
−
    |tag=Yap83
+
Some consequences of non-uniform conditions on uniform classes,
−
    |authors=C. Yap
+
<i>Theoretical Computer Science</i>, 26, pp. 287-300, 1983.
−
    |title=Some consequences of non-uniform conditions on uniform classes
+
[https://doi.org/10.1016/0304-3975(83)90020-8 doi:10.1016/0304-3975(83)90020-8]
−
    |journal=Theoretical Computer Science
 
−
    |srcdetail=(1983), 26, 287-300
 
−
}}
 
  
 
<span id="yam99" style="color:maroon">[Yam99]</span>
 
<span id="yam99" style="color:maroon">[Yam99]</span>
Line 3,424: Line 3,882:
 
Polynomial time samplable distributions,
 
Polynomial time samplable distributions,
 
J. Complexity 15 (1999), no. 4, 557-574.
 
J. Complexity 15 (1999), no. 4, 557-574.
 +
[https://doi.org/10.1006/jcom.1999.0523 doi:10.1006/jcom.1999.0523]
 
ECCC [http://eccc.hpi-web.de/eccc-reports/1995/TR95-039/ TR95-039].
 
ECCC [http://eccc.hpi-web.de/eccc-reports/1995/TR95-039/ TR95-039].
  
Line 3,435: Line 3,894:
 
Expressing combinatorial optimization problems by linear programs,
 
Expressing combinatorial optimization problems by linear programs,
 
<i>Journal of Computer and System Sciences</i>, 43(3):441-466, 1991.
 
<i>Journal of Computer and System Sciences</i>, 43(3):441-466, 1991.
 +
[https://doi.org/10.1016/0022-0000(91)90024-Y doi:10.1016/0022-0000(91)90024-Y]
 +
Originally appeared in [https://doi.org/10.1145/62212.62232 STOC 1988]
  
 
<span id="yao85" style="color:maroon">[Yao85]</span>
 
<span id="yao85" style="color:maroon">[Yao85]</span>
Line 3,440: Line 3,901:
 
Separating the polynomial hierarchy by oracles,
 
Separating the polynomial hierarchy by oracles,
 
<i>Proceedings of IEEE FOCS'85</i>, pp. 1-10, 1985.
 
<i>Proceedings of IEEE FOCS'85</i>, pp. 1-10, 1985.
 +
[https://doi.org/10.1109/SFCS.1985.49 doi:10.1109/SFCS.1985.49]
  
 
<span id="yao89" style="color:maroon">[Yao89]</span>
 
<span id="yao89" style="color:maroon">[Yao89]</span>
Line 3,445: Line 3,907:
 
Circuits and local computation,
 
Circuits and local computation,
 
<i>Proceedings of ACM STOC'89</i>, pp. 186-196, 1989.
 
<i>Proceedings of ACM STOC'89</i>, pp. 186-196, 1989.
 +
[https://doi.org/10.1145/73007.73025 doi:10.1145/73007.73025]
  
 
<span id="yao90" style="color:maroon">[Yao90]</span>
 
<span id="yao90" style="color:maroon">[Yao90]</span>
Line 3,450: Line 3,913:
 
On ACC and threshold circuits,
 
On ACC and threshold circuits,
 
<i>Proceedings of IEEE FOCS'90</i>, pp. 619-627, 1990.
 
<i>Proceedings of IEEE FOCS'90</i>, pp. 619-627, 1990.
 +
[https://doi.org/10.1109/FSCS.1990.89583 doi:10.1109/FSCS.1990.89583]
  
 
<span id="yao90b" style="color:maroon">[Yao90b]</span>
 
<span id="yao90b" style="color:maroon">[Yao90b]</span>
Line 3,455: Line 3,919:
 
Coherent functions and program checkers,
 
Coherent functions and program checkers,
 
<i>Proceedings of ACM STOC'90</i>, 1990.
 
<i>Proceedings of ACM STOC'90</i>, 1990.
 +
[https://doi.org/10.1145/100216.100226 doi:10.1145/100216.100226]
  
 
<span id="yao93" style="color:maroon">[Yao93]</span>
 
<span id="yao93" style="color:maroon">[Yao93]</span>
Line 3,460: Line 3,925:
 
Quantum circuit complexity,
 
Quantum circuit complexity,
 
<i>Proceedings of IEEE FOCS'93</i>, pp. 352-361, 1993.
 
<i>Proceedings of IEEE FOCS'93</i>, pp. 352-361, 1993.
 +
[https://doi.org/10.1109/SFCS.1993.366852 doi:10.1109/SFCS.1993.366852]
  
 
<span id="yes83" style="color:maroon">[Yes83]</span>
 
<span id="yes83" style="color:maroon">[Yes83]</span>
Line 3,466: Line 3,932:
 
<i>SIAM Journal on Computing</i>, 12(3):411-425, 1983.
 
<i>SIAM Journal on Computing</i>, 12(3):411-425, 1983.
 
DOI:[http://dx.doi.org/10.1137/0212027 10.1137/0212027]
 
DOI:[http://dx.doi.org/10.1137/0212027 10.1137/0212027]
 +
 +
<span id="yir24" style="color:maroon">[Yir24]</span>
 +
J. Yirka.
 +
Even quantum advice is unlikely to solve PP,
 +
arXiv:[https://arxiv.org/abs/2403.09994 2403.09994] [cs.CC],
 +
2024.
  
 
===== Z =====
 
===== Z =====
Line 3,472: Line 3,944:
 
S. Zachos.
 
S. Zachos.
 
Probabilistic quantifiers and games,
 
Probabilistic quantifiers and games,
−
<i>Journal of Computer and System Sciences</i> 36(3):433-451, 1988.
+
<i>Journal of Computer and System Sciences</i> 36(3):433-451, 1988.  
 +
[https://doi.org/10.1016/0022-0000(88)90037-2 doi:10.1016/0022-0000(88)90037-2]
  
 
<span id="zh86" style="color:maroon">[ZH86]</span>
 
<span id="zh86" style="color:maroon">[ZH86]</span>
 
S. Zachos and H. Heller.
 
S. Zachos and H. Heller.
 
A decisive characterization of BPP.
 
A decisive characterization of BPP.
−
''Information and Control'', 69(1&ndash;3):125&ndash;135, 1986.
+
''Information and Control'', 69(1&ndash;3):125&ndash;135, 1986.  
 +
[https://doi.org/10.1016/S0019-9958(86)80044-4 doi:10.1016/S0019-9958(86)80044-4]
  
 
<span id="zkt85" style="color:maroon">[ZKT85]</span>
 
<span id="zkt85" style="color:maroon">[ZKT85]</span>
Line 3,489: Line 3,963:
 
Simulating BPP using a general weak random source,
 
Simulating BPP using a general weak random source,
 
<i>Algorithmica</i> 16 (1996), no. 4-5, 367--391
 
<i>Algorithmica</i> 16 (1996), no. 4-5, 367--391
−
[http://www.cs.utexas.edu/users/diz/pubs/bpp.ps http://www.cs.utexas.edu/users/diz/pubs/bpp.ps].
+
[https://www.cs.utexas.edu/~diz/Sub%20Websites/Research/Simulating_bpp_using_a_general_weak_random_sources.pdf Author's webpage 1995 version].
−
 
+
[https://doi.org/10.1007/BF01940870 doi:10.1007/BF01940870]
 +
Originally appeared in [https://doi.org/10.1109/SFCS.1991.185351 FOCS 1991]
 
[[Category:Computational Complexity]]
 
[[Category:Computational Complexity]]

Latest revision as of 01:01, 11 November 2024


Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z


A

[Aar02] S. Aaronson. Quantum lower bound for the collision problem, Proceedings of ACM STOC'2002, pp. 635-642, 2002. arXiv:quant-ph/0111102.

[Aar03] S. Aaronson. Lower bounds for local search by quantum arguments, Proceedings of ACM STOC 2004. arXiv:quant-ph/0307149, ECCC TR03-057.

[Aar03b] S. Aaronson. Multilinear formulas and skepticism of quantum computing, Proceedings of ACM STOC 2004. arXiv:quant-ph/0311039, ECCC TR03-079.

[Aar04b] S. Aaronson. Limitations of quantum advice and one-way communication, Proceedings of IEEE Complexity 2004, pp. 320-332, 2004. arXiv:quant-ph/0402095, ECCC TR04-026.

[Aar05] S. Aaronson. Quantum computing and hidden variables, Physical Review A 71:032325, March 2005. arXiv:quant-ph/0408035.

[Aar05b] S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time, Proceedings of the Royal Society A, 461(2063):3473-3482, 2005. arXiv:quant-ph/0412187.

[Aar05c] S. Aaronson. NP-complete problems and physical reality. ACM SIGACT News, March 2005 quant-ph/0502072.

[Aar06] S. Aaronson. Oracles are subtle but not malicious, Proceedings of IEEE Complexity 2006, 2006. arXiv:cs.CC/0504048, ECCC TR05-040.

[Aar06b] S. Aaronson. QMA/qpoly is contained in PSPACE/poly: de-Merlinizing quantum protocols, Proceedings of IEEE Complexity 2006, 2006. arXiv:quant-ph/0510230.

[Aar10] S. Aaronson. BQP and the Polynomial Hierarchy, Proceedings of ACM STOC 2010. arXiv:0910.4698, ECCC TR09-104.

[Aar18] S. Aaronson. PDQP/qpoly = ALL, arXiv:1805.08577.

[ABOE08] D. Aharonov, M. Ben-Or, E. Eban. Interactive Proofs for Quantum Computations, arXiv:0810.5375.

[AK06] S. Aaronson and G. Kuperberg. Quantum versus classical proofs and advice, submitted, 2006. arXiv:quant-ph/0604056.

[ABFL2014] S. Aaronson, A. Bouland, J. Fitzsimons, M. Lee The space "just above" BQP arXiv:arxiv.org/abs/1412.6507

[AB00] E. Allender and D. A. M. Barrington. Uniform Circuits for Division: Consequences and Problems. J. Comput. System Sci. 65 (2002), no. 4, 695--716. ECCC TR00-65, 2000.

[ABD+08] S. Aaronson, S. Beigi, A. Drucker, B. Fefferman and P. Shor. The power of unentanglement Theory of Computing, 5(1):1-42, 2009 arXiv:0804.0802

[ABF+94] J. Aspnes, R. Beigel, M. L. Furst, and S. Rudich. The expressive power of voting polynomials, Combinatorica 14(2):135-148, 1994. http://www.cs.yale.edu/~aspnes/stoc91voting.ps

[ABK+02] E. Allender, H. Buhrman, M. Koucký, D. van Melkebeek, and D. Ronneburger. Power from random strings, Proceedings of IEEE FOCS'2002, pp. 669-678, 2002. ECCC TR02-028.

[ABL98] A. Ambainis, D. M. Barrington, and H. LêThanh. On counting AC0 circuits with negative constants, Proceedings of MFCS (Mathematical Foundations of Computer Science), pp. 419-427, 1998. ECCC TR98-020.

[ABO99] E. Allender, R. Beals, and M. Ogihara. The complexity of matrix rank and feasible systems of linear equations, Computational Complexity 8(2):99-126, 1999. ECCC TR96-024, DIMACS TR 97-40.

[ABV95] W. Aiello, M. Bellare, and R. Venkatesan. Knowledge on the average - perfect, statistical, and logarithmic, Proceedings of ACM STOC'95, 1995.

[ACG+99] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial optimization problems and their approximability properties, Springer-Verlag, 1999. See also "A compendium of NP optimization problems" (P. Crescenzi and V. Kann, eds.), http://www.nada.kth.se/~viggo/wwwcompendium/.

[ACJ+21] M. Arenas, L. A. Croquevielle, R. Jayaram, and C. Riveros. #NFA admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes. Journal of the ACM 68(6):48:1-48:40, 2021.

[ADH97] L. Adleman, J. DeMarrais, and M. Huang. Quantum computability, SIAM Journal on Computing 26:1524-1540, 1997.

[Adl78] L. Adleman. Two theorems on random polynomial time. FOCS 78.

[AD14] S. Aaronson and A. Drucker. A Full Characterization of Quantum Advice, SIAM Journal on Computing 43(3):1131–1183, 2014. arXiv:1004.0377.

[AFM01] L. Antuñes, L. Fortnow, and D. van Melkebeek. Computational depth, Proceedings of IEEE Complexity'01, pp. 266-273, 2001. https://people.cs.uchicago.edu/~fortnow/papers/depth-j.pdf

[AG00] C. Alvarez and R. Greenlaw. A compendium of problems complete for symmetric logarithmic space, Journal of Computational Complexity 9:73-95, 2000. ECCC TR96-039.

[AG04] S. Aaronson and D. Gottesman. Improved Simulation of Stabilizer Circuits, Phys. Rev. A 70, 052328, 2004. arXiv:quant-ph/0406196.

[AGH90] W. Aiello, S. Goldwasser, and J. Håstad. On The Power Of Interaction. Combinatorica 10 (1990), no. 1, 3--25.

[AGK07] D. Aharonov, D. Gottesman, S. Irani, and J. Kempe;stad. The power of quantum systems on a line. Comm. Math. Physics, vol. 287, no. 1, pp. 41-65 (2009) arXiv:0705.4077

[Agr01] M. Agrawal. For completeness, sublogarithmic space is no space, Information Processing Letters (82), 2001-2002, iss. 6, 321-325. http://www.cse.iitk.ac.in/~manindra/isomorphism/sublog-completeness.pdf

[AJT83] M. Ajtai. Σ-1-1-Formulae on finite structures, Annals of Pure and Applied Logic (24), 1983, 1-48.

[AH87] L. Adleman and M. Huang. Recognizing primes in random polynomial time, Proceedings of ACM STOC'87, pp. 462-470, 1987.

[AH87b] W. Aiello and J. Håstad. Perfect zero-knowledge languages can be recognized in two rounds, Proceedings of IEEE FOCS 1987, pp. 439-448, 1987.

[AIK04] B. Applebaum, Y. Ishai, and E. Kushilevitz. Cryptography in NC0, SIAM Journal of Computing, 36(4):845-888, 2006, http://www.eng.tau.ac.il/%7Ebennyap/pubs/nc0-full.pdf.

[AJ93] C. Alvarez and B. Jenner. A very hard log-space counting class, Theoretical Computer Science 107:3-30, 1993.

[AK02] V. Arvind and P. Kurur. Graph isomorphism is in SPP, Information and Computation, 204(5):835-852, 2006 ECCC TR02-037

[AK06] S. Aaronson and G. Kuperberg. Quantum Versus Classical Proofs and Advice. Theory of Computing 3(7):129-157, 2007 https://theoryofcomputing.org/articles/v003a007/ arXiv:quant-ph/0604056

[AK96] F. Ablayev and M. Karpinski. On the power of randomized branching programs, Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), Springer-Verlag 1099, pp. 348-356, 1996. ECCC TR95-054, DIMACS TR 96-46.

[AKL+79] R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff. Random walks, traversal sequences, and the complexity of maze problems, Proceedings of IEEE FOCS'79, pp. 218-223, 1979.

[AKR+03] E. Allender, M. Koucký, D. Ronneburger, et al. Derandomization and distinguishing complexity, Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 209-220.

[AKS94] V. Arvind, J. Köbler and R. Schuler. On helping and interactive proof systems, Algorithms and Computation: 5th International Symposium, 137-145.

[AKS02] M. Agrawal, N. Kayal, and N. Saxena. Primes is in P, Annals of Mathematics, 160 (2004), 781-793. http://www.cse.iitk.ac.in/primality.pdf.

[AKS+95] V. Arvind, J. Köbler, U. Schöning, and R. Schuler. If NP has polynomial-size circuits, then MA=AM, Theoretical Computer Science 137, 1995. http://www.informatik.hu-berlin.de/Institut/struktur/algorithmenII/Papers/ma-am.ps.gz

[All96] E. Allender. Circuit complexity before the dawn of the new millennium, Proceedings of the 16th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), Lecture Notes in Computer Science 1180, pp. 1-18, 1996. DIMACS TR 97-49.

[All99] E. Allender. The permanent requires large uniform threshold circuits, Chicago Journal of Theoretical Computer Science 7, 1999. DIMACS TR 97-51.

[ALM+98] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems, Journal of the ACM 45(3):501-555, 1998. ECCC TR98-008.

[AM04] R. Alur and P. Madhusudan. Visibly Pushdown Languages, Proceedings of ACM STOC'04, 2004., 202-211.

[AM09] R. Alur and P. Madhusudan. Adding Nesting Structure to Words., Journal of the ACM 56(3), Article 16, May 2009.

[Amb14] A. Ambainis. On physical problems that are slightly more difficult than QMA, Proceedings of the 2014 IEEE 29th Conference on Computational Complexity, 2014. arXiv:quant-ph/1312.4758.

[AMP02] F. Ablayev, C. Moore, and C. Pollett. Quantum and stochastic branching programs of bounded width, Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 2002. arXiv:quant-ph/0201139, ECCC TR02-013.

[AMS06] N. Alon, D. Moshkovitz, and S. Safra. Algorithmic construction of sets for k-restrictions, ACM Transactions on Algorithms (TALG) 2(2): 153–177, 2006. doi:10.1145/1150334.1150336

[Ani+23] Joshua Ani et al. Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines. 2023. arxiv: [1]

[AN02] D. Aharonov and T. Naveh. Quantum NP - a survey, arXiv:quant-ph/0210077.

[AP95] G. Ausiello and M. Protasi Local search, reducibility, and approximability of NP optimization problems, Information Processing Letters 54:73-79, 1995.

[AR01] M. Alekhnovich and A. A. Razborov. Resolution is not automatizable unless W[P] is tractable, Proceedings of IEEE FOCS'01, pp. 210-219, 2001.

[AR03] D. Aharonov and O. Regev. A lattice problem in quantum NP, arXiv:quant-ph/0307220.

[AR88] E. Allender and R. Rubinstein. P-printable sets, SIAM Journal on Computing 17(6):1193-1202, 1988.

[AR16] B. Applebaum and P. Raykov. From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back, Proceedings of TCC(A2), pp. 65-82, 2016.

[Aro96] S. Arora. Polynomial time approximation scheme for Euclidean TSP and other geometric problems, Journal of the ACM 45(5) 753-782, 1998. https://www.cs.princeton.edu/~arora/pubs/tsp.ps

[ARZ99] E. Allender, K. Reinhardt, and S. Zhou. Isolation, matching, and counting: uniform and nonuniform upper bounds, Journal of Computer and System Sciences 59:164-181, 1999. http://www.cs.rutgers.edu/pub/allender/matching.pdf.

[AS94] E. Allender and M. Strauss. Measure on small complexity classes with applications for BPP, Proceedings of IEEE FOCS'94, pp. 807-818, 1994. ECCC TR94-004, DIMACS TR 94-18.

[AS98] S. Arora and M. Safra. Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM 45(1):70-122, 1998. http://www.cs.princeton.edu/~arora/pubs/as.ps.

[ASV00] A. Ambainis, L. Schulman, and U. Vazirani. Quantum computing with highly mixed states, Proceedings of ACM STOC'2000, pp. 705-714, 2000. arXiv:quant-ph/0003136.

[ATW+00] R. Armoni, A. Ta-Shma, A. Wigderson, and S. Zhou. An O(log(n)4/3) algorithm for (s,t) connectivity in undirected graphs, Journal of the ACM 47(2):294-311, 2000. http://whiteboard.cs.tau.ac.il/~amnon/Papers/ATWZ.jacm00.pdf

[AV04] V. Arvind and T. C. Vijayaraghavan. Abelian permutation group problems and logspace counting classes, Proceedings of the 19th IEEE Conference on Computational Complexity, .

[AW09] S. Aaronson and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent, Proceedings of the Royal Society A 465:631-647, 2009. arXiv:0808.2669.

[AW90] E. Allender and K. W. Wagner. Counting hierarchies: polynomial time and constant depth circuits, Bulletin of the EATCS 40, February 1990. http://people.cs.uchicago.edu/~fortnow/beatcs/column40.ps.

B

[Bab85] L. Babai. Trading Group Theory for Randomness. In 17th STOC, pages 421--429, 1985.

[Bab87] L. Babai. Random oracles separate PSPACE from the polynomial-time hierarchy. Information Processing Letters, 26 (1987) 51-53.

[Bar02] B. Barak. A probabilistic-time hierarchy theorem for "slightly non-uniform" algorithms, Proceedings of RANDOM'2002, 2002. http://www.math.weizmann.ac.il/~/boaz/Papers/bptime.ps

[Bar89] D. A. M. Barrington. Bounded-width polynomial-size branching programs can recognize exactly those languages in NC1, Journal of Computer and System Sciences 38:150-164, 1989.

[Baz95] C. Bazgan. Approximation de problèmes d'optimisation et de fonctions totales de NP, PhD thesis, INRIA, Orsay, France, 1998. http://l1.lamsade.dauphine.fr/~bazgan/Papers/these.ps

[BB12] M. Bläser and B. Manthey. Smoothed Complexity Theory, Proceedings of the 37th Int. Symp. on Mathematical Foundations of Computer Science, 2012. ArXiv: 1202.1936.

[BB92] A. Berthiaume and G. Brassard. The quantum challenge to structural complexity theory. Proceedings of Structure in Complexity Theory, 1992, 132--137. DOI

[BBB+97] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing, SIAM Journal on Computing, 26(5):1510-1523, 1997. arXiv:quant-ph/9701001.

[BBF98] R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions, Proceedings of ACM STOC'98, pp. 203-208, 1998. http://people.cs.uchicago.edu/~fortnow/papers/newiso.ps.

[BBR94] D. A. M. Barrington, R. Beigel, and S. Rudich. Representing Boolean functions as polynomials modulo composite integers, Computational Complexity, 4:367-382, 1994. http://www.cis.temple.edu/~beigel/papers/bbr-mods-cc.html.

[BBS86] J. Balcázar, R. Book, and U. Schöning. Sparse sets, lowness, and highness, SIAM Journal on Computing 15:739-747, 1986.

[BCE+95] P. Beame, S. Cook, J. Edmonds, R. Impagliazzo, and T. Pitassi. The relative complexity of NP search problems, Proceedings of ACM STOC'95, pp. 303-314, 1995. http://www.cs.washington.edu/homes/beame/search.ps

[BCH86] P. Beame, S. Cook, and J. Hoover. Log depth circuits for division and related problems, SIAM Journal on Computing 15:994-1003, 1986 http://www.cs.washington.edu/homes/beame/papers/division.ps.

[BCG+92] S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity, Journal of Computer and System Sciences 44(2):193-219, 1992. http://www.cs.technion.ac.il/~shai/aver.pdf

[BCK+14] H. Buhrman, R. Cleve, M. Koucky, B. Loff, and F. Speelman. Computing with a full memory: catalytic space, Symposium on the Theory of Computing (STOC) 857-866, 2014.

[BCS+97] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation, Springer-Verlag, 1997.

[BCD+89] A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. L. Tompa. Two applications of inductive counting for complementation problems, SIAM Journal on Computing 18:559-578, 1989.

[BCP83] A. Borodin, S. A. Cook, and N. Pippenger. Parallel computations for well-endowed rings and space-bounded probabilistic machines, Information and Control 58:113-136, 1983.

[BCHTV17] A. Bouland, L. Chen, D. Holden, J. Thaler, and P. N. Vasudevan. On the Power of Statistical Zero Knowledge, Foundations of Computer Science, pp. 708-719, 2017. arXiv:[2].

[BCY11] F.G.S.L. Brandão, M. Christandl, and J. Yard. A quasipolynomial-time algorithm for the quantum separability problem. Proceedings of ACM STOC'11, pp. 343-352, 2011. arXiv:1011.2751.

[BD99] H. Buhrman and W. van Dam. Bounded quantum query complexity, Proceedings of IEEE Complexity'99, pp. 149-156, 1999. arXiv:quant-ph/9903035.

[BDG88] J. L. Balcázar, J. Díaz, and J. Gabarró Structural complexity 1

[BDH+92] G. Buntrock, C. Damm, U. Hertrampf, and Ch. Meinel. Structure and importance of logspace-MOD-classes, Mathematical Systems Theory 25:223-237, 1992. http://www.num.math.uni-goettingen.de/damm/papers/BDHM92.ps.gz.

[Bei89] R. Beigel. On the relativized power of additional accepting paths, Proceedings of IEEE Complexity'89, pp. 216-224, 1989. http://www.cis.temple.edu/~beigel/papers/ukp-structures.PS.gz.

[Bei94] R. Beigel. Perceptrons, PP, and the polynomial hierarchy, Computational Complexity 4:339-349, 1994. http://www.cis.temple.edu/~beigel/papers/delta2p-cc.PS.gz.

[Ber80] L. Berman. The complexity of logical theories, Theoretical Computer Science 11:71-78, 1980.

[BF92] R. Beigel and J. Feigenbaum. On Being Incoherent Without Being Very Hard. Comput. Complexity 2 (1992), no. 1, 1--17 http://www.cis.temple.edu/~beigel/papers/bf-coherent-cc.html

[BF99] H. Buhrman and L. Fortnow. One-sided versus two-sided randomness, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 100-109, 1999. http://people.cs.uchicago.edu/~fortnow/papers/rpvsbpp.ps.

[BF03] R. Beigel. Are Cook and Karp ever the same?, Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 333-336.

[BFL91] L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols, Computational Complexity 1:3-40, 1991. http://people.cs.uchicago.edu/~fortnow/papers/mip2.ps.

[BFM88] M. Blum, P. Feldman, and S. Micali. Non-interactive zero-knowledge proofs and their applications, Proceedings of the 20th STOC, ACM, 1988.

[BFS86] L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory, Proceedings of IEEE FOCS'86, pp. 337-347, 1986.

[BFT98] H. Buhrman, L. Fortnow, and T. Thierauf. Nonrelativizing separations, Proceedings of IEEE Complexity'98, pp. 8-12, 1998. http://people.cs.uchicago.edu/~fortnow/papers/nonrel.ps.

[BGS75] T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question, SIAM Journal on Computing 4:431-442, 1975.

[BH77] L. Berman and J. Hartmanis. On isomorphism and density of NP and other complete sets, SIAM Journal on Computing 6:305-322, 1977.

[BG03] M. Ben-Or and D. Gutfreund. Trading help for interaction in statistical zero-knowledge proofs, J. Cryptology 16 (2003), no. 2, 95--116. http://www.cs.huji.ac.il/~danig/pubs/help_interaction.ps

[BG69] R. Book and S. Greibach. Quasi-realtime languages, Proceedings of ACM STOC pp. 15-18, 1969. http://portal.acm.org/citation.cfm?id=800169.805416

[BG81] C. H. Bennett and J. Gill. Relative to a random oracle A, PA != NPA != coNPA with probability 1, SIAM Journal on Computing, 10(1):96-113, 1981. DOI:10.1137/0210008

[BG92] R. Beigel and J. Gill. Counting classes: thresholds, parity, mods, and fewness, Theoretical Computer Science 103(1):3-23, 1992. http://www.cis.temple.edu/~beigel/papers/bg-mods-tcs.PS.gz.

[BG98] R. Beigel and J. Goldsmith. Downward separation fails catastrophically for limited nondeterminism classes, SIAM Journal on Computing 17(5):1420-1429, 1998. http://www.cis.temple.edu/~beigel/papers/bg-beta-draft.PS.gz.

[BG94] M. Bellare and S. Goldwasser. The complexity of decision versus search, SIAM Journal on Computing 23(1):91-119, 1994. http://www.cs.ucsd.edu/users/mihir/papers/compip.pdf

[BGG+90] M. Ben-Or, O. Goldreich, S. Goldwasser, J. Håstad, J. Kilian, S. Micali, and P. Rogaway. Everything provable is provable in zero-knowledge, Advances in Cryptology: CRYPTO'88 (S. Goldwasser, ed.), Lecture Notes in Computer Science 403, Springer-Verlag, pp. 37-56, 1990.

[BGK+88] M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: how to remove intractability, Proceedings of ACM STOC'88, pp. 113-131, 1988.

[BG82] A. Blass and Y. Gurevich. On the unique satisfiability problem, Information and Control 55(1-3):80-88, 1982.

[BGM02] E. Böhler, C. Glaßer, and D. Meister. Error-bounded probabilistic computations between MA and AM, Mathematical foundations of computer science 2003, 249--258. http://haegar.informatik.uni-wuerzburg.de/users/glasser/publications/sbp-ma-am-tr.pdf

[BGR93] B. von Braunmühl, R. Gengler, and R. Rettinger. The alternation hierarchy for sublogarithmic space is infinite, Computational Complexity, v.3 n.3, p.207-230, July 1993 [doi>10.1007/BF01271368] [3]

[BH91] S. R. Buss and L. Hay. On truth-table reducibility to SAT, Information and Computation 91(1):86-102, 1991.

[BH97] C. Berg and J. Håstad. On the BPP hierarchy problem, Technical Report TRITA-NA-9702, Royal Institute of Technology, Sweden, 1997. ftp://ftp.nada.kth.se/pub/documents/Theory/Christer-Berg/bpp.ps.

[BH08] H. Buhrman and J. Hitchcock. NP-Hard sets are exponentially eense unless NP is contained in coNP/poly, Electronic Colloquium on Computational Complexity, ECCC Report TR08-022, accepted on Mar 11, 2008. http://eccc.hpi-web.de/eccc-reports/2008/TR08-022/index.html

[BHR00] B. Borchert, L. Hemaspaandra, and J. Rothe. Restrictive Acceptance Suffices for Equivalence Problems. LMS J. Comput. Math. 3 (2000), 86--95 arXiv:cs.CC/9907041.

[BHW89] R. Beigel, L. Hemachandra, and G. Wechsung. On the power of probabilistic polynomial time, Proceedings of IEEE Complexity'89, pp. 225-230, 1989.

[BHZ87] R. B. Boppana, J. Håstad, and S. Zachos. Does co-NP have short interactive proofs?, Information Processing Letters 25:127-132, 1987.

[BK89] M. Blum and S. Kannan. Designing programs that check their work, Proceedings of ACM STOC'89, 1989.

[BKL+00] D. A. M. Barrington, P. Kadau, K.-J. Lange, and P. McKenzie. On the complexity of some problems on groups input as multiplication tables, http://www-fs.informatik.uni-tuebingen.de/~lange/Arbeiten/fologlog/bklm/neu.ps.gz Proceedings of IEEE Complexity'2000, 2000.

[BKS95] R. Beigel, M. Kummer, and F. Stephan. Approximable sets, Information and Computation 120(2):304-314, 1995. http://www.cis.temple.edu/~beigel/papers/bks-queries2-ic.PS.gz.

[BLM+98] D. A. M. Barrington, C.-J. Lu, P. B. Miltersen, and S. Skyum. Searching constant width mazes captures the AC0 hierarchy, Proceedings of the 1998 Symposium of Theoretical Aspects of Computer Science (STACS'98), 1998. ECCC TR97-044.

[BLM+99] D. A. M. Barrington, C.-J. Lu, P. B. Miltersen, and S. Skyum. On monotone planar circuits, Proceedings of IEEE Complexity'99, 1999. http://www.brics.dk/~bromille/Papers/mpc.ps

[BLS84] R. Book, T. Long, and A. Selman. Quantitative relativizations of complexity classes, SIAM Journal on Computing 13(3):461-487, 1984.

[Blu67] M. Blum. A Machine-Independent Theory of the Complexity of Recursive Functions. J. ACM 14: 322-336, 1967.

[BM04] J. Buresh-Oppenheim and T. Morioka. Relativized NP search problems and propositional proof systems, Proceedings of IEEE Complexity 2004, pp. 54-67, 2004. ECCC TR03-084.

[BM88] L. Babai and S. Moran. Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes, Journal of Computer and Systems Sciences 36:254-276, 1988.

[Boo72] R. Book. On languages accepted in polynomial time, SIAM Journal on Computing 1(4):281-287, 1972.

[Boo74] R. Book. Comparing complexity classes, Journal of Computer and System Sciences 3(9):213-229, 1974.

[Boo94] R. Book. On collapsing the polynomial-time hierarchy, Information Processing Letters 52(5):235-237, 1994.

[Bor77] A. Borodin. On relating time and space to size and depth, SIAM Journal on Computing 6:733-744, 1977.

[Bra77] F.-J. Brandenburg. On one-way auxiliary pushdown automata, Proceedings of the Third GI-Conference on Theoretical Computer Science, Springer LNCS vol. 48, pp. 132-144, 1977.

[Bra79] G. Brassard. A note on the complexity of cryptography IEEE Transactions on Information Theory, 25(2):232-233, 1979.

[Bra06] S. Bravyi. Efficient algorithm for a quantum analogue of 2-SAT, arXiv:quant-ph/0602108v1, 2006.

[BRS91] R. Beigel, N. Reingold, and D. A. Spielman. PP is closed under intersection, Proceedings of ACM STOC'91, pp. 1-9, 1991. http://www.cis.temple.edu/~beigel/papers/brs-pp-jcss.PS.gz.

[Bru90] J. Bruck. Harmonic analysis of polynomial threshold functions, SIAM J. Discrete Math., 3 (1990) 168-177.

[BS00] B. Borchert and F. Stephan. Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory. MLQ Math. Log. Q. 46 (2000), no. 4, 489--504, 2000. Also Proc. 5th Kurt Gödel Colloq. KGS 1997, Springer LNCS 1289, pp. 114-127. MLQ KGS 1997

[BS90] J. Bruck and R. Smolensky. Polynomial threshold functions, AC0 functions and spectral norms, Proceedings of IEEE FOCS'90, pp. 632-641, 1990.

[BS90b] R. B. Boppana and M. Sipser. The complexity of finite functions. chapter in Handbook of Theoretical Computer Science, Volume A (J. van Leeuwen, editor), Elsevier, 1990.

[BSF02] A. Ben-Hur, H. T. Siegelmann, and S. Fishman. A theory of complexity for continuous time systems, Journal of Complexity 18(1):51-86, 2002. http://cmgm.stanford.edu/~asab/Papers/dds2.ps.gz

[BT04] H. Buhrman and L. Torenvliet. Separating complexity classes using structural properties, Proceedings of IEEE Complexity 2004, pp. 130-138, 2004. http://staff.science.uva.nl/~leen/PAPERS/superrobustsets.pdf

[BT06] A. Bogdanov and L. Trevisan. Average-Case Complexity, ECCC Report TR06-073, Revision 01, accepted on Fri Sep 29 22:13:11 2006.

[BT88] D. A. M. Barrington and D. Thérien. Finite monoids and the fine structure of NC1, Journal of the ACM 35(4):941-952, 1988.

[Bur00] P. Bürgisser. Completeness and Reduction in Algebraic Complexity Theory, Springer Series in Algorithms and Computation in Mathematics, Volume 7, 2000.

[Buss93] S. Buss. Algorithms for Boolean formula evaluation and for tree-contraction, Proof Theory, Complexity, and Arithmetic, P. Clote and J. Krajicek (eds), Oxford University Press, 1993, pp. 95-115. http://math.ucsd.edu/~sbuss/ResearchWeb/Boolean3/index.html

[Buss17] S. Buss. Uniform Proofs of ACC Representations, Archive for Mathematical Logic 56(5–6):639–669, 2017.

[BV97] E. Bernstein and U. Vazirani. Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. http://www.cs.berkeley.edu/~vazirani/bv.ps

[BVW98] R. Book, H. Vollmer, and K. W. Wagner. Probabilistic type-2 operators and "almost"-classes, Computational Complexity 7(3):265-289, 1998.

[BVW07] H. Burhman, N. Vereshchagin, R. de Wolf. On computation and communication with small bias. Proceedings of IEEE Conference on Computational Complexity 2007 24-32, 2007.

[BW03] H. Buhrman and R. de Wolf. Quantum Zero-Error Algorithms Cannot be Composed, Information Processing Letters, 87(2):79-84, 2003. arXiv:quant-ph/0211029.

C

[Cai01] J.-Y. Cai. S2P is contained in ZPPNP, Proceedings of IEEE FOCS'2001, pp. 620-629, 2001.

[Cai86] J.-Y. Cai. With probability one, a random oracle separates PSPACE from the polynomial hierarchy, Proceedings of ACM STOC'86, pp. 21-29, 1986.

[Cai87] J. Cai. Probability one separation of the Boolean hieararchy, Lecture Notes in Computer Science, vol 247, p148-158, 1987.

[CCH+01] J.-Y. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara. Some Karp-Lipton-type theorems based on S2, University of Rochester Computer Science Technical Report TR-759, November 2001.

[CC93] L. Cai and J. Chen. On fixed-parameter tractability and approximability of NP-hard optimization problems, Proceedings of ISTCS'93 - Israel Symposium on Theory of Computing and Systems, pp. 118-126, 1993.

[CC97] L. Cai and J. Chen. On fixed-parameter tractability and approximability of NP optimization problems, Journal of Computer and System Sciences 54(3):465-474, 1997.

[CF91] J.-Y. Cai and M. Furst. PSPACE survives constant-width bottlenecks, International Journal of Foundations of Computer Science 2(1):67-76, 1991.

[CO22] Wojciech Czerwiński and Łukasz Orlikowski Reachability in vector addition systems is Ackermann-complete, Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, pages 1229–1240, 2022 arXiv: [4]

[Can96] R. Canetti. More on BPP and the polynomial-time hierarchy, Information Processing Letters 57:237-241, 1996.

[CCG+94] R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Håstad, D. Ranjan, and P. Rohatgi. The random oracle hypothesis is false, Journal of Computer and System Sciences 49(1):24-39, 1994.

[CGQ+24] Z. Chen, J. A. Grochow, Y. Qiao, G. Tang, and C. Zhang. On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups. Proc. ITCS '24 doi:10.4230/LIPIcs.ITCS.2024.31

[CS12] André Chailloux and Or Sattath. The Complexity of the Separable Hamiltonian Problem, Proceedings of the 2012 IEEE Annual Conference on Computational Complexity (CCC), pp. 32-41, 2012. arXiv: 1111.5247.

[CTW13] A. Chattopadhyay, J. Torán, F. Wagner. Graph Isomorphism is Not AC0-Reducible to Group Isomorphism ACM Transactions on Computation Theory Volume 5, Issue 4, November 2013, pp.1--13. [5]

[CW22] B. Chapman and R. Williams. Smaller ACC0 Circuits for Symmetric Functions, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pp. 38:1--38:19, 2022. arXiv:2107.04706, LIPIcs-ITCS-2022-38.

[Che16] L. Chen A Note on Oracle Separations for BQP, arXiv:1605.00619.

[CD05] X. Chen and X. Deng 3-NASH is PPAD-Complete, ECCC TR05-134.

[CCD+03] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman. Exponential algorithmic speedup by quantum walk, Proceedings of ACM Symposium on Theory of Computing, pp. 59-68, 2003. arXiv:quant-ph/0209131.

[CDL01] A. Chiu, G. Davida, and B. Litow. Division in logspace-uniform NC1, Theoretical Informatics and Applications 35(3):259, 2001.

[CP07] Y. Chen and J. Flum. On parameterized path and chordless path problems, Proceedings of the IEEE Conference on Computational Complexity 2007, 250-263.

[CFL83] A. Chandra, S. Fortune, R. Lipton. Unbounded fan-in circuits and associative functions, Proceedings of the fifteenth annual ACM symposium on Theory of computing, 52-60, 1983.

[CFL+93] A. Condon, J. Feigenbaum, C. Lund, and P. Shor. Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions (extended abstract), Proceedings of ACM STOC'93, pp. 305-314, 1993.

[CGH+88] J.-Y. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The Boolean hierarchy I: structural properties, SIAM Journal on Computing 17:1232-1252, 1988. Part II: applications in 18:95-111, 1989.

[CGR+04] M. Crasmaru, C. Glaßer, K. W. Regan, and S. Sengupta. A protocol for serializing unique strategies, Proceedings of MFCS 2004 pp. 660-672, 2004. https://www.cse.buffalo.edu/~regan/papers/pdf/CGRS04.pdf

[CH89] J.-Y. Cai and L. A. Hemachandra. On the power of parity polynomial time, Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 349, pp. 229-240, Springer, 1989.

[CHT+04] R. Cleve, P. Høyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies, Proceedings of IEEE Complexity, pp. 236-249, 2004. arXiv:quant-ph/0404076.

[Chu41] A. Church. The calculi of lambda-conversion, Annals of Mathematical Studies 6, Princeton Univ. Press, 1941.

[CIK+03] C. Calabro, R. Impagliazzo, V. Kabanets, et al. The complexity of Unique -SAT: An isolation lemma for -CNFs., Proceedings of the IEEE Conference on Computational Complexity 2003, 135-141.

[CKK+95] F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther. On real Turing machines that toss coins, Proceedings of ACM STOC'95, pp. 335-342, 1995.

[CKS81] A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. Alternation, Journal of the ACM 28:114-133, 1981.

[CKS+99] P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan. Structure in approximation classes, SIAM Journal on Computing 28:1759-1782, 1999. ECCC TR96-066.

[CKSU05] H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic Algorithms for Matrix Multiplication. Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 379-388, 2005.

[CM01] M. Cryan and P. B. Miltersen. On pseudorandom generators in NC0, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 272-284, 2001.

[CM16] T. Cubitt and A. Montanaro. Complexity Classification of Local Hamiltonian Problems. SIAM Journal on Computing 45:2, 2016. doi:10.1137/140998287.

[CMP18] T. Cubitt, A. Montanaro, and S. Piddock. Universal quantum Hamiltonians. PNAS 115:38, 2018. doi:10.1073/pnas.1804949115.

[CMTV98] H. Caussinus, P. McKenzie, D. Thérien, and H. Vollmer. Nondeterministic NC1 computation, Journal of Computer and System Sciences, 200-212, 1998.

[CMI00] Clay Mathematics Institute. The P versus NP problem (a millennium prize problem), with official problem description by S. Cook, http://www.claymath.org/prizeproblems/pvsnp.htm, 2000.

[CNS99] J.-Y. Cai, A. P. Nerurkar, and D. Sivakumar. Hardness and hierarchy theorems for probabilistic quasi-polynomial time, Proceedings of ACM STOC'99, pp. 726-735, 1999.

[Cob64] A. Cobham. The intrinsic computational difficulty of functions, Proceedings of the 1964 Congress on Logic, Mathematics and the Methodology of Science, pp. 24-30, 1964.

[Cob66] A. Cobham. The recognition problem for the set of perfect squares, Proceedings of the 7th Symposium on Switching and Automata Theory, pp. 78-87, 1966.

[Con73] R. Constable. Type 2 computational complexity, Proceedings of ACM STOC'73, pp. 108­-121, 1973.

[Con92] A. Condon. The complexity of stochastic games, Information and Computation 96(2):203-224, 1992.

[Coo71] S. A. Cook. The complexity of theorem-proving procedures, Proceedings of ACM STOC'71, pp. 151-158, 1971.

[Coo71b] S. A. Cook. Characterizations of pushdown machines in terms of time-bounded computers, Journal of the ACM 18(1):4-18, 1971.

[Coo79] S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space, Proceedings of ACM STOC'79, pp. 338-345, 1979.

[Coo85] S. A. Cook. A taxonomy of problems with fast parallel algorithms, Information and Control 64:2-22, 1985.

[CP95] P. Crescenzi and C. Papadimitriou. Reversible simulation of space-bounded computations, Theoretical Computer Science 143:159-165, 1995.

[CP07] R. Chang and S. Purini. Bounded queries and the NP Machine Hypothesis., Proceedings of the IEEE Conference on Computational Complexity 2007, 52-59.

[CR96] S. Chaudhuri and J. Radhakrishnan. Deterministic Restrictions in Circuit Complexity, Proceedings of ACM STOC 1996, pp. 30-36, 1996.

[CR06] V. Chakaravarthy and S. Roy. Oblivious symmetric alternation, Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS) 2006, 230-241. [6]

[CS92] J. Castro and C. Seara. Characterizations of some complexity classes between Θ2p and Δ2p, Proceedings of STACS 1992, pp. 305-317, 1992.

[CT94] P. Crescenzi and L. Trevisan. An approximation scheme preserving reducibility and its applications, Proceedings of 14th Annual Conference on Foundations of Software Technology and Theoretical Computer Computer Science (FSTTCS), pp. 330-341, Lecture Notes in Computer Science 880, Springer-Verlag, 1994.

[CT97] M. Cesati and L. Trevisan. On the efficiency of polynomial time approximation schemes, ECCC TR97-001, 1997.

[CT07] X. Chen and S.-H. Teng. Paths beyond local search: A nearly tight bound for randomized fixed-point computation. FOCS 2007.

[CW82] D. Coppersmith and S. Winograd. On the Asymptotic Complexity of Matrix Multiplication. SIAM J. Comput. 11(3): 472-492,1982.

[CW90] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, 9:251–280, 1990.

[CW00] R. Cleve and J. Watrous. Fast parallel circuits for the quantum Fourier transform, Proceedings of IEEE Focs'2000, pp. 526-536, 2000. arXiv:quant-ph/0006004.

D

[Dam90] C. Damm. Problems complete for ⊕L, Information Processing Letters 36:247-250, 1990. doi:10.1016/0020-0190(90)90150-V

[Dam91] C. Damm. DET=L(#L), Technical Report Informatik-Preprint 8, Fachbereich Informatik der Humboldt–Universit ̈at zu Berlin, 1991.

[DC89] P. W. Dymond and S. Cook. Complexity theory of parallel time and hardware, Information and Computation 80:205-226, 1989. doi:10.1016/0890-5401(89)90009-6

[DDP+98] A. De Santis, G. Di Crescenzo, G. Persiano, and M. Yung. Image density is complete for non-interactive SZK, Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, pp. 784-795, 1998. doi:10.1007/BFb0055102 (Note: Some results in the paper were later retracted.)

[Dek76] M. I. Dekhtyar. On the relativization of deterministic and nondeterministic complexity classes, Mathematical Foundations of Computer Science (MFCS '76), pp. 255-259, Springer LNCS 45, 1976. doi:10.1007/3-540-07854-1_183

[DGPV20] P. Dixon, S. Gayen, A. Pavan, N. V. Vinodchandran. Perfect Zero Knowledge: New Upperbounds and Relativized Separations, Theory of Cryptography Conference (TCC '20), pp. 768, 2020. ePrint:[7] doi:10.1007/978-3-030-64375-1_24

[DF97] R. G. Downey and M. R. Fellows. Threshold dominating sets and an improved characterization of W[2], Theoretical Computer Science 189, 1997. doi:10.1016/S0304-3975(97)00101-1

[DF99] R. G. Downey and M. R. Fellows. Parameterized Complexity, Springer-Verlag Monographs in Computer Science, 1999. doi:10.1007/978-1-4612-0515-9

[DFT96] R. G. Downey, M. R. Fellows, and U. Taylor. On the parameteric complexity of relational database queries and a sharper characterization of W[1], Combinatorics, Complexity, and Logic, Proceedings of DMTCS'96, Springer-Verlag, pp. 194-213, 1996. Author's website version

[DFT96] R. G. Downey, M. R. Fellows, and U. Taylor. Parameterized circuit complexity and the W hierarchy. Theoret. Computer Sci., 191(1–2):97–115, January 1998. doi:10.1016/S0304-3975(96)00317-9

[DGP05] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou The Complexity of Computing a Nash Equilibrium, SIAM J. Comput. 39(1):195-259, 2009. doi:10.1137/070699652 Originally appeared in STOC 2006, Author's website conference version.

[DHI02] W. van Dam, S. Hallgren, and L. Ip. Quantum algorithms for hidden shift problems, SIAM J. Comput. 36(3):763-778, 2006. doi:10.1137/S009753970343141X Originally appeared on arXiv:quant-ph/0211140 and SODA 2003.

[DP05] C. Daskalakis and C. H. Papadimitriou. Three-player games are hard, ECCC TR05-139, 2005.

[DP08] M. David and T. Pitassi. Separating NOF communication complexity classes RP and NP. ECCC TR08-014 and arXiv:0802.3860 [cs.CC], 2008.

[DW86] E. Dahlhaus and M. K. Warmuth. Membership for growing context-sensitive grammars is polynomial, Journal of Computer and System Sciences 33:456-472, 1986. doi:10.1016/0022-0000(86)90062-0 Originally appeared in CAAP 1986

E

[Edm65] J. Edmonds. Paths, trees, and flowers, Canadian Journal of Mathematics 17(3):449-467, 1965. doi:10.4153/CJM-1965-045-4

[EY07] K. Etessami and M. Yannakakis. On the Complexity of Nash Equilibria and Other Fixed Points. SIAM J. Comput. 2010. doi:10.1137/080720826 Originally appeared in FOCS 2007. Author's website version

F

[Fag73] R. Fagin. Contributions to the Model Theory of Finite Structures, Ph.D. Thesis (1973), U.C. Berkeley

[Fag74] R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation (R. M. Karp, ed.), SIAM-AMS Proceedings Vol. 7, 1974. Author's uploaded copy

[Fen02] S. Fenner. PP-lowness and a simple definition of AWPP, Theory Comput. Syst. 36 (2003), no. 2, 199--212. doi:10.1007/s00224-002-1089-8 ECCC TR02-036.

[FF..] S. Fenner, L. Fortnow, Unpublished.

[FFK+93] S. Fenner, L. Fortnow, S. Kurtz, and L. Li. An oracle builder's toolkit, Inform. Comput. 182(2):95-136, 2003. doi:10.1016/S0890-5401(03)00018-X Originally appeared in Structure in Complexity Theory, pages 120-131, 1993. Author's website version.

[FFK94] S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes, Journal of Computer and System Sciences 48(1):116-148, 1994. doi:10.1016/S0022-0000(05)80024-8. Originally appeared in Structure in Complexity Theory, 1991. Author's website version.

[FG02] J. Flum and M. Grohe. The parameterized complexity of counting problems, SIAM J. Comput. 33(4):892-922, 2004. doi:10.1137/S0097539703427203 Originally appeared in FOCS '02.

[FGH+98] S. Fenner, F. Green, S. Homer, and R. Pruim. Quantum NP is hard for PH, Proceedings of the Sixth Italian Conference on Theoretical Computer Science, World-Scientific, pp. 241-252, 1998. arXiv:quant-ph/9812056.

[FGL+91] U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete, Proceedings of IEEE FOCS'91, pp. 2-12, 1991. doi:10.1109/SFCS.1991.185341

[FGM+89] M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos. On Completeness and Soundness in Interactive Proof Systems. In Advances in Computing Research: a research annual, Vol.~5 (Randomness and Computation, S. Micali, ed.), pages 429--442, 1989.

[Fie98] U. Feige. A threshold of ln(n) for approximating set cover. Journal of the ACM (JACM), 45(4): 634--652, 1998. doi:10.1145/285055.285059

[FK05] L. Fortnow and A. Klivans. NP with small advice, Proceedings of IEEE Complexity'2005, pp. 228-234, 2005. doi:10.1109/CCC.2005.15 Author's website version.

[FK97] U. Feige and J. Kilian. Limited versus polynomial nondeterminism, Chicago Journal of Theoretical Computer Science Article 1, 1997. doi:10.4086/cjtcs.1997.001

[FK97b] U. Feige and J. Kilian. Making games short, Proceedings of ACM STOC'1997, pp. 506-516, 1997. doi:10.1145/258533.258644

[FMF16] H. Filho, R. Machado, and C. Figueiredo. Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3, Theoretical Computer Science 618, 2016. doi:10.1016/j.tcs.2016.01.027 arXiv:cs.CC/1312.2086.

[For94] L. Fortnow. The role of relativization in complexity theory, Bulletin of the EATCS 52, February 1994. Author's website version.

[For02] J. Forster. A linear lower bound on the unbounded error probabilistic communication complexity, Journal of Computer and System Sciences 65(4):612-625, 2002. doi:10.1016/S0022-0000(02)00019-3 Originally appeared in CCC '01

[FR74] M. J. Fischer and M. O. Rabin. Super-exponential complexity of Presburger arithmetic, Complexity of Computation (R. M. Karp, ed.), SIAM-AMS Symposium on Applied Mathematics, 1974. Reprinted in 1998 at doi:10.1007/978-3-7091-9459-1_5. Preliminary version MIT Project MAC Tech Report.


[FR96] L. Fortnow and N. Reingold. PP is closed under truth-table reductions, Information and Computation 124(1):1–6, 1996. doi:10.1006/inco.1996.0001

[FR98] L. Fortnow and J. D. Rogers. Complexity limitations on quantum computation, J. Comput. Syst. Sci. 59(2): 240–252. 1999. Special issue for selected papers from the 13th IEEE Conference on Computational Complexity. Originally appeared in CCC '98. arXiv:cs.CC/9811023.

[FR21] B. Fefferman and Z. Remscrim. Eliminating intermediate measurements in space-bounded Quantum computation, Proceedings of ACM STOC'2021, pp. 1343–1356, 2021. arXiv:cs.CC/2006.03530.

[Fri57] R. M. Friedberg. Two recursively enumerable sets of incomparable degrees of unsolvability, Proceedings of the National Academy of Sciences, 43:236-238, 1957. doi:10.1073/pnas.43.2.236.

[FRS88] L. Fortnow, J. Rompel, and M. Sipser. On the power of multiprover interactive protocols, Theoret. Comput. Sci. 134(2):545-557, 1994. doi:10.1016/0304-3975(94)90251-8 Originally appeared in Complexity '88 Author's website version.

[FS04] L. Fortnow and R. Santhanam. Hierarchy theorems for probabilistic polynomial time, Proceedings of IEEE FOCS'2004, 2004. doi:10.1109/FOCS.2004.33 Author's website version

[FS88] L. Fortnow and M. Sipser. Are there interactive protocols for co-NP languages? Inform. Process. Lett. 28 (1988), no. 5, 249--251. doi:10.1016/0020-0190(88)90199-8 Author's website version

[FSS84] M. Furst, J. Saxe, and M. Sipser. Parity, circuits, and the polynomial hierarchy, Mathematical Systems Theory 17:13-27, 1984. doi:10.1007/BF01744431 Originally appeared in FOCS '81.

[FSW09] L. Fortnow, R. Santhanam and R. Williams. Fixed-Polynomial Size Circuit Bounds, Poceedings of the 24th Annual IEEE Conference on Computational Complexity, pp. 19-26, 2009. doi:CCC.2009.21 Author's website version.

[Fur07] M. Furer. Faster Integer Multiplication, Proc. ACM STOC 2007, pp. 57-66. doi:10.1145/1250790.1250800

[FV93] T. Feder and M. Y. Vardi. Monotone monadic SNP and constraint satisfaction, Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 612-622, 1993. DOI:10.1145/167088.167245.

G

[Gas02] W. Gasarch. The P=?NP poll, SIGACT News Complexity Theory Column 36 (L. A. Hemaspaandra, ed.), 2002.

[Geff91] V. Geffert. Nondeterministic computations in sublogarithmic space and space constructibility, SIAM Journal on Computing v. 20 iss. 3, 1991. [8]

[GG66] S. Ginsburg and S. Greibach. Deterministic context free languages, Information and Control 9:620-648, 1966.

[GGK03] W. Gasarch, E. Golub, and C. Kruskal. Constant time parallel sorting: an empirical view, J. Comput. Syst. Sci. 67:63-91, 2003.

[GHJ+91] J. Goldsmith, L. A. Hemaspaandra, D. Joseph, and P. Young. Near-testable sets. SIAM J. Comput. 20 (1991), no. 3, 506--523

[GHP00] F. Green, S. Homer, and C. Pollett. On the complexity of quantum ACC, Proceeedings of IEEE Complexity'2000, pp. 250-262, 2000. See also: F. Green, S. Homer, C. Moore, and S. Pollett. Counting, fanout, and the complexity of quantum ACC, arXiv:quant-ph/0106017, 2001.

[Gil77] J. Gill. Computational complexity of probabilistic Turing machines, SIAM Journal on Computing 6(4):675-695, 1977.

[GJ79] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.

[GK14] S. Gharibian, and J. Kempe. Hardness of approximation for quantum problems, Quantum Information & Computation 14(5 & 6): 517-540, 2014. Extended abstract appeared in Proceeedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), pages 387-398, Springer, 2012.

[GKM15] V. Girard, M. Koucky, and P. McKenzie. Nonuniform catalytic space and the direct sum for space, ECCC [9]

[GKR15] S. Goldwasser, Y. Kalai, and G. Rothblum. Delegating Computation: Interactive Proofs for Muggles, Journal of the ACM 62(4), 2015

[GKR+95] F. Green, J. Köbler, K. W. Regan, T. Schwentick, and J. Torán. The power of the middle bit of a #P function, Journal of Computer and System Sciences 50(3):456-467, 1995.

[GL14] D. Gavinsky and S. Lovett. En route to the log-rank conjecture: New reductions and equivalent formulations, Proceedings of ICALP'14, pp. 514-524, 2014.

[GLM96] J. Goldsmith, M. A. Levy, and M. Mundhenk. Limited nondeterminism, SIGACT News 27(2):20-29, 1996. http://cs.engr.uky.edu/~goldsmit/papers/extended.ps

[GLM+15] M. Göös, S. Lovett, R. Meka, T. Watson, and D. Zuckerman. Rectangles Are Nonnegative Juntas, Proceedings of ACM STOC'15, pp. 257-266, 2015.

[GLV24] K. Gajulapalli, Z. Li, I. Volkovich Oblivious Classes Revisited: Lower Bounds and Hierarchies, ECCC [10]

[GM15] O. Goldreich and O. Meir. Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly, Transactions on Computation Theory 7(4): 16, 2015. https://eccc.weizmann.ac.il/report/2011/023/

[GMR89] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems, SIAM Journal on Computing 18(1):186-208, 1989.

[GMW91] O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM 38(1):691-729, 1991.

[GN13] D. Gosset and D. Nagaj. Quantum 3-SAT is QMA1-complete, arXiv:[11], 2013.

[GO95] A. Gajentaan and M. Overmars. On a class of problems in computational geometry, Computational Geometry, Volume 5, Issue 3, October 1995, pages 165-185.

[Gol97] O. Goldreich. Notes on Levin's theory of average-case complexity, ECCC TR97-058.

[GP01] F. Green and R. Pruim. Relativized separation of EQP from P^NP, Information Processing Letters 80 (2001) 257-260. http://cs.clarku.edu/~fgreen/papers/eqp.ps

[GP86] L. Goldschlager and I. Parberry. On the construction of parallel computers from various bases of Boolean functions, Theoretical Computer Science 43(1):43-58, 1986.

[GP91] O. Goldreich and E. Petrank. Quantifying knowledge complexity, Proceedings of IEEE FOCS'91, pp. 59-68, 1991. http://www.wisdom.weizmann.ac.il/~oded/PS/gp.ps

[GPW15] M. Göös, T. Pitassi, and T. Watson. Deterministic Communication vs. Partition Number, Proceedings of IEEE FOCS'15, 1077-1088, 2015.

[GPW16a] M. Göös, T. Pitassi, and T. Watson. Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication, Algorithmica, Online First, 2016.

[GPW16b] M. Göös, T. Pitassi, and T. Watson. The Landscape of Communication Complexity Classes, Proceedings of ICALP'16, to appear, 2016.

[GPY19] S. Gharibian, S. Piddock, and J. Yirka. Oracle complexity classes and local measurements on physical Hamiltonians, arXiv: 1909.05981v1 [quant-ph], 2019.

[GQ19] J. A. Grochow and Y. Qiao. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness, SIAM J. Comput. 52(2):568-617, 2023 doi:10.1137/21M1441110. Originally appeared in ITCS '21 and arXiv:1907.00309.

[GQ21] J. A. Grochow and Y. Qiao. On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors, ACM Trans. Comput. Theory 16(1):2:1-2:39. doi:10.1145/3625308. Originally appeared in CCC '21.

[Grä92] E. Grädel Capturing complexity classes b fragments of second order logic Information and computaiton 119 (1995), 129-135

[Gre90] F. Green. An oracle separating +P from PPPH, Inform. Process. Lett. 37 (1991), no. 3, 149--153.

[Gre93] F. Green. On the power of deterministic reductions to C=P, Math. Systems Theory 26 (1993), no. 2, 215--233.

[Gri83] D. Ju. Grigor'ev. Complexity of 'wild' matrix problems and of the isomorphism of algebras and graphs, Journal of Mathematical Sciences 22(3):1285-1289, 1983. doi:10.1007/BF01084390

[Gri01] M. Grigni. A Sperner lemma complete for PPA, Information Processing Letters 77:5-6 (2001), pp. 255-259.

[Gro12] J. A. Grochow. Matrix Lie algebra isomorphism, Proceedings of the 2012 IEEE 27th Conference on Computational Complexity, 2012. doi:10.1109/CCC.2012.34 ECCC TR11-168, 2011.

[GS86] S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems, Proceedings of ACM STOC'86, pp. 58-68, 1986.

[GS88] J. Grollman and A. L. Selman. Complexity measures for public-key cryptosystems, SIAM Journal on Computing 17:309-335, 1988.

[GS89] Y. Gurevich and S. Shelah. Nearly Linear Time, Proceedings of LFCS'89, Springer LNCS 363, pp. 108-118, 1989.

[GS90] M. Grigni and M. Sipser. Monotone complexity, Proceedings of LMS Workshop on Boolean Function Complexity (M. S. Paterson, ed.), Durham, Cambridge University Press, 1990. http://www.mathcs.emory.edu/~mic/papers/4.ps

[GS91] M. Grigni and M. Sipser. Monotone separation of NC1 from logspace, Proceedings of IEEE Complexity'91, pp. 294-298, 1991.

[GS15] S. Gharibian, and J. Sikora. Ground state connectivity of local Hamiltonians, Proceeedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), volume 9134 of Lecture Notes in Computer Science, pages 617-628, 2015.

[GSS+03] C. Glaßer, A. L. Selman, S. Sengupta, and L. Zhang. Disjoint NP-pairs, ECCC TR03-011, 2003.

[GSSSY18] S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka. Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2), Computational Complexity 31, 13, 2022. doi:10.1007/s00037-022-00231-8.

[GST03] D. Gutfreund, R. Shaltiel, and A. Ta-Shma. Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games, Comput. Complexity 12 (2003), no. 3-4, 85--130. http://www.cs.huji.ac.il/~danig/pubs/ccc.ps.

[GSV99] O. Goldreich, A. Sahai, and S. Vadhan. Can statistical zero knowledge be made non-interactive? or on the relationship of SZK and NISZK, ECCC TR99-013, 1999. Abstract appeared in CRYPTO'99.

[GTW+91] R. Gavaldá, L. Torenvliet, O. Watanabe, and J. Balcázar. Generalized Kolmogorov complexity in relativized separations, Proceedings of MFCS'91 (Mathematical Foundations of Computer Science), Springer-Verlag Lecture Notes in Computer Science, vol. 452, pp. 269-276, 1991.

[Gup95] S. Gupta. Closure properties and witness reduction, Journal of Computer and System Sciences 50(3):412-432, 1995. ftp://ftp.cis.ohio-state.edu/pub/tech-report/1993/TR46.ps.gz

[Gur87] Y. Gurevich. Complete and incomplete randomized NP problems, Proceedings of IEEE FOCS'87, pp. 111-117, 1987.

[Gur89] E. Gurari. An Introduction to the Theory of Computation, Computer Science Press, 1989. http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html.

[Gut05] G. Gutoski. Upper bounds for quantum interactive proofs with competing provers, Proceedings of IEEE Complexity'2005, pp. 334-343, 2005. http://www.cs.uwaterloo.ca/~gmgutosk/gutoskig_competing.pdf.

[GV02] M. de Graaf and P. Valiant. Comparing EQP and MODp^kP using polynomial degree lower bounds, arXiv:quant-ph/0211179, 2002.

[GV99] O. Goldreich and S. Vadhan. Comparing entropies in statistical zero-knowledge with applications to the structure of SZK, Proceedings of IEEE Complexity'99, pp. 54-73, 1999. ECCC TR98-063.

[GW05] G. Gutoski and J. Watrous. Quantum interactive proofs with competing provers, Proceedings of STACS'2005, pp. 605-616, Springer-Verlag, 2005. arXiv:cs.CC/0412102.

[GW07] G. Gutoski and J. Watrous. Toward a general theory of quantum games, In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC'07), pages 565-574, 2007. arXiv:quant-ph/0611234.

[GW10] G. Gutoski and X. Wu. Short quantum games characterize PSPACE, 2010. arXiv:arXiv:1011.2787.

[GW96] A. Gál and A. Wigderson. Boolean complexity classes vs. their arithmetic analogs, Random Structures and Algorithms 9:1-13, 1996. ECCC TR95-049.

[GW14] M. Göös and T. Watson. Communication Complexity of Set-Disjointness for All Probabilities, Proceedings of RANDOM'14, 721-736, 2014.

[GY16] S. Gharibian, and J. Yirka. The complexity of simulating local measurements on quantum systems, Quantum 3, pp. 189, 2019. doi:10.22331/q-2019-09-30-189.

[GY24] S. Grewal, and J. Yirka. The Entangled Quantum Polynomial Hierarchy Collapses, arXiv:quant-ph/2401.01453, 2024.

[GZ97] O. Goldreich and D. Zuckerman. Another proof that BPP subseteq PH (and more), ECCC TR97-045.


[GHJ+22] M. Göös, A. Hollender, S. Jain, G. Maystre, W. Pires, R. Robere, R. Tao Separations in Proof Complexity and TFNP, ECCC TR22-058.

H

[Hal02] S. Hallgren. Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Proceedings of ACM STOC'2002, 2002. http://www.cse.psu.edu/~hallgren/pell.pdf.

[Har78] J. Hartmanis. Feasible Computations and Provable Complexity Properties, SIAM, 1978.

[Har87] J. Hartmanis. The collapsing hierarchies, Bulletin of the EATCS 33, October 1987. http://external.nj.nec.com/homepages/fortnow/beatcs/column33.ps.

[Har87b] J. Hartmanis. Sparse complete sets for NP and the optimal collapse of the polynomial hierarchy, Bulletin of the EATCS 32, June 1987. http://external.nj.nec.com/homepages/fortnow/beatcs/column32.ps.

[Has87] J. Håstad. Computational Limitations for Small-Depth Circuits, MIT Press, 1987.

[Has88] J. Håstad. Oneway permutations in NC0, Information Processing Letters 26:153-155, 1988.

[Has90] J. Håstad. Tensor rank is NP-complete, J. Algorithms, 11(4):644-654, 1990.

[Has01] J. Håstad. Some optimal inapproximability results, Journal of the ACM, 48(4):798-3859, 2001. http://www-sunos4.nada.kth.se/~johanh/optimalinap.ps

[HCC+92] J. Hartmanis, R. Chang, S. Chari, D. Ranjan, and P. Rohatgi. Relativization: a revisionistic retrospective, Bulletin of the EATCS 47, June 1992. http://external.nj.nec.com/homepages/fortnow/beatcs/column47.ps.

[HCK+88] J. Hartmanis, R. Chang, J. Kadin, and S. G. Mitchell. Some observations about relativization of space bounded computations, Bulletin of the EATCS 35, June 1988. http://external.nj.nec.com/homepages/fortnow/beatcs/column35.ps.

[Hel84a] H. Heller. Relativized polynomial hierarchies extending two levels, Mathematical Systems Theory 17(2):71-84, 1984.

[Hel84b] H. Heller. On Relativized Polynomial and Exponential Computations, SIAM Journal on Computing 13(4):717-725, 1984.

[Hel86] H. Heller. On Relativized Exponential and Probabilistic Complexity Classes, Inform. and Control 71 (1986), no. 3, 231--243

[Hem89] L. Hemachandra. The strong exponential hierarchy collapses, Journal of Computer and System Sciences 39(3):299-322, 1989.

[Her90] U. Hertrampf. Relations among MOD-classes, Theoretical Computer Science 74:325-328, 1990.

[Her97] U. Hertrampf. Acceptance by transformation monoids (with an application to local self-reductions), Proceedings of IEEE Complexity'97, pp. 213-224, 1997.

[Hes01] W. Hesse. Division is in uniform TC0, Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 2001. http://www.cs.umass.edu/~whesse/div.ps

[HH76] J. Hartmanis and J. Hopcroft. Independence results in computer science, ACM SIGACT News 8(4):13-24, 1976.

[HH86] J. Hartmanis and L. Hemachandra. Complexity classes without machines: on complete languages for UP, Proceedings of ICALP'86, Springer-Verlag Lecture Notes in Computer Science volume 226, pp. 123-135, 1986.

[HHH98] E. Hemaspaandra, L. Hemaspaandra, and H. Hempel. What's up with downward collapse: using the easy-hard technique to link Boolean and polynomial hierarchy collapses, SIGACT News 29(3):10-22, 1998. arXiv:cs.CC/9910002.

[HHK+05] L. Hemaspaandra, C. Homan, S. Kosub, and K. Wagner. The complexity of computing the size of an interval, Technical Report TR-856, Department of Computer Science, University of Rochester, 2005. This is an expanded version of HKW01

[HHN+95] L. Hemaspaandra, A. Hoene, A. Naik, M. Ogihara, A. Selman, T. Thierauf, and J. Wang. Nondeterministically selective sets, International Journal of Foundations of Computer Science (IJFCS), 6(4):403-416, 1995.

[HHR97] E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP, Proceedings of ICALP'97, Springer-Verlag Lecture Notes in Computer Science, 1997. arXiv:cs.CC/9907036.

[HHT97] Y. Han, L. Hemaspaandra, and T. Thierauf. Threshold computation and cryptographic security, SIAM Journal on Computing 26(1):59-78, 1997.

[HI02] W. Hesse and N. Immerman. Complete problems for dynamic complexity classes, Proceedings of Logic in Computer Science (LICS), 2002. http://www.cs.umass.edu/~immerman/pub/completeLICS.pdf

[HJV93] L. Hemaspaandra, R. Jain, and N. K. Vereshchagin. Banishing robust Turing completeness, International Journal of Foundations of Computer Science, 3-4:245-265, 1993.

[HKW01] L. Hemaspaandra, S. Kosub, and K. Wagner. The complexity of computing the size of an interval, Proceedings of ICALP'01, Springer-Verlag Lecture Notes in Computer Science, 2001.

[HLS65] J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations, Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design, pp. 179-190, 1965.

[HM13] A. W. Harrow and A. Montanaro. Testing product states, quantum Merlin-Arthur games and tensor optimisation, Journal of the ACM vol. 60 no. 1, 2013 arXiv:1001.0017.

[HMP+93] A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, and G. Turán. Threshold circuits of bounded depth, Journal of Computer and System Sciences 46(2):129-154, 1993.

[HN06] D. Harnik and M. Naor. On the compressibility of NP instances and cryptographic applications. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 719-728, 2006. http://www.cs.technion.ac.il/~harnik/Compress.pdf

[HNO+96] L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman. Computing solutions uniquely collapses the polynomial hierarchy, SIAM Journal on Computing 25(4):697-708, 1996. ECCC TR96-027.

[HO02] L. Hemaspaandra and M. Ogihara. The Complexity Theory Companion, Springer-Verlag, 2002. See also http://www.cs.rochester.edu/u/lane/=companion/.

[HPV77] J. Hopcroft, W. Paul, and L. Valiant. On time versus space, Journal of the ACM 24(2):332-337, 1977.

[HR90] B. Halstenberg and R. Reischuk. Relations between communication complexity classes, Journal of Computer and System Sciences 41(3):402-429, 1990.

[HRV00] U. Hertrampf, S. Reith, and H. Vollmer. A note on closure properties of logspace MOD classes, Information Processing Letters 75(3):91-93, 2000. http://www.thi.uni-hannover.de/forschung/publikationen/daten/he-re-vo99.ps.gz

[HS65] J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms, Transactions of the AMS 117:285-305, 1965.

[HS92] S. Homer and A. L. Selman. Oracles for structural properties: the isomorphism problem and public-key cryptography, Journal of Computer and System Sciences 44(2):287-301, 1992.

[HS05] P. Høyer and R. Špalek. Qauntum fan-out is powerful, Theory of computing (1)1:81-103, 2005.

[HT03] C. M. Homan and M. Thakur. One-way permutations and self-witnessing languages, Journal of Computer and System Sciences 67 (2003), 608-622. [12].

[HT06] L. Hella and J. M. Turull-Torres. Computing queries with higher-order logics, Theorical. Comput. Sci. 355 (2006), 197-214. [13].

[HY84] J. Hartmanis and Y. Yesha. Computation times of NP sets of different densities, Theoretical Computer Science 34:17-32, 1984.

I

[Iba72] O. Ibarra. A note concerning nondeterministic tape complexities, Journal of the ACM 4:608-612, 1972. doi:10.1145/321724.321727

[IKW01] R. Impagliazzo, V. Kabanets, and A. Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time, J. Comput. Syst. Sci., 2002. doi:10.1016/S0022-0000(02)00024-7 Originally appearing in IEEE CCC 2001. Author's website version

[IL90] R. Impagliazzo and L. A. Levin. No better ways to generate hard NP instances than picking uniformly at random, Proceedings of IEEE FOCS'90, pp. 812-821, 1990. doi:10.1109/FSCS.1990.89604

[IM03] R. Impagliazzo and P. Moser. A zero-one law for RP and derandomization of AM if NP is not small, Information and Computation 207(7):787-792, 2009. doi:10.1016/j.ic.2009.02.002 Originally appeared as "A zero one law for RP" in IEEE CCC 2003.

[Imp95] R. Impagliazzo. A personal view of average-case complexity, Proceedings of the 10th Conference on Structure in Complexity Theory, 134-147, 1995. doi:10.1109/SCT.1995.514853 Author's website version

[Imm82] N. Immerman. Relational queries computable in in polynomial time. Information and Control 68(1-3):86-104, 1986. doi:10.1016/S0019-9958(86)80029-8 Originally appeared in STOC 1982. Author's website conference version

[Imm83] N. Immerman. Languages That Capture Complexity Classes SIAM J. Comput., 16(4):760-778, 1986. doi:10.1137/0216051 Originally appeared as "Languages Which Capture Complexity Classes" in STOC 1983. Author's website version

[Imm88] N. Immerman. Nondeterministic space is closed under complement, SIAM Journal on Computing, 17:935-938, 1988. doi:10.1137/0217058 Originally appeared in SCT 1988 Author's website version

[Imm89] N. Immerman. Expressibility and Parallel Complexity SIAM Journal on Computing, 18:625-638, 1989. doi:10.1137/0218043 Author's website version

[Imm98] N. Immerman. Descriptive Complexity, Springer Graduate Texts in Computer Science, 1998. doi:10.1007/978-1-4612-0539-5

[Imp02] R. Impagliazzo. Hardness as randomness: a survey of universal derandomization, Proceedings of the ICM, Beijing, vol. 3, pp. 649-658, 2002. arXiv:cs.CC/0304040.

[IN96] R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum, Journal of Cryptology 9(4):199-216, 1996. doi:10.1007/BF00189260 Originally appeared in FOCS 1989 (technically SFCS). Author's website version

[IPZ01] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity, Journal of Computer and System Sciences 63(4):512-530, 2001. doi:10.1006/jcss.2001.1774 Originally appeared in SFCS 1998. Author's website journal version

[IS91] R. Impagliazzo and M. Sudan. Private communication, cited in [#bg94" style="color:maroon">[BG94], 1991.

[IT89] R. Impagliazzo and G. Tardos. Decision versus search problems in super-polynomial time, in Proceedings of IEEE FOCS 1989, pp. 222-227, 1989. doi:SFCS.1989.63482

[Ito10] T. Ito Polynomial-Space Approximation of No-Signaling Provers, in Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 2010, pp. 140-151. doi:10.1007/978-3-642-14165-2_13 arXiv:0908.2363.

[IV12] T. Ito and T. Vidick. A multi-prover interactive proof for NEXP sound against entangled provers, to appear in Proceedings of IEEE FOCS 2012 doi:10.1109/FOCS.2012.11 arXiv:1207.0550.

[IW97] R. Impagliazzo and A. Wigderson. P=BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of ACM STOC'97, pp. 220-229, 1997. doi:10.1145/258533.258590 Author's website version

J

[JNVWY20] Z. Ji, A. Natarajan, T. Vidick, J. Wright, H. Yuen. MIP* = RE, arXiv:2001.04383, 2020.

[Jeř07] E. Jeřábek. Approximate counting in bounded arithmetic, Journal of Symbolic Logic 72(3):959–993, 2007. Available on JSTOR

[Jeř12] E. Jeřábek. Integer factoring and modular square roots, Journal of Computer and System Sciences 82(2):380–394, 2016. doi:10.1016/j.jcss.2015.08.001 arXiv:1207.5220

[JJUW09] R. Jain, Z. Ji, S. Upadhyay, and J. Watrous. QIP = PSPACE, J. ACM 58(6):1-27, 2011. doi:10.1145/2049697.2049704 arXiv:0907.4737.

[JKS02] J. C. Jackson, A. R. Klivans, and R. A. Servedio. Learnability beyond AC0, Proceedings of ACM STOC'2002, pp. 776-784, 2002. doi:10.1145/509907.510018 Author's website version

[JL95] D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems, SIAM Journal on Computing 24(2):279-295, 1995. doi:10.1137/S0097539792238133 Author's website version

[Joh90] D. S. Johnson. A catalog of complexity classes, chapter 2 in Handbook of Theoretical Computer Science, Volume A (J. van Leeuwen, editor), Elsevier, 1990.

[Jon98] N. D. Jones. LOGSPACE and PTIME Characteried by Programming Languages, Theoret. Comput. Sci. 228(1-2):151-174, 1999. doi:10.1016/S0304-3975(98)00357-0 https://core.ac.uk/download/pdf/82651296.pdf

[JPY88] D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis. How easy is local search?, Journal of Computer and System Sciences 37:79-100, 1988. DOI:10.1016/0022-0000(88)90046-3 Originally appeared in FOCS 1985.

[JSV01] M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, J. ACM 51(4):671-697, 2004. doi:10.1145/1008731.1008738 Originally appeared in STOC 2001 , ECCC TR00-079.

[Jun85] H. Jung. On probabilistic time and space, Proceedings of 12th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, 194:310-317, 1985. doi:10.1007/BFb0015756

[JW04] M. Jerrum and U. Wagner. Counting, Sampling, and Integrating: Algorithms and Complexity, Chapter 3 (lecture notes labeled as under construction). http://www.dcs.ed.ac.uk/home/mrj/ETHbook/chap3.ps.

[JW09] R. Jain and J. Watrous. Parallel approximation of non-interactive zero-sum quantum games, Proceedings of the 24th Annual IEEE Conference on Computational Complexity, pages 243–253, 2009. doi:10.1109/CCC.2009.26 arXiv:0808.2775 [quant-ph].

[JWB03] D. Janzing, P. Wocjan, and T. Beth. Cooling and low energy state preparation for 3-local Hamiltonians are FQMA-complete, arXiv:quant-ph/0303186, 2003.

[JY88] D. S. Johnson and M. Yannakakis. On generating all maximal independent sets, Information Processing Letters 27(3):119-123, 1988. doi:10.1016/0020-0190(88)90065-8

K

[Kad88] J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy collapses, SIAM Journal on Computing 17:1263-1282, 1988.

[Kan82] R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets, Information and Control 55:40-56, 1982.

[Kar72] R. M. Karp. Reducibility among combinatorial problems, Complexity of Computer Computations (J. W. Thatcher and R. E. Miller, eds.), Plenum Press, 1972.

[Kar86] H. Karloff. A Las Vegas algorithm for maximum matching, Combinatorica 6:387-392, 1986.

[KF84] C. M. R. Kintala and P. Fischer. Refining nondeterminism in relativized complexity classes, SIAM Journal on Computing 13:329-337, 1984.

[Kha79] L. G. Khachiyan. A polynomial algorithm for linear programming, Soviet Math Doklady 20:191-194, 1979.

[Kha93] M. Kharitonov. Cryptographic hardness of distribution-specific learning, Proceedings of ACM STOC'93, pp. 372-381, 1993.

[KI02] V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity 13:1–46, 2004. DOI:10.1007/s00037-004-0182-6, https://www.cs.sfu.ca/~kabanets/Research/poly.html

[KKR04] J. Kempe, A. Kitaev, and O. Regev. The Complexity of the Local Hamiltonian Problem, SIAM Journal of Computing, Vol. 35(5), p. 1070-1097 (2006). arXiv:quant-ph/0406180.

[KL82] R. M. Karp and R. J. Lipton. Turing machines that take advice, Enseign. Math. 28:191-201, 1982.

[Kla03] H. Klauck. Rectangle size bounds and threshold covers in communication complexity, Proceedings of IEEE CCC'03, pp. 118-134, 2003.

[Kla07] H. Klauck. Lower bounds for quantum communication complexity, SIAM Journal on Computing 37(1):20-46, 2007.

[Kla11] H. Klauck. On Arthur Merlin games in communication complexity, Proceedings of IEEE CCC'11, pp. 189-199, 2011.

[Kle71] S. C. Kleene. Introduction to Metamathematics, Elsevier, 1971.

[KM02] H. Kobayashi and K. Matsumoto. Quantum multi-prover interactive proof systems with limited prior entanglement, Proceedings of ISAAC'2002, pp. 115-127, 2002. arXiv:cs.CC/0102013.

[KM92] D. Koller and N. Megiddo. On the Complexity of Two-person Zero-sum Games in Extensive Form, Games and Economic Behavior 4, 528-552, 1992. http://theory.stanford.edu/~megiddo/pdf/recall.pdf

[KM99] A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses, in Proceedings of ACM STOC'99, pp. 659-667, 1999.

[KMS+99] S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational views of approximability, SIAM Journal on Computing 28:164-191, 1999. ECCC TR95-023.

[KMSY14] G. Kol, S. Moran, A. Shpilka, and A. Yehudayoff. Approximate nonnegative rank is equivalent to the smooth rectangle bound, Proceedings of the ICALP'14, pp. 701-712, 2014.

[KMY01] H. Kobayashi, K. Matsumoto, and T. Yamakami. Quantum certificate verification: single versus multiple quantum certificates, arXiv:quant-ph/0110006, 2001.

[Ko82] K. Ko. Some observations on the probabilistic algorithms and NP-hard problems, Information Processing Letters 14(1):39-43, 1982.

[Ko85] K. Ko. On some natural complete operators, Theoretical Computer Science 37(1):1-30, 1985.

[Kob02] H. Kobayashi. Non-interactive quantum statistical and perfect zero-knowledge, arXiv:quant-ph/0207158, 2002.

[Kob89] J. Köbler. Strukturelle Komplexität von Anzahlproblemen, PhD thesis, Universität Stuttgart, 1989.

[Koi96] P. Koiran. Hilbert's Nullstellensatz is in the polynomial hierarchy, Journal of Complexity 12(4):273-286, 1996, DIMACS TR 96-27.

[Koz92] D. C. Kozen. On the Myhill-Nerode theorem for trees, Bulletin of the EATCS 47:170-173, 1992.

[Koz97] D. C. Kozen. Automata and Computability, Springer-Verlag, 1997.

[KP89] J. Krajicek and P. Pudlak. Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations, J. Symb. Log., 54:1063-79, 1989.

[KPTWY24] J. Kallaugher, O. Parekh, K. Thompson, Y. Wang, and J. Yirka. Complexity Classification of Product State Problems for Local Hamiltonians. arXiv:2401.06725, 2024.

[KR03] J. Kempe and O. Regev. 3-Local Hamiltonian is QMA-complete, Quantum Inf. Comput., 3(3):258-264, 2003. arXiv:quant-ph/0302079.

[Kra..] H. Krawczyk. Unpublished.

[KRC00] V. Kabanets, C. Rackoff, and S. A. Cook. Efficiently approximable real-valued functions, ECCC TR00-034, 2000.

[Kre88] M. Krentel. The complexity of optimization problems, Journal of Computer and System Sciences 36:490-509, 1988.

[KRR13] Y. T. Kalai, R. Raz, and R. D. Rothblum. How to Delegate Computations: The Power of No-Signaling Proofs, ePrint Report 2013/862, 2013.

[KRS90] C. P. Kruskal, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms, Theoretical Computer Science 71:95-132, 1990.

[KS05] N. Kayal and N. Saxena. On the ring isomorphism and automorphism problems, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, 2-12, 2005.

[KST+89] J. Köbler, U. Schöning, and J. Torán. On counting and approximation, Acta Informatica 26:363-379, 1989.

[KST+89b] J. Köbler, U. Schöning, S. Toda, and J. Torán. Turing machines with few accepting computations and low sets for PP, Proceedings of IEEE Complexity'89, pp. 208-215, 1989. http://www.informatik.hu-berlin.de/Forschung_Lehre/algorithmenII/Papers/few.ps.gz

[KST92] J. Köbler, U. Schöning, and J. Torán. Graph isomorphism is low for PP, Computational Complexity 2:301-330, 1992.

[KST93] J. Köbler, U. Schöning, and J. Torán. The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, 1993.

[KSV02] A. Kitaev, A. Shen, and M. N. Vyalyi. Classical and Quantum Computation, American Mathematical Society, 2002.

[KT94] P. G. Koliatis and M. N. Thakur. Logical definability of NP optimization problems, Information and Computation 115:321-353, 1994.

[KT96] J. Köbler and S. Toda. On the power of generalized MOD-classes, Mathematical Systems Theory 29(1):33-46, 1996. ftp://theorie.informatik.uni-ulm.de/pub/papers/ti/mod.ps.gz

[Kup09] G. Kuperberg. How hard is it to approximate the Jones polynomial?, 2009. arXiv:quant-ph/0908.0512v1.

[Kur64] S. Y. Kuroda. Classes of languages and linear-bounded automata, Information and Control 7:207-233, 1964.

[Kur83] S. Kurtz. On the random oracle hypothesis, Information and Control 57:40-47, 1983.

[Kur85] S. Kurtz. On Relativized Exponential and Probabilistic Complexity Classes, Information and Control 71:231-243, 1985.

[KUW86] R. Karp, E. Upfal, and A. Wigderson. Constructing a perfect matching is in random NC, Combinatorica 6:35-48, 1986.

[KV88] M. Karpinski and R. Verbeek. Randomness, provability, and the separation of Monte Carlo time and space, Lecture Notes in Computer Science 270, pp. 189-207, Springer, 1988.

[KV94] M. Kearns and L. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM 41(1):67-95, 1994. http://www.cis.upenn.edu/~mkearns/papers/crypto.pdf

[KV96] M. Karpinski and R. Verbeek. On Randomized Versus Deterministic Computation, Theoret. Comput. Sci. 154 (1996), no. 1, 23--39. ECCC TR95-021.

[KW..] A. Kitaev and J. Watrous. Unpublished.

[KW00] A. Kitaev and J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems, Proceedings of ACM STOC'2000, pp. 608-617, 2000. https://cs.uwaterloo.ca/~watrous/Papers/QuantumInteractiveProofs.pdf

[KW88] M. Karchmer and A. Wigderson. Monotone circuits for connectivity require superlogarithmic depth, Proceedings of ACM STOC'88, pp. 539-550, 1988.

[KW93] M. Karchmer and A. Wigderson. On span programs, Proceedings of IEEE Complexity'93, pp. 102-111, 1993.

[KW98] J. Köbler and O. Watanabe. New collapse consequences of NP having small circuits, SIAM Journal on Computing 28(1):311-324, 1998. http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Papers/collapse.ps.gz

[KW15] J. Kwisthout. Tree-width and the computational complexity of MAP approximations in Bayesian networks, Journal of Artificial Intelligence Research 53:699-720, 2015. http://www.socsci.ru.nl/johank/tree-width_PP.pdf

L

[Lad75] R. Ladner. On the structure of polynomial time reducibility, Journal of the ACM 22:155-171, 1975. doi:10.1145/321864.321877

[Lau83] C. Lautemann. BPP and the polynomial time hierarchy, Information Processing Letters 17:215-218, 1983. doi:10.1016/0020-0190(83)90044-3

[Lee02] T. Lee. Arithmetical definability over finite structures, Mathematical Logic Quarterly, Vol. 49(4), 2003. doi:10.1002/malq.200310041 Author's webpage version

[Ler22] Jérôme Leroux The Reachability Problem for Petri Nets is Not Primitive Recursive, Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, Pages 1241–1252, 2022 arXiv: [14]

[Lev73] L. A. Levin. Universal sequential search problems (in Russian), Problemy Peredachi Informatsii 9(3):265-266, 1973. http://mi.mathnet.ru/ppi914 English translation digitally available in Trakhtenbrot "A survey of Russian approaches to perebor (brute-force search) algorithms", Ann. Hist. Comput. 6(4):384-400, 1984, doi:10.1109/MAHC.1984.10036.

[Lev86] L. A. Levin. Average case complete problems, SIAM Journal on Computing, 15:285-286, 1986. doi:10.1137/0215020

[LFK+90] C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proofs, J. ACM, 39(4):859-868, 1992. doi:10.1145/146585.146605 Originally appeared in FOCS 1990 Authors' webpage version

[Li93] L. Li. On the Counting Functions, PhD thesis, University of Chicago, 1993. http://newtraell.cs.uchicago.edu/files/tr_authentic/TR-93-12.ps

[Li23] Z. Li. Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform, Electronic Colloquium on Computational Complexity (ECCC), 2023 ECCC Version

[LiRe93] M. Liskiewicz, R. Reischuk. The complexity world below logarithmic space, Proceedings of the Structure in Complexity Theory Conference, 64-78, 1993. doi:10.1109/SCT.1994.315816 Author's webpage version

[Li11] Y. D. Li. BQP and PPAD, Electronic Colloquium on Computational Complexity TR11-103, 2011. arXiv:1108.0223 [cs.CC]

[LL76] R. Ladner and N. A. Lynch. Relativization of questions about log space computability, Mathematical Systems Theory 10:19-32, 1976. doi:10.1007/BF01683260

[LMN93] N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability, Journal of the ACM 40(3):607-620, 1993. doi:10.1145/174130.174138

[LMSV01] C. Lautemann, P. McKenzie, T. Schwentick, H. Vollmer. The Descriptive Complexity Approach to LOGCFL. J. Comput. Syst. Sci. 62(4):629-652. doi:10.1006/jcss.2000.1742

[LMT97] K. Lange, P. McKenzie, and A. Tapp. Reversible space equals deterministic space (extended abstract), Journal of Computer and System Sciences, 60(2):354-367, 2000. doi:10.1006/jcss.1999.1672 Originally appeared in CCC 1997

[LP82] H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation, Theoretical Computer Science 19:161-187, 1982. doi:10.1016/0304-3975(82)90058-5

[LS74] E. A. Lamagna and J. E. Savage Combinational complexity of some monotone functions, FOCS (previously SWAT) 140-44, 1974. doi:10.1109/SWAT.1974.9

[Lut91] J. H. Lutz. An upward measure separation theorem, Theoretical Computer Science 81:127-135, 1991. doi:10.1016/0304-3975(91)90320-2 Author's webpage version

[Lut93] J. H. Lutz. The quantitative structure of exponential time, Proc. 8th Structure in Complexity Theory Conference, 158-175, 1993. doi:10.1109/SCT.1993.336530 See also version in Complexity Theory Retrospective II, Springer, 1998.

[LV97] M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications (second edition), Springer, 1997. doi:10.1007/978-0-387-49820-1

M

[MV97] Meena Mahajan and V. Vinay. Determinant: Combinatorics, Algorithms, and Complexity, Chicago J. Theoret. Comput. Sci., Article 5, 1997. doi:10.4086/cjtcs.1997.005

[M08] L. Malka. How to achieve perfect simulation, and a complete problem for non-interactive perfect zero-knowledge. J. Cryptology 28:533-550, 2015. doi:10.1007/s00145-013-9165-6 Originally appeared in TCC 2008 Author's website version.

[Mah18] U. Mahadev. Classical Verification of Quantum Computations, arXiv:abs/1804.01082.

[Mah82] S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis, Journal of Computer and System Sciences 25:130-143, 1982. doi:10.1016/0022-0000(82)90002-2 Originally appeared in FOCS 1980

[May94] E. Mayordomo. Almost every set in exponential time is P-bi-immune, Theoretical Computer Science 136(2):487-506, 1994. doi:10.1016/0304-3975(94)00023-C Originally appeared in MFCS 1992

[May94b] E. Mayordomo. Contributions to the study of resource-bounded measure, PhD thesis, Universitat Politecnica de Catalunya, 1994. Available on ECCC.

[MS89] E. W. Mayr and A. Subramanian. The complexity of circuit value and network stability, J. Comput. Syst. Sci. 44(2):302-323, 1992. doi:10.1016/0022-0000(92)90024-D Originally appeared in Complexity '89. Stanford technical report STAN-CS-89-1278

[MC00] C. Moore and J. P. Crutchfield. Quantum automata and quantum grammars, Theoretical Computer Science 237:275-306, 2000. doi:10.1016/S0304-3975(98)00191-1 Preprint available as arXiv:quant-ph/9707031.

[Mel00] D. van Melkebeek. The zero-one law holds for BPP, Theoretical Computer Science 244(1-2):283-288, 2000. doi:10.1016/S0304-3975(00)00191-2

[Mes99] J. Messner. On optimal algorithms and optimal proof systems, STACS, Lecture Notes in Computer Science 1563:541-550, 1999. doi:10.1007/3-540-49116-3_51

[Mil76] G. Miller. Riemann's hypothesis and tests for primality, Journal of Computer and System Sciences, 13:300-317, 1976. doi:10.1016/S0022-0000(76)80043-8

[Mil92] P. B. Miltersen. Circuit depth relative to a random oracle, Information Processing Letters 42(6):295-298, 1992. doi:10.1016/0020-0190(92)90225-K

[MN02] C. Moore and M. Nilsson. Parallel quantum computation and quantum codes, SIAM Journal on Computing 31(3):799-815, 2002. doi:10.1137/S0097539799355053 arXiv:quant-ph/9808027.

[Mon80] B. Monien. On a subclass of pseudopolynomial problems, Mathematical Foundations of Computer Science (MFCS'80), Springer LNCS 88, pp. 414-425, 1980. doi:10.1007/BFb0022521

[Moo99] C. Moore. Quantum circuits: fanout, parity, and counting, ECCC TR99-032.

[Mor01] T. Morioka. Classification of search problems and their definability in bounded arithmetic, master's thesis, University of Toronto, 2001. Permalink ECCC TR01-082.

[MP75] D. E. Muller and F. P. Preparata. Bounds to complexities of networks for sorting and for switching, Journal of the ACM 22:195-201, 1975. doi:10.1145/321879.321882

[MP91] N. Megiddo and C. H. Papadimitriou. On total functions, existence theorems, and computational complexity, Theoretical Computer Science 81(2):317-324, 1991. doi:10.1016/0304-3975(91)90200-L

[MR95] R. Motwani and P. Raghavan. Randomized Algorithms, Cambridge University Press, 1995.

[MS02] K. Mulmuley and M. Sohoni. Geometric complexity theory I: An approach to the P vs. NP and related problems, SIAM Journal on Computing 31(2):496-526, 2002. doi:10.1137/S009753970038715X

[Muc56] A. A. Muchnik. On the unsolvability of the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk SSSR 108:194-197, 1956.

[MV99] P. B. Miltersen and N. V. Vinodchandran. Derandomizing Arthur-Merlin games using hitting sets, comput. complexity 14:256–279, 2005. doi:10.1007/s00037-005-0197-7 Originally appeared in FOCS 1999

[MVV87] K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion, Combinatorica 7:105–113, 1987. doi:10.1007/BF02579206 Originally appeared in STOC 1987 Author's website conference version

[MVW99] P. B. Miltersen, N. V. Vinodchandran, and O. Watanabe. Super-polynomial versus half-exponential circuit size in the exponential hierarchy, Proceedings of the 5th Annual Conference on Computing and Combinatorics (COCOON'99), pp. 210-220, Lecture Notes in Computer Science 1627, Springer-Verlag, 1999. doi:10.1007/3-540-48686-0_21

[MW05] C. Marriott and J. Watrous. Quantum Arthur-Merlin Games, Computational Complexity, 14(2):122-152, 2005. doi:10.1007/s00037-005-0194-x arXiv:cs/0506068.

[MW18] S. Menda and J. Watrous. Oracle separations for quantum statistical zero-knowledge, arXiv:1801.08967.

N

[NC00] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information, Cambridge University Press, 2000. doi:10.1017/CBO9780511976667

[NHK00] M. Nakanishi, K. Hamaguchi, and T. Kashiwabara. Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction, Proceedings of COCOON'2000 (Computing and Combinatorics), Springer LNCS 1858, pp. 467-476, 2000. doi:10.1007/3-540-44968-X_46

[Nie02] G. Niemann and J. R. Woinowski. The Growing Context-Sensitive Languages Are the Acyclic Context-Sensitive Languages, Developments in Language Theory. LNCS 2295, pp. 197-205. doi:10.1007/3-540-46011-X_16

[Nis02] T. Nishino. Mathematical models of quantum computation, New Gen. Comput. 20 (2002), no 4, 317-337. doi:10.1007/BF03037370

[Nis92] N. Nisan. RL &subseteq; SC, comput. complexity 4:1-11, 1994. doi:10.1007/BF01205052 Originally appeared in STOC 1992.

[Nis93] N. Nisan. On read-once vs. multiple access to randomness in logspace Theoretical Computer Science 107:135–144, 1993. 10.1016/0304-3975(93)90258-U Originally appeared in Structure in Complexity Theory Conference, 1990.

[NR97] M. Naor and O. Reingold. Number-theoretic constructions of efficient pseudorandom functions, Journal of the ACM, 51(2):231-262, 2004. doi:10.1145/972639.972643 Originally appeared in FOCS 1997.

[NR98] R. Niedermeier and P. Rossmanith. Unambiguous computations and locally definable acceptance types, Theoretical Computer Science 194:137-161, 1998. doi:10.1016/S0304-3975(97)00005-4

[NRR01] M. Naor, O. Reingold, and A. Rosen. Pseudo-random functions and factoring, SIAM J. Comput., 31(5):1383-1404, 2012. doi:S0097539701389257 ECCC TR01-064.

[NS05] A. Nickelsen and B. Schelm. Average-case computations - comparing AvgP, HP, and Nearly-P, Proceedings of IEEE Complexity'2005, pp. 235-242, 2005. doi:10.1109/CCC.2005.4

[NSW92] N. Nisan, E. Szemerédi, and A. Wigderson. Undirected connectivity in O(log1.5n) space, Proceedings of IEEE FOCS'92, pp. 24-29, 1992. doi:10.1109/SFCS.1992.267822

[NT95] N. Nisan and A. Ta-Shma. Symmetric logspace is closed under complement, Chicago J. Theoret. Comput. Sci., Article 1, 1995. doi:10.4086/cjtcs.1995.001 Originally appeared in STOC 1995, preprint ECCC TR94-003.

[NW94] N. Nisan and A. Wigderson. Hardness versus randomness, Journal of Computer and System Sciences 49:149-167, 1994. doi:10.1016/S0022-0000(05)80043-1 Author's webpage version

[NY03] H. Nishimura and T. Yamakami. Polynomial time quantum computation with advice, Inform. Proc. Lett., 90(4):195-204, 2004. doi:10.1016/j.ipl.2004.02.005 arXiv:quant-ph/0305100, ECCC TR03-059, 2003.

[NY03b] H. Nishimura and T. Yamakami. An algorithmic argument for query complexity lower bounds of advised quantum computation, MFCS, pp. 827–838, 2004. doi:10.1007/978-3-540-28629-5_65 arXiv:quant-ph/0312003

O

[Ogi94] M. Ogihara. On serializable languages, International Journal of Foundations of Computer Science 5(3-4):303-318, 1994. doi:10.1142/S0129054194000177

[OH93] M. Ogihara and L. Hemachandra. A complexity theory for feasible closure properties, Journal of Computer and System Sciences 46(3):295-325, 1993. doi:10.1016/0022-0000(93)90006-I

[Oka96] T. Okamoto. On relationships between statistical zero-knowledge proofs, Journal of Computer and System Sciences 60(1):47-108, 2000. doi:10.1006/jcss.1999.1664 Originally appeared in STOC 1996.

[OKS+94] P. Orponen, K.-I. Ko, U. Schöning, and O. Watanabe. Instance complexity, Journal of the ACM 41:96-121, 1994. doi:10.1145/174644.174648

[Ost91] R. Ostrovsky. One-way functions, hard on average problems and statistical zero-knowledge proofs, Proceedings of IEEE Complexity'91, pp. 51-59, 1991. doi:10.1109/SCT.1991.160253 Author's website version

[OW93] R. Ostrovsky and A. Wigderson. One-way functions are essential for non-trivial zero-knowledge, Proceedings of the 2nd Israel Symposium on Theory of Computing and Systems (ISTCS-93), 1993. doi:10.1109/ISTCS.1993.253489 Author's website version

P

[Pap83] C. H. Papadimitriou. Games against nature, J. Comput. Syst. Sci. 31(2):288-301, 1985. doi:10.1016/0022-0000(85)90045-5 Originally appeared in Proceedings of IEEE FOCS'83, pp. 446-450, 1983.

[Pap90] C. H. Papadimitriou. On graph-theoretic lemmata and complexity classes, Proceedings of IEEE FOCS'90, pp. 794-801, 1990. doi:10.1109/FSCS.1990.89602

[Pap94] C. H. Papadimitriou. Computational Complexity, Addison-Wesley, 1994.

[Pap94b] C. H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences 48(3):498-532, 1994. doi:10.1016/S0022-0000(05)80063-7

[Per07] K. Pervyshev. On heuristic time hierarchies, Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, 347-357, 2007.

[PM15] S. Piddock and A. Montanaro. The complexity of antiferromagnetic interactions and 2D lattices. arXiv:1506.04014, 2015.

[Pos44] E. L. Post. Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society 50:284-316, 1944. doi:10.1090/S0002-9904-1944-08111-1

[PP00] S. Parker and M. B. Plenio. Efficient factorization with a single pure qubit and log N mixed qubits, Physical Review Letters 85:3049, 2000. doi:10.1103/PhysRevLett.85.3049 arXiv:quant-ph/0001066.

[PPS+83] W. J. Paul, N. Pippenger, E. Szemerédi, and W. T. Trotter. On determinism versus nondeterminism and related problems, Proceedings of IEEE FOCS'83, pp. 429-438, 1983. doi:10.1109/SFCS.1983.39

[PPS14] P. Papakonstantinou, D. Scheder, and H. Song. Overlays and limited memory communication, Proceedings of IEEE CCC'14, pp. 298-308, 2014. doi:10.1109/CCC.2014.37

[Pra74] V. R. Pratt. The power of negative thinking in multiplying Boolean matrices, doi:10.1137/0204027 Originally appeared in STOC '74: Proceedings of the sixth annual ACM Symposium on Theory of Computing, 80-83, 1974.

[Pra75] V. R. Pratt. Every prime has a succinct certificate, SIAM Journal on Computing, 4:214-220, 1975. doi:10.1137/0204018

[PS86] R. Paturi and J. Simon. Probabilistic communication complexity, Journal of Computer and System Sciences, 33(1):106-123, 1986. doi:10.1016/0022-0000(86)90046-2 Originally appeared in FOCS '84

[PV04] A. Pavan and N. V. Vinodchandran. Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility ECCC TR04-053.

[PY84] C. H. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity), Journal of Computer and System Sciences 28:244-259, 1984. doi:10.1016/0022-0000(84)90068-0

[PY88] C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes, J. Comput. Syst. Sci. 43(3): 425-440 (1991) doi:10.1016/0022-0000(91)90023-X Originally appeared in Proceedings of ACM STOC'88, pp. 229-234, 1988.

[PY96] C. H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the VC dimension, Journal of Computer and System Sciences 53(2):161-170, 1996. doi:10.1006/jcss.1996.0058

[PZ83] C. H. Papadimitriou and S. Zachos. Two remarks on the power of counting, Proceedings of the 6th GI Conference in Theoretical Computer Science, Lecture Notes in Computer Science Vol. 145, Springer-Verlag, pp. 269-276, 1983. doi:10.1007/BFb0009651

R

[RA00] K. Reinhardt and E. Allender. Making nondeterminism unambiguous, SIAM Journal on Computing 29:1118-1131, 2000. ECCC TR97-014, DIMACS TR 97-46. doi:10.1137/S0097539798339041 Originally appeared in FOCS 1997, pp. 244-253.

[Rab60] M. O. Rabin. Degree of difficulty of computing a function and a partial ordering of recursive sets, Tech Report No. 2, Hebrew University, 1960.

[Rac82] C. Rackoff. Relativized questions involving probabilistic algorithms, Journal of the ACM 29(1):261-268, 1982.

[Raz05] R. Raz. Quantum information and the PCP theorem, Proc. IEEE FOCS, 2005. arXiv:quant-ph/0504075, ECCC TR05-038.

[Raz85] A. A. Razborov. Lower bounds on the monotone complexity of some Boolean functions, Dokl. Akad. Nauk SSSR 281(4):798-801, 1985. English translation in Soviet Math. Dokl. 31:354-357, 1985.

[Raz85b] A. A. Razborov. A lower bound on the monotone network complexity of the logical permanent, Mat. Zametky 37(6):887-900, 1985. English translation in Russian Mathematical Notes 37:485-493, 1985.

[Raz87] A. A. Razborov. Lower bounds for the size of circuits of bounded depth with basis {&,}, Mathematicheskie Zametki 41(4):598-607, 1987. English translation in Math. Notes. USSR 41(4):333-338, 1987.

[Raz92] A. A. Razborov. On the distributional complexity of disjointness, Theoretical Computer Science 106(2):385-390, 1992.

[Raz94] A. A. Razborov. On provably disjoint NP-pairs, ECCC TR94-006, 1994.

[Reg02] K. Regan. Understanding the Mulmuley-Sohoni approach to P vs. NP, Bulletin of the EATCS 78, October 2002. http://people.cs.uchicago.edu/~fortnow/beatcs/column78.pdf.

[Rei04] O. Reingold. Undirected st-connectivity in log-space, ECCC TR04-094, 2004.

[RR95] K. Regan and J. Royer. On Closure Properties of Bounded two-Sided Error Complexity Classes, Math. Systems Theory, 28 (1995) 229-243. ftp://ftp.cis.syr.edu/users/royer/coinflips.ps

[RR97] A. A. Razborov and S. Rudich. Natural proofs, Journal of Computer and System Sciences 55(1):24-35, 1997. ECCC TR94-010.

[RS98] A. Russell and R. Sundaram. Symmetric alternation captures BPP, Computational Complexity 7(2):152-162, 1998.

[RS10] A. Razborov and A. Sherstov. The sign-rank of AC0, SIAM Journal on Computing 39(5):1833-1855, 2010.

[RST15] B. Rossman and Rocco Servedio and Li-Yang Tan. An average-case depth hierarchy theorem for Boolean circuits, Foundations of Computer Science (FOCS), 2015.

[RG20] V. Rozhoň and M. Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization, Symposium on Theory of Computing (STOC), 2020.

[RT92] J. Reif and S. Tate. On Threshold Circuits and Polynomial Computation, SIAM J. Comput., 21(5) 896-908, 1992.

[RT18] R. Raz and A. Tal. Oracle Separation of BQP and PH, ECCC TR18-107, 2018.

[RTV05] O. Reingold and L. Trevisan and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem, ECCC TR05-022, 2004.

[Rub88] R. Rubinstein. Structural Complexity Classes of Sparse Sets: Intractability, Data Compression, and Printability, PhD Thesis, Northeastern University (Boston, MA), 1988.

[Rud97] S. Rudich. Super-bits, demi-bits, and NP/qpoly-natural proofs, RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science, Springer-Verlag, 1997.

[Rus85] D. A. Russo. Structural Properties of Complexity Classes. PhD thesis, UC Santa Barbara, 1985.

[RUV12] B. W. Reichardt, F. Unger, and U. Vazirani. A classical leash for a quantum system: Command of quantum systems via rigidity of CHSH games, Nature 496:456–460, 2013.

[Ruz81] W. L. Ruzzo. On uniform circuit complexity, Journal of Computer and System Sciences 22(3):365-383, 1971.

[RV97] K. Regan and H. Vollmer. "Gap-languages and log-time complexity classes", Theoretical Computer Science 188(1–2):101–116, 1997.

[RW01] S. Reith and K. Wagner. On Boolean lowness and Boolean highness, Theoretical Computer Science 261(2):305-321, 2001.

S

[San07] R. Santhanam. Circuit lower bounds for Merlin-Arthur classes, Electronic Colloquium on Computational Complexity, Report TR07-005.

[Sav70] W. Savitch. Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4(2):177-192, 1970.

[Sch02a] M. Schaefer and C. Umans. Completeness in the Polynomial-Time Hierarchy: A Compendium, Sigact News September, 2002.

[Sch02b] M. Schaefer and C. Umans. Completeness in the Polynomial-Time Hierarchy: Part II, Sigact News December, 2002.

[Sch03] P. Schnoebelen. Oracle circuits for branching-time model checking, Proceedings of ICALP 2003, pp. 790-801, 2003.

[Sch78] C. P. Schnorr. Satisfiability Is Quasilinear Complete in NQL, Journal of the ACM 25(1):136-145, 1978.

[Sch83] U. Schöning. A low and a high hierarchy within NP, Journal of Computer and System Sciences 27:14-28, 1983. DOI

[Sch86] U. Schöning. Complete Sets and Closeness to Complexity Classes, Mathematical Systems Theory 19:29-41, 1986. DOI:10.1007/BF01704904

[Sch16] Sylvain Schmitz. Complexity Hierarchies Beyond Elementary, ACM Transactions on Computation Theory (TOCT), Volume 8, Issue 1, February 2016.

[Sel79] A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities in NP, Mathematical Systems Theory 13(1):55-65, 1979.

[SES05] E. Allender, S. Datta, and S. Roy. The directed planar reachability problem, Proceedings of FSTTCS, #1373 in Computer Science

[SF98] H. T. Siegelmann and S. Fishman. Analog computation with dynamical systems, Physica 120D, p. 214, 1998.

[SFM78] J. Seiferas, M. Fischer, and A. Meyer. Separating nondeterministic time complexity classes, Journal of the ACM 25:146-167, 1978.

[Sha10] M. Schaefer. Complexity of some geometric and topological problems, Graph Drawing, LNCS 5849, Springer-Verlag, 334–344, 2010.

[Sha90] A. Shamir. IP=PSPACE, Proceedings of IEEE FOCS'90, pp. 11-15, 1990.

[She59] J. C. Shepherdson. The reduction of two-way automata to one-way automata, IBM Journal of Research and Development, 3:198-200, 1959.

[She08] A. A. Sherstov. Separating AC0 from depth-2 majority circuits, Computational Complexity, 17(2):149-178, 2008. http://www.cs.utexas.edu/~sherstov/publications/pdf/cc08hsmat.pdf

[Shi03] Y. Shi. Quantum and classical tradeoffs, arXiv:quant-ph/0312213, ECCC TR04-023, 2003.

[Sho97] P. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26(5):1484-1509, 1997. arXiv:quant-ph/9508027.

[Sho99] R. A. Shore. The recursively enumerable degrees, Handbook of Recursion Theory (E. Griffor, ed.), pp. 169-197, North-Holland, Amsterdam, 1999.

[Sip82] M. Sipser. On relativization and the existence of complete sets, Proceedings of ICALP'82, Springer-Verlag Lecture Notes in Computer Science volume 140, pp. 523-531, 1982.

[Sip92] M. Sipser. The history and status of the P versus NP question, Proceedings of ACM STOC'92, pp. 603-618, 1992.

[SJ08] Peter W. Shor and Stephen P. Jordan. Estimating Jones polynomials is a complete problem for one clean qubit, Quantum Information & Computation, Volume 8, Issue 8, September 2008, pages 681-714.

[SM02] L. J. Stockmeyer and A. R. Meyer. Cosmological lower bound on the circuit complexity of a small problem in logic, Journal of the ACM 49(6):753-784, 2002. http://theory.lcs.mit.edu/~meyer/stock-circuit-jacm.pdf.

[SM03] R. Santhanam and D. van Melkebeek. Holographic proofs and derandomization, Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 269-283.

[Smo87] R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of ACM STOC'87, pp. 77-82, 1987.

[SP98] U. Schöning and R. Pruim. Gems of Theoretical Computer Science, Springer-Verlag, 1998.

[Spa02] R. Špalek. Quantum circuits with unbounded fan-out, arXiv:quant-ph/0208043, 2002.

[SS04] A. Selman and S. Sengupta. Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Proceedings of IEEE Complexity 2004, pp. 82-90, 2004. ECCC TR04-007.

[SS77] R. Solovay and V. Strassen. A fast Monte-Carlo test for primality, SIAM Journal on Computing, 6:84-86, 1977.

[Sto76] L. J. Stockmeyer. The polynomial hierarchy, Theoretical Computer Science 3:1-22, 1976.

[Sto85] L. J. Stockmeyer. On approximation algorithms for #P, SIAM Journal on Computing 14:849-861, 1985.

[STT05] H. Spakowski, M. Thakur, and R. Tripathi. Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties, Inform. and Comput. 200 (2005), no. 1, 1--34. http://web.umr.edu/~thakurk/publications/quantum-j.pdf

[SU05] R. Shaltiel and C. Umans. Pseudorandomness for approximate counting and sampling, Proceedings of IEEE Complexity'2005, pp. 212-226, 2005. http://www.cs.haifa.ac.il/~ronen/online_papers/derand-ccc-final.ps.

[Sub94] A. Subramanian. A New Approach to Stable Matching Problems, SIAM Journal on Computing 23(4), 671-701, 1994.

[Sud78] I. Sudborough. On the tape complexity of deterministic context-free languages, Journal of the ACM 25(3):405-414, 1978.

[SV97] A. Sahai and S. Vadhan. A complete promise problem for statistical zero-knowledge, Proceedings of IEEE FOCS'97. http://www.eecs.harvard.edu/~salil/papers/complete-abs.html.

[SZ95] M. Saks and S. Zhou. RSPACE(s) is contained in DSPACE(s3/2), Proceedings of IEEE FOCS'95, pp. 344-353, 1995.

[Sze87] R. Szelepcsényi. The method of forcing for nondeterministic automata, Bulletin of the EATCS 33:96-100, 1987.

[Szep94] A. Szepietowski. Turing Machines With Sublogarithmic Space, Lecture Notes in Computer Science, volume 843.

T

[Tak12] Y. Takahashi. and T. Seiichiro Collapse of the hierarchy of constant-depth exact quantum circuits Computational complexity, 25.4:849-881, 2016. doi:10.1109/CCC.2013.25


[Tan07] T. Tantau. Logspace Optimization Problems and Their Approximability Properties, Theory of Computing Systems, 41:327-350, 2007. doi:10.1007/s00224-007-2011-1 ECCC TR03-077

[Tar88] E. Tardos. The gap between monotone and non-monotone circuit complexity is exponential, Combinatorica, 8:141-142, 1988. doi:10.1007/BF02122563 Author's webpage version

[Tar89] G. Tardos. Query complexity, or why is it difficult to separate NPA intersect coNPA from PA by random oracles A, Combinatorica, 9:385-392, 1989. doi:10.1007/BF02125350

[Tha98] J. S. Thathachar. On Separating the Read-k-Times Branching Program Hierarchy, Proceedings of the 30th ACM Symposium on Theory of Computing, pp. 653-662, 1998. ECCC TR98-02, DOI:10.1145/276698.276881.

[Tod89] S. Toda. On the computational power of PP and (+)P, Proceedings of IEEE FOCS'89, pp. 514-519, 1989. doi:10.1109/SFCS.1989.63527

[Tod91] S. Toda. Counting problems computationally equivalent to the determinant, manuscript, 1991.

[Tor00] J. Torán. On the hardness of graph isomorphism, Proceedings of IEEE FOCS'2000, pp. 180-186, 2000. doi:10.1109/SFCS.2000.892080

[Tor88] J. Torán. Structural Properties of the Counting Hierarchies, Ph.D Thesis, 1988. http://hdl.handle.net/2117/189084

[Tor90] J. Torán. Counting the number of solutions, Proceedings of 15th Conference on Mathematical Foundations of Computer Science (MFCS), pp. 121-135, Springer-Verlag Lecture Notes in Computer Science 452, 1990. doi:10.1007/BFb0029600

[Tor91] J. Torán. Complexity classes defined by counting quantifiers, Journal of the ACM 38:753-774, 1991. doi:10.1145/116825.116858

[Tur36] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society 2(42):230-265, 1936; 2(43):544-546, 1937. doi:10.1112/plms/s2-42.1.230

[TV02] L. Trevisan and S. Vadhan. Pseudorandomness and average-case complexity via uniform reductions, computational complexity 16:331-364, 2007. doi:10.1007/s00037-007-0233-x Originally appeared in CCC 2002. Author's webpage version

U

[Uma98] C. Umans. The minimum equivalent DNF problem and shortest implicants, J. Comput. Syst. Sci. 63(4):597-611, 2001. doi:10.1006/jcss.2001.1775 Originally appeared in Proceedings of IEEE FOCS'98, pp. 556-563, 1998. doi:10.1109/SFCS.1998.743506

V

[Vad06] S. Vadhan. An Unconditional Study of Computational Zero Knowledge, SIAM J. Comput. 36(4):1160-1214, 2006. doi:10.1137/S0097539705447207 Originally appeared in FOCS 2004. Preprint ECCC TR06-056.

[Val03] L. G. Valiant. Three problems in computer science, Journal of the ACM 50(1):96-99, 2003. doi:10.1145/602382.602410

[Val76] L. G. Valiant. Relative complexity of checking and evaluating, Information Processing Letters, 5:20-23, 1976. doi:10.1016/0020-0190(76)90097-1

[Val79] L. G. Valiant. The complexity of computing the permanent, Theoretical Computer Science, 8:189-201, 1979. doi:10.1016/0304-3975(79)90044-6

[Val79b] L. G. Valiant. Completeness classes in algebra, Proceedings of ACM STOC'79, pp. 249-261, 1979. doi:10.1145/800135.804419

[Var82] M. Vardi. Complexity of relational query languages, Proceedings of ACM STOC'82, pp. 137-146, 1982. doi:10.1145/800070.802186 Author's website version

[Ven91] H. Venkateswaran. Properties that characterize LOGCFL, Journal of Computer and System Sciences 43(2):380-404, 1991. doi:10.1016/0022-0000(91)90020-6 Originally appeared in STOC 1987

[Ver92] N. K. Vereshchagin. On the power of PP, Proceedings of IEEE Complexity'92, pp. 138-143, 1992. doi:10.1109/SCT.1992.215389

[Ver95] N. K. Vereshchagin. Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems, Izvestiya Mathematics 59(6):1103-1122, 1995. doi:10.1070/IM1995v059n06ABEH000050

[Vid03] G. Vidal. Efficient classical simulation of slightly entangled quantum computations, Physical Review Letters 91:147902, 2003. arXiv:quant-ph/0301063. doi:10.1103/PhysRevLett.91.147902

[Vin91] V. Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits, Proc. of the Sixth Annual Structure in Complexity Theory Conference, pp. 270-284, 1991. doi:10.1109/SCT.1991.160269

[Vin04] N. V. Vinodchandran. Counting complexity of solvable group problems, SIAM Journal on Computing 33(4):852-869, 2004, doi:10.1137/S0097539703420651 Author's website version.

[Vin04b] N. V. Vinodchandran. A note on the circuit complexity of PP, Theoretical Computer Science 347(1-2):415-418, 2005. doi:10.1016/j.tcs.2005.07.032 Preprint ECCC TR04-056, 2004.

[Vol20] I. Volkovich. The untold story of SBP, Proceedings Proceedings of the 15th International Computer Science Symposium in Russia (CSR), pp. 393-405, 2020. doi:10.1007/978-3-030-50026-9_29

[VSBR83] L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors, SIAM Journal on Computing 12(4):641-644, 1983. doi:10.1137/0212043 Originally appeared in MFCS 1981

[VV85] U. V. Vazirani and V. V. Vazirani. Random polynomial time equals slightly-random polynomial time, Proceedings of IEEE FOCS'85, pp. 417-428, 1985. doi:10.1109/SFCS.1985.45

[VV86] L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions, Theoretical Computer Science 47(3):85-93, 1986. doi:10.1016/0304-3975(86)90135-0 Originally appeared in STOC 1985.

[Vya03] M. Vyalyi. QMA=PP implies that PP contains PH, ECCC TR03-021, 2003.

W

[Wag86] K. W. Wagner. The complexity of combinatorial problems with succinct input representation, Acta Informatica 23:325-356, 1986. doi:10.1007/BF00289117

[Wag90] K. W. Wagner. Bounded query classes, SIAM J. Comput. 19(5): 833-846 (1990) doi:10.1137/0219058 Originally appeared in Proceedings of IEEE Complexity'88, pp. 260-277, 1988.

[Wan94] E. Wanke. Bounded Tree-Width and LOGCFL. J. Algorithms 16(3):470-491. doi:10.1006/jagm.1994.1022

[WW85] G. Wechsung. On the Boolean closure of NP, Proceedings of the International Conference on Fundamentals of Computation Theory, LNCS volume 199, Springer-Verlag, pp. 485-493. doi:10.1007/BFb0028832

[Wat00] J. Watrous. Succinct quantum proofs for properties of finite groups, Proceedings of IEEE FOCS'2000, pp. 537-546, 2000. arXiv:cs.CC/0009002. doi:10.1109/SFCS.2000.892141

[Wat02] J. Watrous. Limits on the power of quantum statistical zero-knowledge, to appear in Proceedings of IEEE FOCS'2002. arXiv:quant-ph/0202111. doi:10.1109/SFCS.2002.1181970

[Wat09] J. Watrous. Quantum Computational Complexity, Encyclopedia of Complexity and Systems Science, Springer, pp. 7174-7201, 2009. arXiv:quant-ph/0804.3401. doi:10.1007/978-0-387-30440-3_428

[Wat87] O. Watanabe. Comparison of polynomial time completeness notions, Theoretical Computer Science 53:249-265, 1987. doi:10.1016/0304-3975(87)90132-0

[Wat99] J. Watrous. PSPACE has constant-round quantum interactive proof systems, Theoret. Comput. Sci 292(30:575-588, 2003. Originally appeared in Proceedings of IEEE FOCS'99, pp. 112-119, 1999. arXiv:cs.CC/9901015. doi:10.1016/S0304-3975(01)00375-9

[Wat99b] J. Watrous. Space-bounded quantum complexity, Journal of Computer and System Sciences 59(2):281-326, 1999. doi:10.1006/jcss.1999.1655 Author's website version.

[Wat15] T. Watson. The complexity of deciding statistical properties of samplable distributions, Theory of Computing, 11:1-34, 2015. doi:10.4086/toc.2015.v011a001

[Weg87] I. Wegener. The Complexity of Boolean Functions, New York: Wiley 1987. Full book on ECCC

[Weg88] I. Wegener. On the Complexity of Branching Programs and Decision Trees for Clique Functions, Journal of the ACM 35(2):461-471, 1988. doi:10.1145/42282.46161.

[Weh06] S. Wehner. Entanglement in interactive proof systems with binary answers, In Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, volume 3884 of Lecture Notes in Computer Science, pages 162–171. Springer, 2006 doi:10.1007/11672142_12

[Wig06] A. Wigderson P, NP, and mathematics--a computational complexity perspective, 2006 mimeo. http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf.

[Wil85] C. Wilson. Relativized circuit complexity, Journal of Computer and System Sciences 31:169-181, 1985. doi:10.1016/0022-0000(85)90040-6

[Wil14] R. Williams. Non-uniform ACC circuit lower bounds, J. ACM 61(1):2:1-2:32, 2014. doi:10.1145/2559903 Originally appeared in Proceedings of IEEE Conference on Computational Complexity 2011. Author's website version.

[Wol94] M. J. Wolf. Nondeterministic circuits, space complexity and quasigroups, Theoretical Computer Science 125:295–313, 1994. doi:10.1016/0304-3975(92)00014-I

[Wu22] X. Wu. A stochastic calculus approach to the oracle separation of BQP and PH, Theory of Computing 18(17):1-11, 2022. doi:10.4086/toc.2022.v018a017

[WKST19] A. B. Watts, R. Kothari, L. Schaeffer, and A. Tal. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. STOC doi:10.1145/3313276.3316404, 2010.

Y

[Yap83] C. Yap. Some consequences of non-uniform conditions on uniform classes, Theoretical Computer Science, 26, pp. 287-300, 1983. doi:10.1016/0304-3975(83)90020-8

[Yam99] T. Yamakami. Polynomial time samplable distributions, J. Complexity 15 (1999), no. 4, 557-574. doi:10.1006/jcom.1999.0523 ECCC TR95-039.

[Yan81] M. Yannakakis. Algorithms for acyclic database schemas, Proceedings of VLDB (Very Large Databases), 1981.

[Yan91] M. Yannakakis. Expressing combinatorial optimization problems by linear programs, Journal of Computer and System Sciences, 43(3):441-466, 1991. doi:10.1016/0022-0000(91)90024-Y Originally appeared in STOC 1988

[Yao85] A. C.-C. Yao. Separating the polynomial hierarchy by oracles, Proceedings of IEEE FOCS'85, pp. 1-10, 1985. doi:10.1109/SFCS.1985.49

[Yao89] A. C.-C. Yao. Circuits and local computation, Proceedings of ACM STOC'89, pp. 186-196, 1989. doi:10.1145/73007.73025

[Yao90] A. C.-C. Yao. On ACC and threshold circuits, Proceedings of IEEE FOCS'90, pp. 619-627, 1990. doi:10.1109/FSCS.1990.89583

[Yao90b] A. C.-C. Yao. Coherent functions and program checkers, Proceedings of ACM STOC'90, 1990. doi:10.1145/100216.100226

[Yao93] A. C.-C. Yao. Quantum circuit complexity, Proceedings of IEEE FOCS'93, pp. 352-361, 1993. doi:10.1109/SFCS.1993.366852

[Yes83] Y. Yesha. On certain polynomial-time truth-table reducibilities of complete sets to sparse sets, SIAM Journal on Computing, 12(3):411-425, 1983. DOI:10.1137/0212027

[Yir24] J. Yirka. Even quantum advice is unlikely to solve PP, arXiv:2403.09994 [cs.CC], 2024.

Z

[Zac88] S. Zachos. Probabilistic quantifiers and games, Journal of Computer and System Sciences 36(3):433-451, 1988. doi:10.1016/0022-0000(88)90037-2

[ZH86] S. Zachos and H. Heller. A decisive characterization of BPP. Information and Control, 69(1–3):125–135, 1986. doi:10.1016/S0019-9958(86)80044-4

[ZKT85] V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich. Graph isomorphism problem, Journal of Mathematical Sciences, 29(4):1426-1481, 1985. doi:10.1007%2FBF02104746.

[Zuc91] D. Zuckerman. Simulating BPP using a general weak random source, Algorithmica 16 (1996), no. 4-5, 367--391 Author's webpage 1995 version. doi:10.1007/BF01940870 Originally appeared in FOCS 1991

Retrieved from "https://complexityzoo.net/index.php?title=Complexity_Zoo_References&oldid=7548"