{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T16:35:39Z","timestamp":1791563739338,"version":"4.3.4"},"publisher-location":"Cham","reference-count":246,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319321608","type":"print"},{"value":"9783319321622","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-32162-2_1","type":"book-chapter","created":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T10:20:27Z","timestamp":1467714027000},"page":"1-122","source":"Crossref","is-referenced-by-count":18,"title":["$$P\\mathop{ =}\\limits^{?}NP$$"],"prefix":"10.1007","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,7,6]]},"reference":[{"key":"1_CR1","unstructured":"S. Aaronson. Is P versus NP formally independent? Bulletin of the EATCS, (81), October 2003."},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"S. Aaronson. Multilinear formulas and skepticism of quantum computing. In Proc. ACM STOC, pages 118\u2013127, 2004. quant-ph\/0311039, www.scottaaronson.com\/papers\/mlinsiam.pdf .","DOI":"10.1145\/1007352.1007378"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"S. Aaronson. NP-complete problems and physical reality. SIGACT News, March 2005. quant-ph\/0502072.","DOI":"10.1145\/1052796.1052804"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"S. Aaronson. Oracles are subtle but not malicious. In Proc. Conference on Computational Complexity, pages 340\u2013354, 2006. ECCC TR05-040.","DOI":"10.1109\/CCC.2006.32"},{"key":"1_CR5","volume-title":"Arithmetic natural proofs theory is sought","author":"S. Aaronson","year":"2008","unstructured":"S. Aaronson. Arithmetic natural proofs theory is sought, 2008. www.scottaaronson.com\/blog\/?p=336 ."},{"key":"1_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511979309","volume-title":"Quantum Computing Since Democritus","author":"S. Aaronson","year":"2013","unstructured":"S. Aaronson. Quantum Computing Since Democritus. Cambridge University Press, 2013."},{"key":"1_CR7","unstructured":"S. Aaronson. The scientific case for P \u2260 NP, 2014. www.scottaaronson.com\/blog\/?p=1720 ."},{"key":"1_CR8","unstructured":"S. Aaronson et al. The Complexity Zoo. www.complexityzoo.com ."},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"S. Aaronson, R. Impagliazzo, and D. Moshkovitz. AM with multiple Merlins. In Proc. Conference on Computational Complexity, pages 44\u201355, 2014. arXiv:1401.6848.","DOI":"10.1109\/CCC.2014.13"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"S. Aaronson and A. Wigderson. Algebrization: a new barrier in complexity theory. ACM Trans. on Computation Theory, 1(1), 2009. Earlier version in Proc. ACM STOC\u20192008.","DOI":"10.1145\/1490270.1490272"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"L. Adleman. Two theorems on random polynomial time. In Proc. IEEE FOCS, pages 75\u201383, 1978.","DOI":"10.1109\/SFCS.1978.37"},{"issue":"5","key":"1_CR12","doi-asserted-by":"crossref","first-page":"1524","DOI":"10.1137\/S0097539795293639","volume":"26","author":"L. Adleman","year":"1997","unstructured":"L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524\u20131540, 1997.","journal-title":"SIAM J. Comput."},{"key":"1_CR13","unstructured":"M. Agrawal. Determinant versus permanent. In Proceedings of the International Congress of Mathematicians, 2006."},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Annals of Mathematics, 160(2):781\u2013793, 2004. Preprint released in 2002.","DOI":"10.4007\/annals.2004.160.781"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"M. Agrawal and V. Vinay. Arithmetic circuits: a chasm at depth four. In Proc. IEEE FOCS, pages 67\u201375, 2008.","DOI":"10.1109\/FOCS.2008.32"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"M. Ajtai. $$\\Sigma _{1}^{1}$$ -formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1\u201348, 1983.","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"1_CR17","unstructured":"M. Ajtai. A non-linear time lower bound for Boolean branching programs. Theory of Computing, 1(1):149\u2013176, 2005. Earlier version in Proc. IEEE FOCS\u20191999, pp. 60\u201370."},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"B. Alexeev, M. A. Forbes, and J. Tsimerman. Tensor rank: some lower and upper bounds. In Proc. Conference on Computational Complexity, pages 283\u2013291, 2011.","DOI":"10.1109\/CCC.2011.28"},{"key":"1_CR19","first-page":"19","volume":"7","author":"E. Allender","year":"1999","unstructured":"E. Allender. The permanent requires large uniform threshold circuits. Chicago Journal of Theoretical Computer Science, 7:19, 1999.","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"E. Allender. Cracks in the defenses: scouting out approaches on circuit lower bounds. In Computer Science in Russia, pages 3\u201310, 2008.","DOI":"10.1007\/978-3-540-79709-8_2"},{"key":"1_CR21","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0065-2458(09)01204-2","volume":"77","author":"E. Allender","year":"2009","unstructured":"E. Allender. A status report on the P versus NP question. Advances in Computers, 77:117\u2013147, 2009.","journal-title":"Advances in Computers"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"E. Allender and V. Gore. On strong separations from AC 0. In Fundamentals of Computation Theory, pages 1\u201315. Springer Berlin Heidelberg, 1991.","DOI":"10.1007\/3-540-54458-5_44"},{"issue":"5","key":"1_CR23","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1137\/S0097539792233907","volume":"23","author":"E. Allender","year":"1994","unstructured":"E. Allender and V. Gore. A uniform circuit lower bound for the permanent. SIAM J. Comput., 23(5):1026\u20131049, 1994.","journal-title":"SIAM J. Comput."},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"E. Allender and M. Kouck\u00fd. Amplifying lower bounds by means of self-reducibility. J. of the ACM, 57(3):1\u201336, 2010. Earlier version in Proc. IEEE Complexity\u20192008, pp. 31\u201340.","DOI":"10.1145\/1706591.1706594"},{"issue":"1","key":"1_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon and R. B. Boppana. The monotone circuit complexity of Boolean functions. Combinatorica, 7(1):1\u201322, 1987.","journal-title":"Combinatorica"},{"key":"1_CR26","first-page":"63","volume":"42","author":"A. E. Andreev","year":"1987","unstructured":"A. E. Andreev. On a method for obtaining more than quadratic effective lower bounds for the complexity of \u03c0-schemes. Moscow Univ. Math. Bull., 42:63\u201366, 1987. In Russian.","journal-title":"Moscow Univ. Math. Bull."},{"key":"1_CR27","unstructured":"S. Arora and B. Barak. Complexity Theory: A Modern Approach. Cambridge University Press, 2009. Online draft at www.cs.princeton.edu\/theory\/complexity\/ ."},{"key":"1_CR28","volume-title":"Relativizing versus nonrelativizing techniques: the role of local checkability","author":"S. Arora","year":"1992","unstructured":"S. Arora, R. Impagliazzo, and U. Vazirani. Relativizing versus nonrelativizing techniques: the role of local checkability. Manuscript, 1992."},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. J. of the ACM, 45(3):501\u2013555, 1998. Earlier version in Proc. IEEE FOCS\u20191992, pp. 14\u201323.","DOI":"10.1145\/278298.278306"},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. J. of the ACM, 45(1):70\u2013122, 1998. Earlier version in Proc. IEEE FOCS\u20191992, pp. 2\u201313.","DOI":"10.1145\/273865.273901"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"A. Atserias. Distinguishing SAT from polynomial-size circuits, through black-box queries. In Proc. Conference on Computational Complexity, pages 88\u201395, 2006.","DOI":"10.1109\/CCC.2006.17"},{"key":"1_CR32","doi-asserted-by":"crossref","unstructured":"L. Babai. Graph isomorphism in quasipolynomial time. arXiv:1512.03547, 2015.","DOI":"10.1145\/2897518.2897542"},{"key":"1_CR33","doi-asserted-by":"crossref","unstructured":"A. Backurs and P. Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proc. ACM STOC, pages 51\u201358, 2015.","DOI":"10.1145\/2746539.2746612"},{"key":"1_CR34","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question. SIAM J. Comput., 4:431\u2013442, 1975.","journal-title":"SIAM J. Comput."},{"key":"1_CR35","doi-asserted-by":"crossref","unstructured":"A. Banerjee, C. Peikert, and A. Rosen. Pseudorandom functions and lattices. In Proc. of EUROCRYPT, pages 719\u2013737, 2012.","DOI":"10.1007\/978-3-642-29011-4_42"},{"key":"1_CR36","unstructured":"P. Beame and T. Pitassi. Propositional proof complexity: past, present, and future. Current Trends in Theoretical Computer Science, pages 42\u201370, 2001."},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"P. Beame, M. E. Saks, X. Sun, and E. Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. of the ACM, 50(2):154\u2013195, 2003. Earlier version in Proc. IEEE FOCS\u20192000, pp. 169\u2013179.","DOI":"10.1145\/636865.636867"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"R. Beigel and J. Tarui. On ACC. Computational Complexity, 4:350\u2013366, 1994. Earlier version in Proc. IEEE FOCS\u20191991, pp. 783\u2013792.","DOI":"10.1007\/BF01263423"},{"key":"1_CR39","unstructured":"S. Ben-David and S. Halevi. On the independence of P versus NP. Technical Report TR714, Technion, 1992."},{"key":"1_CR40","doi-asserted-by":"crossref","unstructured":"C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510\u20131523, 1997. quant-ph\/9701001.","DOI":"10.1137\/S0097539796300933"},{"issue":"1","key":"1_CR41","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. H. Bennett","year":"1981","unstructured":"C. H. Bennett and J. Gill. Relative to a random oracle A, P A \u2260 NP A \u2260 coNP A with probability 1. SIAM J. Comput., 10(1):96\u2013113, 1981.","journal-title":"SIAM J. Comput."},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411\u20131473, 1997. Earlier version in Proc. ACM STOC\u20191993.","DOI":"10.1137\/S0097539796300921"},{"key":"1_CR43","doi-asserted-by":"crossref","unstructured":"D. Bini. Relations between exact and approximate bilinear algorithms. applications. Calcolo, 17(1):87\u201397, 1980.","DOI":"10.1007\/BF02575865"},{"issue":"4","key":"1_CR44","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1137\/0209053","volume":"9","author":"D. Bini","year":"1980","unstructured":"D. Bini, G. Lotti, and F. Romani. Approximate solutions for the bilinear form computational problem. SIAM J. Comput., 9(4):692\u2013697, 1980.","journal-title":"SIAM J. Comput."},{"key":"1_CR45","doi-asserted-by":"crossref","unstructured":"J. Blasiak, K. Mulmuley, and M. Sohoni. Geometric complexity theory IV: nonstandard quantum group for the Kronecker problem, volume 235 of Memoirs of the American Mathematical Society. 2015. arXiv:cs.CC\/0703110.","DOI":"10.1090\/memo\/1109"},{"key":"1_CR46","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1997","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1997."},{"key":"1_CR47","doi-asserted-by":"crossref","unstructured":"A. Bogdanov and L. Trevisan. Average-case complexity. Foundations and Trends in Theoretical Computer Science, 2(1), 2006. ECCC TR06-073.","DOI":"10.1561\/0400000004"},{"key":"1_CR48","doi-asserted-by":"crossref","unstructured":"A. D. Bookatz. QMA-complete problems. Quantum Information and Computation, 14(5-6):361\u2013383, 2014. arXiv:1212.6312.","DOI":"10.26421\/QIC14.5-6-1"},{"key":"1_CR49","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. B. Boppana","year":"1987","unstructured":"R. B. Boppana, J. H\u00e5stad, and S. Zachos. Does co-NP have short interactive proofs? Inform. Proc. Lett., 25:127\u2013132, 1987.","journal-title":"Inform. Proc. Lett."},{"issue":"2","key":"1_CR50","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.20057","volume":"27","author":"A. Braunstein","year":"2005","unstructured":"A. Braunstein, M. M\u00e9zard, and R. Zecchina. Survey propagation: An algorithm for satisfiability. Random Structures and Algorithms, 27(2):201\u2013226, 2005.","journal-title":"Random Structures and Algorithms"},{"key":"1_CR51","doi-asserted-by":"crossref","unstructured":"M. Braverman. Poly-logarithmic independence fools AC 0 circuits. In Proc. Conference on Computational Complexity, pages 3\u20138, 2009. ECCC TR09-011.","DOI":"10.1109\/CCC.2009.35"},{"key":"1_CR52","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. P. Brent","year":"1974","unstructured":"R. P. Brent. The parallel evaluation of general arithmetic expressions. J. of the ACM, 21:201\u2013206, 1974.","journal-title":"J. of the ACM"},{"key":"1_CR53","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, R. Cleve, and W. Eberly. Size-depth tradeoffs for algebraic formulae. SIAM J. Comput., 24(4):682\u2013705, 1995. Earlier version in Proc. IEEE FOCS\u20191991, pp. 334\u2013341.","DOI":"10.1137\/S0097539792232586"},{"issue":"3","key":"1_CR54","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N. H. Bshouty","year":"1996","unstructured":"N. H. Bshouty, R. Cleve, R. Gavald\u00e0, S. Kannan, and C. Tamon. Oracles and queries that are sufficient for exact learning. J. Comput. Sys. Sci., 52(3):421\u2013433, 1996.","journal-title":"J. Comput. Sys. Sci."},{"issue":"203","key":"1_CR55","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1090\/S0025-5718-1993-1197511-5","volume":"61","author":"J. Buhler","year":"1993","unstructured":"J. Buhler, R. Crandall, R. Ernvall, and T. Mets\u00e4nkyl\u00e4. Irregular primes and cyclotomic invariants to four million. Mathematics of Computation, 61(203):151\u2013153, 1993.","journal-title":"Mathematics of Computation"},{"key":"1_CR56","doi-asserted-by":"crossref","unstructured":"H. Buhrman, L. Fortnow, and T. Thierauf. Nonrelativizing separations. In Proc. Conference on Computational Complexity, pages 8\u201312, 1998.","DOI":"10.1109\/CCC.1998.694585"},{"key":"1_CR57","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser. Completeness and reduction in algebraic complexity theory. 2000. Available at math- www.uni-paderborn.de\/agpb\/work\/habil.ps .","DOI":"10.1007\/978-3-662-04179-6"},{"issue":"1","key":"1_CR58","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0304-3975(99)00183-8","volume":"235","author":"P. B\u00fcrgisser","year":"2000","unstructured":"P. B\u00fcrgisser. Cook\u2019s versus Valiant\u2019s hypothesis. Theoretical Comput. Sci., 235(1):71\u201388, 2000.","journal-title":"Theoretical Comput. Sci."},{"key":"1_CR59","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser. On defining integers and proving arithmetic circuit lower bounds. Computational Complexity, 18(1):81\u2013103, 2009. Earlier version in Proc. STACS\u20192007, pp. 133\u2013144.","DOI":"10.1007\/s00037-009-0260-x"},{"issue":"4","key":"1_CR60","doi-asserted-by":"crossref","first-page":"1639","DOI":"10.1137\/120892532","volume":"27","author":"P. B\u00fcrgisser","year":"2013","unstructured":"P. B\u00fcrgisser and C. Ikenmeyer. Deciding positivity of Littlewood-Richardson coefficients. SIAM J. Discrete Math., 27(4):1639\u20131681, 2013.","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR61","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser and C. Ikenmeyer. Explicit lower bounds via geometric complexity theory. In Proc. ACM STOC, pages 141\u2013150, 2013. arXiv:1210.8368.","DOI":"10.1145\/2488608.2488627"},{"key":"1_CR62","unstructured":"P. B\u00fcrgisser, C. Ikenmeyer, and J. H\u00fcttenhain. Permanent versus determinant: not via saturations. arXiv:1501.05528, 2015."},{"key":"1_CR63","doi-asserted-by":"crossref","unstructured":"S. R. Buss and R. Williams. Limits on alternation trading proofs for time-space lower bounds. Computational Complexity, 24(3):533\u2013600, 2015. Earlier version in Proc. IEEE Complexity\u20192012, pp. 181\u2013191.","DOI":"10.1007\/s00037-015-0104-9"},{"key":"1_CR64","doi-asserted-by":"crossref","unstructured":"J.-Y. Cai, X. Chen, and D. Li. Quadratic lower bound for permanent vs. determinant in any characteristic. 19(1):37\u201356, 2010. Earlier version in Proc. ACM STOC\u20192008, pp. 491\u2013498.","DOI":"10.1007\/s00037-009-0284-2"},{"key":"1_CR65","unstructured":"A. Cobham. The intrinsic computational difficulty of functions. In Proceedings of Logic, Methodology, and Philosophy of Science II. North Holland, 1965."},{"key":"1_CR66","unstructured":"S. Cook. The P versus NP problem, 2000. Clay Math Institute official problem description. At www.claymath.org\/sites\/default\/files\/pvsnp.pdf ."},{"key":"1_CR67","doi-asserted-by":"crossref","unstructured":"S. A. Cook. The complexity of theorem-proving procedures. In Proc. ACM STOC, pages 151\u2013158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"1_CR68","doi-asserted-by":"crossref","unstructured":"S. A. Cook. A hierarchy for nondeterministic time complexity. In Proc. ACM STOC, pages 187\u2013192, 1972.","DOI":"10.1145\/800152.804913"},{"issue":"3","key":"1_CR69","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1137\/0211037","volume":"11","author":"D. Coppersmith","year":"1982","unstructured":"D. Coppersmith. Rapid multiplication of rectangular matrices. SIAM J. Comput., 11(3):467\u2013471, 1982.","journal-title":"SIAM J. Comput."},{"key":"1_CR70","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251\u2013280, 1990. Earlier version in Proc. ACM STOC\u20191987.","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"1_CR71","doi-asserted-by":"crossref","unstructured":"C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash equilibrium. Commun. of the ACM, 52(2):89\u201397, 2009. Earlier version in Proc. ACM STOC\u20192006.","DOI":"10.1145\/1461928.1461951"},{"issue":"7","key":"1_CR72","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"M. Davis, G. Logemann, and D. Loveland. A machine program for theorem proving. Commun. of the ACM, 5(7):394\u2013397, 1962.","journal-title":"Commun. of the ACM"},{"key":"1_CR73","unstructured":"V. Deolalikar. P \u2260 NP. Archived version available at www.win.tue.nl\/~gwoegi\/P-versus-NP\/Deolalikar.pdf , 2010."},{"issue":"3","key":"1_CR74","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17(3):449\u2013467, 1965.","journal-title":"Canadian Journal of Mathematics"},{"key":"1_CR75","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/089\/1006472","volume":"89","author":"M. R. Fellows","year":"1989","unstructured":"M. R. Fellows. The Robertson-Seymour theorems: a survey of applications. Contemporary Mathematics, 89:1\u201318, 1989.","journal-title":"Contemporary Mathematics"},{"key":"1_CR76","doi-asserted-by":"crossref","unstructured":"S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf. Exponential lower bounds for polytopes in combinatorial optimization. J. of the ACM, 62(2):17, 2015. Earlier version in Proc. ACM STOC\u20192012, pp. 95\u2013106.","DOI":"10.1145\/2716307"},{"key":"1_CR77","doi-asserted-by":"crossref","unstructured":"M. A. Forbes and A. Shpilka. Explicit Noether normalization for simultaneous conjugation via polynomial identity testing. pages 527\u2013542, 2013. arXiv:1303.0084.","DOI":"10.1007\/978-3-642-40328-6_37"},{"key":"1_CR78","volume-title":"Flows in Networks","author":"L. R. Ford","year":"1962","unstructured":"L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton, 1962."},{"issue":"9","key":"1_CR79","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/1562164.1562186","volume":"52","author":"L. Fortnow","year":"2009","unstructured":"L. Fortnow. The status of the P versus NP problem. Commun. of the ACM, 52(9):78\u201386, 2009.","journal-title":"Commun. of the ACM"},{"key":"1_CR80","volume-title":"The Golden Ticket: P, NP, and the Search for the Impossible","author":"L. Fortnow","year":"2009","unstructured":"L. Fortnow. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton University Press, 2009."},{"key":"1_CR81","doi-asserted-by":"crossref","unstructured":"L. Fortnow and D. van Melkebeek. Time-space tradeoffs for nondeterministic computation. In Proc. Conference on Computational Complexity, pages 2\u201313, 2000.","DOI":"10.1109\/CCC.2000.856730"},{"key":"1_CR82","doi-asserted-by":"crossref","unstructured":"L. Fortnow, A. Pavan, and S. Sengupta. Proving SAT does not have small circuits with an application to the two queries problem. J. Comput. Sys. Sci., 74(3):358\u2013363, 2008. Earlier version in Proc. IEEE Complexity\u20192003, pp. 347\u2013350.","DOI":"10.1016\/j.jcss.2007.06.017"},{"key":"1_CR83","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","volume":"28","author":"L. Fortnow","year":"1988","unstructured":"L. Fortnow and M. Sipser. Are there interactive protocols for co-NP languages? Inform. Proc. Lett., 28:249\u2013251, 1988.","journal-title":"Inform. Proc. Lett."},{"key":"1_CR84","unstructured":"H. M. Friedman. Mathematically natural concrete incompleteness. At u.osu.edu\/friedman.8\/ files\/2014\/01\/Putnam062115pdf-15ku867.pdf, 2015."},{"key":"1_CR85","doi-asserted-by":"crossref","unstructured":"M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial time hierarchy. Math. Systems Theory, 17:13\u201327, 1984. Earlier version in Proc. IEEE FOCS\u20191981, pp. 260\u2013270.","DOI":"10.1007\/BF01744431"},{"key":"1_CR86","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979."},{"key":"1_CR87","doi-asserted-by":"crossref","unstructured":"W. Gasarch. The P=?NP poll. SIGACT News, 33(2):34\u201347, June 2002.","DOI":"10.1145\/564585.564599"},{"key":"1_CR88","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. J. of the ACM, 33(4):792\u2013807, 1984. Earlier version in Proc. IEEE FOCS\u20191984, pp. 464\u2013479.","DOI":"10.1145\/6490.6503"},{"issue":"1","key":"1_CR89","first-page":"691","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. of the ACM, 38(1):691\u2013729, 1991.","journal-title":"J. of the ACM"},{"key":"1_CR90","unstructured":"S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In Randomness and Computation, volume 5 of Advances in Computing Research. JAI Press, 1989."},{"key":"1_CR91","doi-asserted-by":"crossref","first-page":"33","DOI":"10.2307\/2268019","volume":"9","author":"R. Goodstein","year":"1944","unstructured":"R. Goodstein. On the restricted ordinal theorem. J. Symbolic Logic, 9:33\u201341, 1944.","journal-title":"J. Symbolic Logic"},{"key":"1_CR92","unstructured":"B. Grenet. An upper bound for the permanent versus determinant problem. www.lirmm.fr\/~grenet\/publis\/Gre11.pdf , 2011."},{"key":"1_CR93","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and M. Karpinski. An exponential lower bound for depth 3 arithmetic circuits. In Proc. ACM STOC, pages 577\u2013582, 1998.","DOI":"10.1145\/276698.276872"},{"key":"1_CR94","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and A. A. Razborov. Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Eng. Commun. Comput., 10(6):465\u2013487, 2000. Earlier version in Proc. IEEE FOCS\u20191998, pp. 269\u2013278.","DOI":"10.1007\/s002009900021"},{"key":"1_CR95","unstructured":"J. A. Grochow. Symmetry and equivalence relations in classical and geometric complexity theory. PhD thesis, 2012."},{"key":"1_CR96","doi-asserted-by":"crossref","unstructured":"J. A. Grochow. Unifying known lower bounds via Geometric Complexity Theory. Computational Complexity, 24(2):393\u2013475, 2015. Earlier version in Proc. IEEE Complexity\u20192014, pp. 274\u2013285.","DOI":"10.1007\/s00037-015-0103-x"},{"key":"1_CR97","doi-asserted-by":"crossref","unstructured":"L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc. ACM STOC, pages 212\u2013219, 1996. quant-ph\/9605043.","DOI":"10.1145\/237814.237866"},{"key":"1_CR98","doi-asserted-by":"crossref","unstructured":"A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Arithmetic circuits: a chasm at depth three. In Proc. IEEE FOCS, pages 578\u2013587, 2013.","DOI":"10.1109\/FOCS.2013.68"},{"key":"1_CR99","doi-asserted-by":"crossref","unstructured":"A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Approaching the chasm at depth four. J. of the ACM, 61(6):1\u201316, 2014. Earlier version in Proc. IEEE Complexity\u20192013, pp. 65\u201373.","DOI":"10.1145\/2629541"},{"key":"1_CR100","doi-asserted-by":"crossref","unstructured":"L. Gurvits. On the complexity of mixed discriminants and related problems. In Mathematical Foundations of Computer Science, pages 447\u2013458, 2005.","DOI":"10.1007\/11549345_39"},{"key":"1_CR101","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"A. Haken. The intractability of resolution. Theoretical Comput. Sci., 39:297\u2013308, 1985.","journal-title":"Theoretical Comput. Sci."},{"key":"1_CR102","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285\u2013306, 1965.","journal-title":"Transactions of the American Mathematical Society"},{"key":"1_CR103","volume-title":"Computational Limitations for Small Depth Circuits","author":"J. H\u00e5stad","year":"1987","unstructured":"J. H\u00e5stad. Computational Limitations for Small Depth Circuits. MIT Press, 1987."},{"key":"1_CR104","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. The shrinkage exponent of De Morgan formulas is 2. SIAM J. Comput., 27(1):48\u201364, 1998. Earlier version in Proc. IEEE FOCS\u20191993, pp. 114\u2013123.","DOI":"10.1137\/S0097539794261556"},{"key":"1_CR105","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. Some optimal inapproximability results. J. of the ACM, 48:798\u2013859, 2001. Earlier version in Proc. ACM STOC\u20191997, pp. 1\u201310.","DOI":"10.1145\/502090.502098"},{"issue":"4","key":"1_CR106","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"J. H\u00e5stad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364\u20131396, 1999.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1_CR107","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M. Held","year":"1962","unstructured":"M. Held and R. M. Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196\u2013210, 1962.","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"1_CR108","unstructured":"C. Ikenmeyer, K. Mulmuley, and M. Walter. On vanishing of Kronecker coefficients. arXiv:1507.02955, 2015."},{"key":"1_CR109","unstructured":"C. Ikenmeyer and G. Panova. Rectangular Kronecker coefficients and plethysms in geometric complexity theory. arXiv:1512.03798, 2015."},{"key":"1_CR110","doi-asserted-by":"crossref","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. SIAM J. Comput., 17(5):935\u2013938, 1988. Earlier version in Proc. IEEE Structure in Complexity Theory, 1988.","DOI":"10.1109\/SCT.1988.5270"},{"key":"1_CR111","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1998","unstructured":"N. Immerman. Descriptive Complexity. Springer, 1998."},{"key":"1_CR112","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, V. Kabanets, and A. Kolokolova. An axiomatic approach to algebrization. In Proc. ACM STOC, pages 695\u2013704, 2009.","DOI":"10.1145\/1536414.1536509"},{"key":"1_CR113","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, V. Kabanets, and A. Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Sys. Sci., 65(4):672\u2013694, 2002. Earlier version in Proc. IEEE Complexity\u20192001, pp. 2\u201312.","DOI":"10.1016\/S0022-0000(02)00024-7"},{"issue":"2","key":"1_CR114","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/rsa.3240040202","volume":"4","author":"R. Impagliazzo","year":"1993","unstructured":"R. Impagliazzo and N. Nisan. The effect of random restrictions on formula size. Random Structures and Algorithms, 4(2):121\u2013134, 1993.","journal-title":"Random Structures and Algorithms"},{"key":"1_CR115","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and A. Wigderson. P=BPP unless E has subexponential circuits: derandomizing the XOR Lemma. In Proc. ACM STOC, pages 220\u2013229, 1997.","DOI":"10.1145\/258533.258590"},{"issue":"3","key":"1_CR116","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1145\/322326.322341","volume":"29","author":"M. Jerrum","year":"1982","unstructured":"M. Jerrum and M. Snir. Some exact complexity results for straight-line computations over semirings. J. of the ACM, 29(3):874\u2013897, 1982.","journal-title":"J. of the ACM"},{"key":"1_CR117","doi-asserted-by":"crossref","unstructured":"V. Kabanets and J.-Y. Cai. Circuit minimization problem. In Proc. ACM STOC, pages 73\u201379, 2000. TR99-045.","DOI":"10.1145\/335305.335314"},{"key":"1_CR118","doi-asserted-by":"crossref","unstructured":"V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity testing means proving circuit lower bounds. Computational Complexity, 13(1-2):1\u201346, 2004. Earlier version in Proc. ACM STOC\u20192003. ECCC TR02-055.","DOI":"10.1007\/s00037-004-0182-6"},{"key":"1_CR119","unstructured":"D. M. Kane and R. Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. arXiv:1511.07860, 2015."},{"key":"1_CR120","doi-asserted-by":"crossref","unstructured":"R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control, 55:40\u201356, 1982. Earlier version in Proc. IEEE FOCS\u20191981, pp. 304\u2013309.","DOI":"10.1016\/S0019-9958(82)90382-5"},{"key":"1_CR121","doi-asserted-by":"crossref","unstructured":"M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Comput., 3:255\u2013265, 1990. Earlier version in Proc. ACM STOC\u20191988, pp. 539\u2013550.","DOI":"10.1137\/0403021"},{"key":"1_CR122","doi-asserted-by":"crossref","unstructured":"R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum Press, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1_CR123","doi-asserted-by":"crossref","unstructured":"R. M. Karp and R. J. Lipton. Turing machines that take advice. Enseign. Math., 28:191\u2013201, 1982. Earlier version in Proc. ACM STOC\u20191980, pp. 302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"1_CR124","doi-asserted-by":"crossref","unstructured":"N. Kayal. Affine projections of polynomials: extended abstract. In Proc. ACM STOC, pages 643\u2013662, 2012.","DOI":"10.1145\/2213977.2214036"},{"key":"1_CR125","doi-asserted-by":"crossref","unstructured":"N. Kayal, N. Limaye, C. Saha, and S. Srinivasan. An exponential lower bound for homogeneous depth four arithmetic formulas. In Proc. IEEE FOCS, pages 61\u201370, 2014.","DOI":"10.1109\/FOCS.2014.15"},{"key":"1_CR126","doi-asserted-by":"crossref","unstructured":"N. Kayal, C. Saha, and R. Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In Proc. ACM STOC, pages 146\u2013153, 2014.","DOI":"10.1145\/2591796.2591847"},{"key":"1_CR127","doi-asserted-by":"crossref","unstructured":"S. Khot. On the Unique Games Conjecture. In Proc. Conference on Computational Complexity, pages 99\u2013121, 2010.","DOI":"10.1109\/CCC.2010.19"},{"key":"1_CR128","first-page":"83","volume":"10","author":"V. M. Khrapchenko","year":"1971","unstructured":"V. M. Khrapchenko. A method of determining lower bounds for the complexity of \u03c0 schemes. Matematischi Zametki, 10:83\u201392, 1971. In Russian.","journal-title":"Matematischi Zametki"},{"key":"1_CR129","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1112\/blms\/14.4.285","volume":"14","author":"L. Kirby","year":"1982","unstructured":"L. Kirby and J. Paris. Accessible independence results for Peano arithmetic. Bulletin of the London Mathematical Society, 14:285\u2013293, 1982.","journal-title":"Bulletin of the London Mathematical Society"},{"key":"1_CR130","doi-asserted-by":"crossref","unstructured":"A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31:1501\u20131526, 2002. Earlier version in Proc. ACM STOC\u20191999.","DOI":"10.1137\/S0097539700389652"},{"key":"1_CR131","volume-title":"Algorithmic Barriers Falling: P=NP?","author":"D. E. Knuth","year":"2014","unstructured":"D. E. Knuth and E. G. Daylight. Algorithmic Barriers Falling: P=NP? Lonely Scholar, 2014."},{"issue":"4","key":"1_CR132","doi-asserted-by":"crossref","first-page":"1055","DOI":"10.1090\/S0894-0347-99-00299-4","volume":"12","author":"A. Knutson","year":"1999","unstructured":"A. Knutson and T. Tao. The honeycomb model of $$GL_{n}(\\mathbb{C})$$ tensor products I: proof of the saturation conjecture. J. Amer. Math. Soc., 12(4):1055\u20131090, 1999.","journal-title":"J. Amer. Math. Soc."},{"key":"1_CR133","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.tcs.2012.03.041","volume":"448","author":"P. Koiran","year":"2012","unstructured":"P. Koiran. Arithmetic circuits: the chasm at depth four gets wider. Theor. Comput. Sci., 448:56\u201365, 2012.","journal-title":"Theor. Comput. Sci."},{"key":"1_CR134","doi-asserted-by":"crossref","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge, 1997."},{"key":"1_CR135","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner. On the structure of polynomial time reducibility. J. of the ACM, 22:155\u2013171, 1975.","journal-title":"J. of the ACM"},{"key":"1_CR136","doi-asserted-by":"crossref","unstructured":"J. M. Landsberg. The border rank of the multiplication of two by two matrices is seven. J. Amer. Math. Soc., 19(2):447\u2013459, 2006. arXiv:math\/0407224.","DOI":"10.1090\/S0894-0347-05-00506-0"},{"key":"1_CR137","unstructured":"J. M. Landsberg. Geometric complexity theory: an introduction for geometers. Annali dell\u2019Universita di Ferrara, 61(1):65\u2013117, 2015. arXiv:1305.7387."},{"key":"1_CR138","doi-asserted-by":"crossref","unstructured":"J. M. Landsberg and G. Ottaviani. New lower bounds for the border rank of matrix multiplication. Theory of Computing, 11:285\u2013298, 2015. arXiv:1112.6007.","DOI":"10.4086\/toc.2015.v011a011"},{"key":"1_CR139","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C. Lautemann","year":"1983","unstructured":"C. Lautemann. BPP and the polynomial hierarchy. Inform. Proc. Lett., 17:215\u2013217, 1983.","journal-title":"Inform. Proc. Lett."},{"key":"1_CR140","doi-asserted-by":"crossref","unstructured":"J. R. Lee, P. Raghavendra, and D. Steurer. Lower bounds on the size of semidefinite programming relaxations. In Proc. ACM STOC, pages 567\u2013576, 2015.","DOI":"10.1145\/2746539.2746599"},{"issue":"3","key":"1_CR141","first-page":"115","volume":"9","author":"L. A. Levin","year":"1973","unstructured":"L. A. Levin. Universal sequential search problems. Problems of Information Transmission, 9(3):115\u2013116, 1973.","journal-title":"Problems of Information Transmission"},{"issue":"3","key":"1_CR142","first-page":"206","volume":"10","author":"L. A. Levin","year":"1974","unstructured":"L. A. Levin. Laws of information conservation (non-growth) and aspects of the foundations of probability theory. Problems of Information Transmission, 10(3):206\u2013210, 1974.","journal-title":"Problems of Information Transmission"},{"issue":"3","key":"1_CR143","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0020-0190(92)90138-L","volume":"42","author":"M. Li","year":"1992","unstructured":"M. Li and P. M. B. Vit\u00e1nyi. Average case complexity under the universal distribution equals worst-case complexity. Inform. Proc. Lett., 42(3):145\u2013149, 1992.","journal-title":"Inform. Proc. Lett."},{"key":"1_CR144","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. J. of the ACM, 40(3):607\u2013620, 1993. Earlier version in Proc. IEEE FOCS\u20191989, pp. 574\u2013579.","DOI":"10.1145\/174130.174138"},{"key":"1_CR145","doi-asserted-by":"crossref","unstructured":"N. Linial and N. Nisan. Approximate inclusion-exclusion. Combinatorica, 10(4):349\u2013365, 1990. Earlier version in Proc. ACM STOC\u20191990.","DOI":"10.1145\/100216.100250"},{"key":"1_CR146","doi-asserted-by":"crossref","unstructured":"R. J. Lipton. New directions in testing. In Distributed Computing and Cryptography, pages 191\u2013202. AMS, 1991.","DOI":"10.1090\/dimacs\/002\/13"},{"key":"1_CR147","unstructured":"R. J. Lipton. Galactic algorithms, 2010. rjlipton. wordpress.com\/2010\/10\/23\/galactic-algorithms\/."},{"key":"1_CR148","volume-title":"Practically P=NP?","author":"R. J. Lipton","year":"2014","unstructured":"R. J. Lipton and K. W. Regan. Practically P=NP?, 2014. rjlipton.wordpress.com\/2014\/02\/28\/practically-pnp\/."},{"key":"1_CR149","doi-asserted-by":"crossref","unstructured":"R. J. Lipton and A. Viglas. On the complexity of SAT. In Proc. IEEE FOCS, pages 459\u2013464, 1999.","DOI":"10.1109\/SFFCS.1999.814618"},{"key":"1_CR150","doi-asserted-by":"crossref","first-page":"81","DOI":"10.24033\/msmf.110","volume":"33","author":"D. Luna","year":"1973","unstructured":"D. Luna. Slices \u00e9tales. M\u00e9moires de la Soci\u00e9t\u00e9 Math\u00e9matique de France, 33:81\u2013105, 1973.","journal-title":"M\u00e9moires de la Soci\u00e9t\u00e9 Math\u00e9matique de France"},{"key":"1_CR151","doi-asserted-by":"crossref","unstructured":"C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. J. of the ACM, 39:859\u2013868, 1992. Earlier version in Proc. IEEE FOCS\u20191990, pp. 2\u201310.","DOI":"10.1145\/146585.146605"},{"key":"1_CR152","doi-asserted-by":"crossref","unstructured":"D. van Melkebeek. A survey of lower bounds for satisfiability and related problems. Foundations and Trends in Theoretical Computer Science, 2:197\u2013303, 2007. ECCC TR07-099.","DOI":"10.1561\/0400000012"},{"key":"1_CR153","doi-asserted-by":"crossref","first-page":"4241","DOI":"10.1155\/S1073792804142566","volume":"79","author":"T. Mignon","year":"2004","unstructured":"T. Mignon and N. Ressayre. A quadratic bound for the determinant and permanent problem. International Mathematics Research Notices, (79):4241\u20134253, 2004.","journal-title":"International Mathematics Research Notices"},{"key":"1_CR154","doi-asserted-by":"crossref","unstructured":"G. L. Miller. Riemann\u2019s hypothesis and tests for primality. J. Comput. Sys. Sci., 13:300\u2013317, 1976. Earlier version in Proc. ACM STOC\u20191975.","DOI":"10.1016\/S0022-0000(76)80043-8"},{"key":"1_CR155","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001","volume-title":"The Nature of Computation","author":"C. Moore","year":"2011","unstructured":"C. Moore and S. Mertens. The Nature of Computation. Oxford University Press, 2011."},{"issue":"1","key":"1_CR156","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-0000(81)90017-9","volume":"22","author":"S. Moran","year":"1981","unstructured":"S. Moran. Some results on relativized deterministic and nondeterministic time hierarchies. J. Comput. Sys. Sci., 22(1):1\u20138, 1981.","journal-title":"J. Comput. Sys. Sci."},{"key":"1_CR157","unstructured":"K. Mulmuley. GCT publications web page. ramakrishnadas.cs.uchicago.edu."},{"issue":"4","key":"1_CR158","doi-asserted-by":"crossref","first-page":"1460","DOI":"10.1137\/S0097539794282930","volume":"28","author":"K. Mulmuley","year":"1999","unstructured":"K. Mulmuley. Lower bounds in a parallel model without bit operations. SIAM J. Comput., 28(4):1460\u20131509, 1999.","journal-title":"SIAM J. Comput."},{"key":"1_CR159","unstructured":"K. Mulmuley. Geometric complexity theory VII: nonstandard quantum group for the plethysm problem. Technical Report TR-2007-14, University of Chicago, 2007. arXiv:0709.0749."},{"key":"1_CR160","unstructured":"K. Mulmuley. Geometric complexity theory VIII: on canonical bases for the nonstandard quantum groups. Technical Report TR-2007-15, University of Chicago, 2007. arXiv:0709.0751."},{"key":"1_CR161","unstructured":"K. Mulmuley. Explicit proofs and the flip. arXiv:1009.0246, 2010."},{"key":"1_CR162","unstructured":"K. Mulmuley. Geometric complexity theory VI: the flip via positivity. Technical report, University of Chicago, 2011. arXiv:0704.0229."},{"key":"1_CR163","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. On P vs. NP and geometric complexity theory: dedicated to Sri Ramakrishna. J. of the ACM, 58(2):5, 2011.","DOI":"10.1145\/1944345.1944346"},{"key":"1_CR164","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. The GCT program toward the P vs. NP problem. Commun. of the ACM, 55(6):98\u2013107, June 2012.","DOI":"10.1145\/2184319.2184341"},{"key":"1_CR165","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. Geometric complexity theory V: equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether\u2019s Normalization Lemma. In Proc. IEEE FOCS, pages 629\u2013638, 2012. Full version available at arXiv:1209.5993.","DOI":"10.1109\/FOCS.2012.15"},{"issue":"1","key":"1_CR166","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/s10801-011-0325-1","volume":"36","author":"K. Mulmuley","year":"2012","unstructured":"K. Mulmuley, H. Narayanan, and M. Sohoni. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. Journal of Algebraic Combinatorics, 36(1):103\u2013110, 2012.","journal-title":"Journal of Algebraic Combinatorics"},{"key":"1_CR167","doi-asserted-by":"crossref","unstructured":"K. Mulmuley and M. Sohoni. Geometric complexity theory I: An approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496\u2013526, 2001.","DOI":"10.1137\/S009753970038715X"},{"issue":"3","key":"1_CR168","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1137\/080718115","volume":"38","author":"K. Mulmuley","year":"2008","unstructured":"K. Mulmuley and M. Sohoni. Geometric complexity theory II: Towards explicit obstructions for embeddings among class varieties. SIAM J. Comput., 38(3):1175\u20131206, 2008.","journal-title":"SIAM J. Comput."},{"key":"1_CR169","unstructured":"C. D. Murray and R. R. Williams. On the (non) NP-hardness of computing circuit complexity. In Proc. Conference on Computational Complexity, pages 365\u2013380, 2015."},{"key":"1_CR170","doi-asserted-by":"crossref","unstructured":"J. Naor and M. Naor. Number-theoretic constructions of efficient pseudo-random functions. J. of the ACM, 51(2):231\u2013262, 2004. Earlier version in Proc. IEEE FOCS\u20191997.","DOI":"10.1145\/972639.972643"},{"key":"1_CR171","volume-title":"Letter to the United States National Security Agency","author":"J. Nash","year":"1950","unstructured":"J. Nash. Letter to the United States National Security Agency, 1950. Available at www.nsa.gov\/public_info\/_files\/nash_letters\/nash_letters1.pdf ."},{"key":"1_CR172","volume-title":"Quantum Computation and Quantum Information","author":"M. Nielsen","year":"2000","unstructured":"M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000."},{"key":"1_CR173","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217\u2013234, 1997. Earlier version in Proc. IEEE FOCS\u20191995, pp. 16\u201325.","DOI":"10.1007\/BF01294256"},{"key":"1_CR174","volume-title":"Affine relativization: unifying the algebrization and relativization barriers","author":"B. Ayd\u0131nl\u0131o\u011flu","year":"2016","unstructured":"B. Ayd\u0131nl\u0131o\u011flu and E. Bach. Affine relativization: unifying the algebrization and relativization barriers. 2016."},{"key":"1_CR175","volume-title":"Computational Complexity","author":"C. H. Papadimitriou","year":"1994","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"issue":"2","key":"1_CR176","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/rsa.3240040203","volume":"4","author":"M. Paterson","year":"1993","unstructured":"M. Paterson and U. Zwick. Shrinkage of De Morgan formulae under restriction. Random Structures and Algorithms, 4(2):135\u2013150, 1993.","journal-title":"Random Structures and Algorithms"},{"key":"1_CR177","doi-asserted-by":"crossref","unstructured":"W. J. Paul, N. Pippenger, E. Szemer\u00e9di, and W. T. Trotter. On determinism versus non-determinism and related problems. In Proc. IEEE FOCS, pages 429\u2013438, 1983.","DOI":"10.1109\/SFCS.1983.39"},{"key":"1_CR178","doi-asserted-by":"crossref","unstructured":"C. Peikert and B. Waters. Lossy trapdoor functions and their applications. SIAM J. Comput., 40(6):1803\u20131844, 2011. Earlier version in Proc. ACM STOC\u20192008.","DOI":"10.1137\/080733954"},{"key":"1_CR179","unstructured":"G. Perelman. The entropy formula for the Ricci flow and its geometric applications. arXiv:math\/0211159, 2002."},{"issue":"3","key":"1_CR180","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0204018","volume":"4","author":"V. R. Pratt","year":"1975","unstructured":"V. R. Pratt. Every prime has a succinct certificate. SIAM J. Comput., 4(3):214\u2013220, 1975.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1_CR181","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"M. O. Rabin","year":"1980","unstructured":"M. O. Rabin. Probabilistic algorithm for testing primality. J. Number Theory, 12(1):128\u2013138, 1980.","journal-title":"J. Number Theory"},{"key":"1_CR182","doi-asserted-by":"crossref","unstructured":"R. Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. of the ACM, 56(2):8, 2009. Earlier version in Proc. ACM STOC\u20192004, pp. 633\u2013641. ECCC TR03-067.","DOI":"10.1145\/1502793.1502797"},{"key":"1_CR183","doi-asserted-by":"crossref","unstructured":"R. Raz. Elusive functions and lower bounds for arithmetic circuits. Theory of Computing, 6:135\u2013177, 2010. Earlier version in Proc. ACM STOC\u20192008.","DOI":"10.1145\/1374376.1374479"},{"key":"1_CR184","doi-asserted-by":"crossref","unstructured":"R. Raz. Tensor-rank and lower bounds for arithmetic formulas. J. of the ACM, 60(6):40, 2013. Earlier version in Proc. ACM STOC\u20192010, pp. 659\u2013666.","DOI":"10.1145\/2535928"},{"key":"1_CR185","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171\u2013207, 2009. Earlier version in Proc. IEEE Complexity\u20192008, pp. 128\u2013139.","DOI":"10.1007\/s00037-009-0270-8"},{"key":"1_CR186","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Yehudayoff. Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. J. Comput. Sys. Sci., 77(1):167\u2013190, 2011. Earlier version in Proc. IEEE FOCS\u20192008, pp. 273\u2013282.","DOI":"10.1016\/j.jcss.2010.06.013"},{"key":"1_CR187","unstructured":"A. A. Razborov. Lower bounds for the monotone complexity of some Boolean functions. Doklady Akademii Nauk SSSR, 281(4):798\u2013801, 1985. English translation in Soviet Math. Doklady 31:354\u2013357, 1985."},{"key":"1_CR188","doi-asserted-by":"crossref","unstructured":"A. A. Razborov. Lower bounds on monotone complexity of the logical permanent. Mathematical Notes, 37(6):485\u2013493, 1985. Original Russian version in Matematischi Zametki.","DOI":"10.1007\/BF01157687"},{"key":"1_CR189","unstructured":"A. A. Razborov. Lower bounds for the size of circuits of bounded depth with basis $$\\left \\{\\&,\\oplus \\right \\}$$ . Mathematicheskie Zametki, 41(4):598\u2013607, 1987. English translation in Math. Notes. Acad. Sci. USSR 41(4):333\u2013338, 1987."},{"issue":"1","key":"1_CR190","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1070\/IM1995v059n01ABEH000009","volume":"59","author":"A. A. Razborov","year":"1995","unstructured":"A. A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya Math., 59(1):205\u2013227, 1995.","journal-title":"Izvestiya Math."},{"key":"1_CR191","doi-asserted-by":"crossref","unstructured":"A. A. Razborov and S. Rudich. Natural proofs. J. Comput. Sys. Sci., 55(1):24\u201335, 1997. Earlier version in Proc. ACM STOC\u20191994, pp. 204\u2013213.","DOI":"10.1006\/jcss.1997.1494"},{"key":"1_CR192","unstructured":"K. W. Regan. Understanding the Mulmuley-Sohoni approach to P vs. NP. Bulletin of the EATCS, 78:86\u201399, 2002."},{"key":"1_CR193","doi-asserted-by":"crossref","unstructured":"B. Rossman, R. A. Servedio, and L.-Y. Tan. An average-case depth hierarchy theorem for Boolean circuits. In Proc. IEEE FOCS, pages 1030\u20131048, 2015. ECCC TR15-065.","DOI":"10.1109\/FOCS.2015.67"},{"key":"1_CR194","doi-asserted-by":"crossref","unstructured":"T. Rothvo\u00df. The matching polytope has exponential extension complexity. In Proc. ACM STOC, pages 263\u2013272, 2014.","DOI":"10.1145\/2591796.2591834"},{"key":"1_CR195","doi-asserted-by":"crossref","unstructured":"R. Santhanam. Circuit lower bounds for Merlin-Arthur classes. In Proc. ACM STOC, pages 275\u2013283, 2007.","DOI":"10.1145\/1250790.1250832"},{"key":"1_CR196","doi-asserted-by":"crossref","unstructured":"S. Saraf. Recent progress on lower bounds for arithmetic circuits. In Proc. Conference on Computational Complexity, pages 155\u2013160, 2014.","DOI":"10.1109\/CCC.2014.23"},{"issue":"2","key":"1_CR197","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Sys. Sci., 4(2):177\u2013192, 1970.","journal-title":"J. Comput. Sys. Sci."},{"key":"1_CR198","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proc. IEEE FOCS, pages 410\u2013414, 1999.","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"1_CR199","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-60322-8","volume-title":"Gems of Theoretical Computer Science","author":"U. Sch\u00f6ning","year":"1998","unstructured":"U. Sch\u00f6ning and R. J. Pruim. Gems of Theoretical Computer Science. Springer, 1998."},{"key":"1_CR200","doi-asserted-by":"crossref","unstructured":"A. Shamir. IP=PSPACE. J. of the ACM, 39(4):869\u2013877, 1992. Earlier version in Proc. IEEE FOCS\u20191990, pp. 11\u201315.","DOI":"10.1145\/146585.146609"},{"issue":"1","key":"1_CR201","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"C. Shannon","year":"1949","unstructured":"C. Shannon. The synthesis of two-terminal switching circuits. Bell System Technical Journal, 28(1):59\u201398, 1949.","journal-title":"Bell System Technical Journal"},{"key":"1_CR202","unstructured":"J. Shoenfield. The problem of predicativity. In Y. Bar-Hillel et al., editor, Essays on the Foundations of Mathematics, pages 132\u2013142. Hebrew University Magnes Press, 1961."},{"key":"1_CR203","doi-asserted-by":"crossref","unstructured":"P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484\u20131509, 1997. Earlier version in Proc. IEEE FOCS\u20191994. quant-ph\/9508027.","DOI":"10.1137\/S0097539795293172"},{"key":"1_CR204","doi-asserted-by":"crossref","unstructured":"A. Shpilka and A. Wigderson. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity, 10(1):1\u201327, 2001. Earlier version in Proc. IEEE Complexity\u20191999.","DOI":"10.1007\/PL00001609"},{"issue":"3-4","key":"1_CR205","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1561\/0400000039","volume":"5","author":"A. Shpilka","year":"2010","unstructured":"A. Shpilka and A. Yehudayoff. Arithmetic circuits: a survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207\u2013388, 2010.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"1_CR206","doi-asserted-by":"crossref","unstructured":"M. Sipser. A complexity theoretic approach to randomness. In Proc. ACM STOC, pages 330\u2013335, 1983.","DOI":"10.1145\/800061.808762"},{"key":"1_CR207","doi-asserted-by":"crossref","unstructured":"M. Sipser. The history and status of the P versus NP question. In Proc. ACM STOC, pages 603\u2013618, 1992.","DOI":"10.1145\/129712.129771"},{"key":"1_CR208","volume-title":"Introduction to the Theory of Computation (Second Edition)","author":"M. Sipser","year":"2005","unstructured":"M. Sipser. Introduction to the Theory of Computation (Second Edition). Course Technology, 2005."},{"key":"1_CR209","doi-asserted-by":"crossref","unstructured":"R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. ACM STOC, pages 77\u201382, 1987.","DOI":"10.1145\/28395.28404"},{"issue":"1","key":"1_CR210","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1977","unstructured":"R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM J. Comput., 6(1):84\u201385, 1977.","journal-title":"SIAM J. Comput."},{"key":"1_CR211","doi-asserted-by":"crossref","unstructured":"A. Srinivasan. On the approximability of clique and related maximization problems. J. Comput. Sys. Sci., 67(3):633\u2013651, 2003. Earlier version in Proc. ACM STOC\u20192000, pp. 144\u2013152.","DOI":"10.1016\/S0022-0000(03)00110-7"},{"key":"1_CR212","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer. The complexity of approximate counting. In Proc. ACM STOC, pages 118\u2013126, 1983.","DOI":"10.1145\/800061.808740"},{"key":"1_CR213","unstructured":"A. J. Stothers. On the complexity of matrix multiplication. PhD thesis, 2010."},{"issue":"13","key":"1_CR214","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","volume":"14","author":"V. Strassen","year":"1969","unstructured":"V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 14(13):354\u2013356, 1969.","journal-title":"Numerische Mathematik"},{"key":"1_CR215","first-page":"182","volume":"264","author":"V. Strassen","year":"1973","unstructured":"V. Strassen. Vermeidung von divisionen. Journal f\u00fcr die Reine und Angewandte Mathematik, 264:182\u2013202, 1973.","journal-title":"Journal f\u00fcr die Reine und Angewandte Mathematik"},{"key":"1_CR216","unstructured":"B. A. Subbotovskaya. Realizations of linear functions by formulas using +,\u2009\u00d7,\u2009\u2212. Doklady Akademii Nauk SSSR, 136(3):553\u2013555, 1961. In Russian."},{"key":"1_CR217","unstructured":"E. R. Swart. P = NP. Technical report, University of Guelph, 1986. Revision in 1987."},{"issue":"3","key":"1_CR218","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26(3):279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"1_CR219","doi-asserted-by":"crossref","unstructured":"A. Tal. Shrinkage of De Morgan formulae by spectral techniques. In Proc. IEEE FOCS, pages 551\u2013560, 2014. ECCC TR14-048.","DOI":"10.1109\/FOCS.2014.65"},{"issue":"1","key":"1_CR220","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"\u00c9. Tardos","year":"1988","unstructured":"\u00c9. Tardos. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141\u2013142, 1988.","journal-title":"Combinatorica"},{"key":"1_CR221","doi-asserted-by":"crossref","unstructured":"S. Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inf. Comput., 240:2\u201311, 2015. Earlier version in Proc. MFCS\u20192013, pp. 813\u2013824.","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"1_CR222","doi-asserted-by":"crossref","unstructured":"S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865\u2013877, 1991. Earlier version in Proc. IEEE FOCS\u20191989, pp. 514\u2013519.","DOI":"10.1137\/0220053"},{"issue":"4","key":"1_CR223","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/MAHC.1984.10036","volume":"6","author":"B. A. Trakhtenbrot","year":"1984","unstructured":"B. A. Trakhtenbrot. A survey of Russian approaches to perebor (brute-force search) algorithms. Annals of the History of Computing, 6(4):384\u2013400, 1984.","journal-title":"Annals of the History of Computing"},{"key":"1_CR224","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical Foundations of Computer Science, pages 162\u2013176, 1977.","DOI":"10.1007\/3-540-08353-7_135"},{"key":"1_CR225","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. Completeness classes in algebra. In Proc. ACM STOC, pages 249\u2013261, 1979.","DOI":"10.1145\/800135.804419"},{"issue":"2","key":"1_CR226","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of computing the permanent. Theoretical Comput. Sci., 8(2):189\u2013201, 1979.","journal-title":"Theoretical Comput. Sci."},{"key":"1_CR227","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. Accidental algorithms. In Proc. IEEE FOCS, pages 509\u2013517, 2006.","DOI":"10.1109\/FOCS.2006.7"},{"issue":"4","key":"1_CR228","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. G. Valiant","year":"1983","unstructured":"L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641\u2013644, 1983.","journal-title":"SIAM J. Comput."},{"key":"1_CR229","unstructured":"Various authors. Deolalikar P vs NP paper (wiki page). Last modified 30 September 2011. michaelnielsen.org\/polymath1\/index.php?title=Deolalikar_P_vs_NP_paper."},{"key":"1_CR230","doi-asserted-by":"crossref","unstructured":"V. Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proc. ACM STOC, pages 887\u2013898, 2012.","DOI":"10.1145\/2213977.2214056"},{"key":"1_CR231","doi-asserted-by":"crossref","unstructured":"N. V. Vinodchandran. A note on the circuit complexity of PP. Theor. Comput. Sci., 347:415\u2013418, 2005. ECCC TR04-056.","DOI":"10.1016\/j.tcs.2005.07.032"},{"key":"1_CR232","doi-asserted-by":"crossref","unstructured":"A. Wigderson. P, NP and mathematics - a computational complexity perspective. In Proceedings of the International Congress of Mathematicians 2006 (Madrid), pages 665\u2013712. EMS Publishing House, 2007. www.math.ias.edu\/~avi\/PUBLICATIONS\/MYPAPERS\/W06\/w06.pdf .","DOI":"10.4171\/022-1\/25"},{"issue":"3","key":"1_CR233","doi-asserted-by":"crossref","first-page":"443","DOI":"10.2307\/2118559","volume":"141","author":"A. Wiles","year":"1995","unstructured":"A. Wiles. Modular elliptic curves and Fermat\u2019s Last Theorem. Annals of Mathematics, 141(3):443\u2013551, 1995.","journal-title":"Annals of Mathematics"},{"key":"1_CR234","doi-asserted-by":"crossref","unstructured":"R. Williams. Better time-space lower bounds for SAT and related problems. In Proc. Conference on Computational Complexity, pages 40\u201349, 2005.","DOI":"10.1109\/CCC.2005.6"},{"key":"1_CR235","doi-asserted-by":"crossref","unstructured":"R. Williams. Time-space tradeoffs for counting NP solutions modulo integers. Computational Complexity, 17(2):179\u2013219, 2008. Earlier version in Proc. IEEE Complexity\u20192007, pp. 70\u201382.","DOI":"10.1007\/s00037-008-0248-y"},{"issue":"3","key":"1_CR236","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1145\/2034575.2034591","volume":"42","author":"R. Williams","year":"2011","unstructured":"R. Williams. Guest column: a casual tour around a circuit complexity bound. ACM SIGACT News, 42(3):54\u201376, 2011.","journal-title":"ACM SIGACT News"},{"key":"1_CR237","doi-asserted-by":"crossref","unstructured":"R. Williams. Alternation-trading proofs, linear programming, and lower bounds. ACM Trans. on Computation Theory, 5(2):6, 2013. Earlier version in Proc. STACS\u20192010, pp. 669\u2013680.","DOI":"10.1145\/2493246.2493249"},{"key":"1_CR238","doi-asserted-by":"crossref","unstructured":"R. Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218\u20131244, 2013. Earlier version in Proc. ACM STOC\u20192010.","DOI":"10.1137\/10080703X"},{"key":"1_CR239","doi-asserted-by":"crossref","unstructured":"R. Williams. Natural proofs versus derandomization. In Proc. ACM STOC, pages 21\u201330, 2013.","DOI":"10.1145\/2488608.2488612"},{"key":"1_CR240","doi-asserted-by":"crossref","unstructured":"R. Williams. Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable. In Proceedings of the International Congress of Mathematicians, 2014.","DOI":"10.1109\/CCC.2014.33"},{"key":"1_CR241","doi-asserted-by":"crossref","unstructured":"R. Williams. New algorithms and lower bounds for circuits with linear threshold gates. In Proc. ACM STOC, pages 194\u2013202, 2014.","DOI":"10.1145\/2591796.2591858"},{"key":"1_CR242","doi-asserted-by":"crossref","unstructured":"R. Williams. Nonuniform ACC circuit lower bounds. J. of the ACM, 61(1):1\u201332, 2014. Earlier version in Proc. IEEE Complexity\u20192011.","DOI":"10.1145\/2559903"},{"issue":"2","key":"1_CR243","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. B. Wilson","year":"1985","unstructured":"C. B. Wilson. Relativized circuit complexity. J. Comput. Sys. Sci., 31(2):169\u2013181, 1985.","journal-title":"J. Comput. Sys. Sci."},{"key":"1_CR244","doi-asserted-by":"crossref","unstructured":"M. Yannakakis. Expressing combinatorial optimization problems by linear programs. J. Comput. Sys. Sci., 43(3):441\u2013466, 1991. Earlier version in Proc. ACM STOC\u20191988, pp. 223\u2013228.","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"1_CR245","doi-asserted-by":"crossref","unstructured":"A. C-C. Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In Proc. IEEE FOCS, pages 1\u201310, 1985.","DOI":"10.1109\/SFCS.1985.49"},{"key":"1_CR246","doi-asserted-by":"crossref","unstructured":"A. C-C. Yao. On ACC and threshold circuits. In Proc. IEEE FOCS, pages 619\u2013627, 1990.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Open Problems in Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-32162-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T23:56:01Z","timestamp":1748994961000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-32162-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319321608","9783319321622"],"references-count":246,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-32162-2_1","relation":{},"subject":[],"published":{"date-parts":[[2016]]}}}