[1]   Scott Aaronson: PNP. In Open Problems in Mathematics, pp. 1–122. Springer, 2016. [doi:10.1007/978-3-319-32162-2_1]

[2]   Scott Aaronson and Andrew Drucker: Arithmetic natural proofs theory is sought, 2008. Shtetl-Optimized: The Blog of Scott Aaronson.

[3]   Scott Aaronson and Avi Wigderson: Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):2:1–2:54, 2009. Conference version in STOC’08. [doi:10.1145/1490270.1490272]

[4]   Manindra Agrawal: Proving lower bounds via pseudo-random generators. In Proc. 25th Internat. Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’05), pp. 92–105. Springer, 2005. [doi:10.1007/11590156_6]

[5]   Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena: Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM J. Comput., 44(3):669–697, 2015. [doi:10.1137/140975103, arXiv:1406.7535]

[6]   Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena: Jacobian hits circuits: Hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits. SIAM J. Comput., 45(4):1533–1562, 2016. Conference version in STOC’12. [doi:10.1137/130910725, arXiv:1111.0582]

[7]    Manindra Agrawal, Chandan Saha, and Nitin Saxena: Quasi-polynomial hitting-set for set-depth- formulas. In Proc. 45th STOC, pp. 321–330. ACM Press, 2013. [doi:10.1145/2488608.2488649, arXiv:1209.2333]

[8]   Manindra Agrawal and V. Vinay: Arithmetic circuits: A chasm at depth four. In Proc. 49th FOCS, pp. 67–75. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.32]

[9]   Miklós Ajtai: Σ₁¹-formulae on finite structures. Ann. Pure Appl. Logic, 24(1):1–48, 1983. [doi:10.1016/0168-0072(83)90038-6]

[10]   Eric Allender, Jia Jiao, Meena Mahajan, and V. Vinay: Non-commutative arithmetic circuits: depth reduction and size lower bounds. Theoret. Comput. Sci., 209(1–2):47–86, 1998. [doi:10.1016/S0304-3975(97)00227-2]

[11]   Noga Alon and Ravi B. Boppana: The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1–22, 1987. [doi:10.1007/BF02579196]

[12]   Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta: Simple construction of almost k-wise independent random variables. Random Structures Algorithms, 3(3):289–304, 1992. Conference version in FOCS’90. [doi:10.1002/rsa.3240030308]

[13]   Aleksandr Egorovich Andreev: On a method for obtaining lower bounds for the complexity of individual monotone functions. Doklady Akad. Nauk SSSR, 282(5):1033–1037, 1985. Russian. English translation in Soviet Math. Dokl. 31 (1985) 530–534.

[14]   Theodore P. Baker, John Gill, and Robert Solovay: Relativizations of the PNP question. SIAM J. Comput., 4(4):431–442, 1975. [doi:10.1137/0204037]

[15]   Walter Baur and Volker Strassen: The complexity of partial derivatives. Theoret. Comput. Sci., 22(3):317–330, 1983. [doi:10.1016/0304-3975(83)90110-X]

[16]   Malte Beecken, Johannes Mittmann, and Nitin Saxena: Algebraic independence and blackbox identity testing. Inform. and Comput., 222:2–19, 2013. Conference version in ICALP’11. [doi:10.1016/j.ic.2012.10.004, arXiv:1102.2789]

[17]   Stuart J. Berkowitz: On computing the determinant in small parallel time using a small number of processors. Inform. Process. Lett., 18(3):147–150, 1984. [doi:10.1016/0020-0190(84)90018-8]

[18]   Markus Bläser: Explicit tensors. In Perspectives in Computational Complexity, pp. 117–130. Springer, 2014. [doi:10.1007/978-3-319-05446-9_6]

[19]   Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov: Generalized matrix completion and algebraic natural proofs. In Proc. 45th STOC, pp. 1193–1206. ACM Press, 2018. [doi:10.1145/3188745.3188832]

[20]   Mark Braverman: Polylogarithmic independence fools AC⁰ circuits. J. ACM, 57(5):28:1–28:10, 2010. Conference version in CCC’09. [doi:10.1145/1754399.1754401]

[21]   Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam: On algebraic branching programs of small width. J. ACM, 65(5), 2018. Conference version in CCC’17. [doi:10.1145/3209663, arXiv:1702.05328]

[22]   Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory. Springer, 2000. [doi:10.1007/978-3-662-04179-6]

[23]   Peter Bürgisser, Michael Clausen, and Mohammad A. Shokrollahi: Algebraic Complexity Theory. Springer, 1997. [doi:10.1007/978-3-662-03338-8]

[24]   Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova: Learning algorithms from natural proofs. In Proc. 31st Conf. on Computational Complexity (CCC’16), pp. 10:1–10:24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.10]

[25]   Brynmor Chapman and R. Ryan Williams: The circuit-input game, natural proofs, and testing circuits with data. In Proc. 6th Conf. on Innovations in Theoret. Computer Science (ITCS’15), pp. 263–270. ACM Press, 2015. [doi:10.1145/2688073.2688115]

[26]   Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, and V. Vinay: The chasm at depth four, and tensor rank : Old results, new insights. Electron. Colloq. on Comput. Complexity (ECCC), 2016. [ECCC:TR16-096, arXiv:1606.04200]

[27]   Timothy Y. Chow: Almost-natural proofs. J. Comput. System Sci., 77(4):728–737, 2011. Conference version in FOCS’08. [doi:10.1016/j.jcss.2010.06.017, arXiv:0805.1385]

[28]   Richard A. DeMillo and Richard J. Lipton: A probabilistic remark on algebraic program testing. Inform. Process. Lett., 7(4):193–195, 1978. [doi:10.1016/0020-0190(78)90067-4]

[29]   Zeev Dvir and Amir Shpilka: Locally Decodable Codes with two queries and Polynomial Identity Testing for depth 3 circuits. SIAM J. Comput., 36(5):1404–1434, 2007. Conference version in STOC’05. [doi:10.1137/05063605X]

[30]   Zeev Dvir, Amir Shpilka, and Amir Yehudayoff: Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279–1293, 2009. Conference version in STOC’08. [doi:10.1137/080735850]

[31]   Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson: Barriers for rank methods in arithmetic complexity. In Proc. 9th Conf. on Innovations in Theoret. Computer Science (ITCS’18), pp. 1:1–1:19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.1, arXiv:1710.09502]

[32]   Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf: Bipartite perfect matching is in quasi-NC. In Proc. 48th STOC, pp. 754–763. ACM Press, 2016. [doi:10.1145/2897518.2897564, arXiv:1601.06319]

[33]   Michael A. Forbes: Deterministic divisibility testing via shifted partial derivatives. In Proc. 56th FOCS, pp. 451–465. IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.35]

[34]   Michael A. Forbes and Venkatesan Guruswami: Dimension expanders via rank condensers. In Proc. 19th Internat. Workshop on Randomization and Computation (RANDOM’15), pp. 800–814. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.800, arXiv:1411.7455]

[35]   Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka: Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proc. 46th STOC, pp. 867–875. ACM Press, 2014. [doi:10.1145/2591796.2591816]

[36]   Michael A. Forbes and Amir Shpilka: On identity testing of tensors, low-rank recovery and compressed sensing. In Proc. 44th STOC, pp. 163–172. ACM Press, 2012. [doi:10.1145/2213977.2213995, arXiv:1111.0663]

[37]   Michael A. Forbes and Amir Shpilka: Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In Proc. 54th FOCS, pp. 243–252. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.34, arXiv:1209.2408]

[38]   Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson: Proof complexity lower bounds from algebraic circuit complexity. In Proc. 31st Conf. on Computational Complexity (CCC’16), pp. 32:1–32:17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.32, arXiv:1606.05050]

[39]   Michael A. Forbes, Amir Shpilka, and Ben Lee Volk: Succinct hitting sets and barriers to proving algebraic circuits lower bounds. In Proc. 49th STOC, pp. 653–664. ACM Press, 2017. [doi:10.1145/3055399.3055496, arXiv:1701.05328]

[40]   Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan: Lower bounds for depth-4 formulas computing Iterated Matrix Multiplication. SIAM J. Comput., 44(5):1173–1201, 2015. Conference version in STOC’14. [doi:10.1137/140990280]

[41]   Merrick L. Furst, James B. Saxe, and Michael Sipser: Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13–27, 1984. Conference version in FOCS’81. [doi:10.1007/BF01744431]

[42]   Ariel Gabizon and Ran Raz: Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415–440, 2008. Conference version in FOCS’05. [doi:10.1007/s00493-008-2259-3]

[43]   Oded Goldreich, Shafi Goldwasser, and Silvio Micali: How to construct random functions. J. ACM, 33(4):792–807, 1986. Conference version in FOCS’84. [doi:10.1145/6490.6503]

[44]   Joshua A. Grochow: Unifying known lower bounds via Geometric Complexity Theory. Comput. Complexity, 24(2):393–475, 2015. Conference version in CCC’14. [doi:10.1007/s00037-015-0103-x]

[45]   Joshua A. Grochow, Mrinal Kumar, Michael Saks, and Shubhangi Saraf: Towards an algebraic natural proofs barrier via polynomial identity testing. ECCC, 2017. [ECCC:TR17-009, arXiv:1701.01717]

[46]   Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao: Boundaries of VP and VNP. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16), pp. 34:1–34:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.34, arXiv:1605.02815]

[47]   Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi: Approaching the chasm at depth four. J. ACM, 61(6):33:1–33:16, 2014. Conference version in CCC’13. [doi:10.1145/2629541]

[48]   Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi: Arithmetic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064–1079, 2016. Conference version in FOCS’13. [doi:10.1137/140957123]

[49]   Rohit Gurjar, Arpita Korwar, and Nitin Saxena: Identity testing for constant-width, and any-order, read-once oblivious arithmetic branching programs. Theory of Computing, 13(2):1–21, 2017. Conference version in CCC’16. [doi:10.4086/toc.2017.v013a002, arXiv:1601.08031]

[50]   Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf: Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Comput. Complexity, 26(4):835–880, 2017. Conference version in CCC’15. [doi:10.1007/s00037-016-0141-z, arXiv:1411.7341]

[51]   Rohit Gurjar and Thomas Thierauf: Linear matroid intersection is in quasi-NC. In Proc. 49th STOC, pp. 821–830. ACM Press, 2017. [doi:10.1145/3055399.3055440]

[52]   Juris Hartmanis and Richard E. Stearns: On the computational complexity of algorithms. Trans. Amer. Math. Soc., 117:285–306, 1965. [doi:10.2307/1994208]

[53]   Johan Håstad: Almost optimal lower bounds for small depth circuits. In Proc. 18th STOC, pp. 6–20. ACM Press, 1986. [doi:10.1145/12130.12132]

[54]   Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby: A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999. [doi:10.1137/S0097539793244708]

[55]   Joos Heintz and Claus-Peter Schnorr: Testing polynomials which are easy to compute (Extended Abstract). In Proc. 12th STOC, pp. 262–272. ACM Press, 1980. [doi:10.1145/800141.804674]

[56]   Valentine Kabanets and Russell Impagliazzo: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complexity, 13(1–2):1–46, 2004. Conference version in STOC’03. [doi:10.1007/s00037-004-0182-6]

[57]   Zohar Shay Karnin and Amir Shpilka: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 31(3):333–364, 2011. Conference version in CCC’08. [doi:10.1007/s00493-011-2537-3]

[58]   Richard M. Karp and Richard J. Lipton: Turing machines that take advice. L’Enseignement Mathématique, 28(2):191–209, 1982. [doi:10.5169/seals-52237]

[59]   Neeraj Kayal: An exponential lower bound for the sum of powers of bounded degree polynomials. Electron. Colloq. on Comput. Complexity (ECCC), 2012. [ECCC:TR12-081]

[60]   Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan: An exponential lower bound for homogeneous depth four arithmetic circuits. SIAM J. Comput., 46(1):307–335, 2017. Conference version in FOCS’14. [doi:10.1137/151002423]

[61]   Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi: A super-polynomial lower bound for regular arithmetic formulas. In Proc. 46th STOC, pp. 146–153. ACM Press, 2014. [doi:10.1145/2591796.2591847]

[62]   Neeraj Kayal and Shubhangi Saraf: Blackbox polynomial identity testing for depth 3 circuits. In Proc. 50th FOCS, pp. 198–207. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.67]

[63]   Adam R. Klivans and Daniel A. Spielman: Randomness efficient identity testing of multivariate polynomials. In Proc. 33rd STOC, pp. 216–223. ACM Press, 2001. [doi:10.1145/380752.380801]

[64]   Pascal Koiran: Arithmetic circuits: The chasm at depth four gets wider. Theoret. Comput. Sci., 448:56–65, 2012. [doi:10.1016/j.tcs.2012.03.041]

[65]   Matthias Krause and Stefan Lucks: Pseudorandom functions in TC⁰ and cryptographic limitations to proving lower bounds. Comput. Complexity, 10(4):297–313, 2001. [doi:10.1007/s000370100002]

[66]   Mrinal Kumar and Shubhangi Saraf: On the power of homogeneous depth 4 arithmetic circuits. SIAM J. Comput., 46(1):336–387, 2017. Conference version in FOCS’14. [doi:10.1137/140999335, arXiv:1404.1950]

[67]   Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan: Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, 1992. Conference version in FOCS’90. [doi:10.1145/146585.146605]

[68]   Meena Mahajan and V. Vinay: A combinatorial algorithm for the determinant. In Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’97), pp. 730–738. ACM Press, 1997. ACM DL.

[69]   Raghu Meka and David Zuckerman: Pseudorandom generators for polynomial threshold functions. SIAM J. Comput., 42(3):1275–1301, 2013. Conference version in STOC’10. [doi:10.1137/100811623, arXiv:0910.4122]

[70]   Ketan D. Mulmuley: Geometric Complexity Theory V: Equivalence between blackbox derandomization of Polynomial Identity Testing and derandomization of Noether’s normalization lemma. J. Amer. Math. Soc., 30:225–309, 2017. Conference version in FOCS’12. [doi:10.1090/jams/864, arXiv:1209.5993]

[71]   Ketan D. Mulmuley and Milind Sohoni: Geometric Complexity Theory I: An approach to the PNP and related problems. SIAM J. Comput., 31(2):496–526, 2001. [doi:10.1137/S009753970038715X]

[72]   Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. Conference version in STOC’90. [doi:10.1137/0222053]

[73]   Moni Naor and Omer Reingold: Number-theoretic constructions of efficient pseudo-random functions. J. ACM, 51(2):231–262, 2004. Conference version in FOCS’97. [doi:10.1145/972639.972643]

[74]   Noam Nisan: Lower bounds for non-commutative computation. In Proc. 23rd STOC, pp. 410–418. ACM Press, 1991. [doi:10.1145/103418.103462]

[75]   Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991. [doi:10.1007/BF01375474]

[76]   Noam Nisan and Avi Wigderson: Hardness vs randomness. J. Comput. System Sci., 49(2):149–167, 1994. Conference version in FOCS’88. [doi:10.1016/S0022-0000(05)80043-1]

[77]   Noam Nisan and Avi Wigderson: Lower bounds on arithmetic circuits via partial derivatives. Comput. Complexity, 6(3):217–234, 1996. Conference version in FOCS’95. [doi:10.1007/BF01294256]

[78]   Rafael Oliveira, Amir Shpilka, and Ben Lee Volk: Subexponential size hitting sets for bounded depth multilinear formulas. Comput. Complexity, 25(2):455–505, 2016. Conference version in CCC’15. [doi:10.1007/s00037-016-0131-1, arXiv:1411.7492]

[79]   Ran Raz: Separation of multilinear circuit and formula size. Theory of Computing, 2(6):121–135, 2006. Conference version in FOCS’04. [doi:10.4086/toc.2006.v002a006]

[80]   Ran Raz: Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2):8:1–8:17, 2009. Conference version in STOC’04. [doi:10.1145/1502793.1502797]

[81]   Ran Raz: Elusive functions and lower bounds for arithmetic circuits. Theory of Computing, 6(7):135–177, 2010. Conference version in STOC’08. [doi:10.4086/toc.2010.v006a007]

[82]   Ran Raz and Amir Yehudayoff: Balancing syntactically multilinear arithmetic circuits. Comput. Complexity, 17(4):515–535, 2008. [doi:10.1007/s00037-008-0254-0]

[83]   Ran Raz and Amir Yehudayoff: Lower bounds and separations for constant depth multilinear circuits. Comput. Complexity, 18(2):171–207, 2009. Conference version in CCC’08. [doi:10.1007/s00037-009-0270-8]

[84]   Alexander Alexandrovich Razborov: Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk SSSR, 281(4):798–801, 1985. Available at author’s webpage.

[85]   Alexander Alexandrovich Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41(4):333–338, 1987. [doi:10.1007/BF01137685]

[86]   Alexander Alexandrovich Razborov and Steven Rudich: Natural proofs. J. Comput. System Sci., 55(1):24–35, 1997. Conference version in STOC’94. [doi:10.1006/jcss.1997.1494]

[87]   Ramprasad Saptharishi: Unified Approaches to Polynomial Identity Testing and Lower Bounds. Ph. D. thesis, Chennai Mathematical Institute, 2012. Available at author’s webpage.

[88]   Ramprasad Saptharishi: A survey of lower bounds in arithmetic circuit complexity, 2016. Available at Github.

[89]   Nitin Saxena: Progress on polynomial identity testing. Bulletin of the EATCS, 99:49–79, 2009. [ECCC:TR09-101]

[90]   Nitin Saxena: Progress on polynomial identity testing - II. In Perspectives in Computational Complexity, pp. 131–146. Springer, 2014. [doi:10.1007/978-3-319-05446-9_7, arXiv:1401.0976]

[91]   Nitin Saxena and C. Seshadhri: An almost optimal rank bound for depth-3 identities. SIAM J. Comput., 40(1):200–224, 2011. Conference version in CCC’09. [doi:10.1137/090770679]

[92]   Nitin Saxena and C. Seshadhri: Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn’t matter. SIAM J. Comput., 41(5):1285–1298, 2012. Conference version in STOC’11. [doi:10.1137/10848232, arXiv:1011.3234]

[93]   Nitin Saxena and C. Seshadhri: From Sylvester-Gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM, 60(5):33:1–33:33, 2013. Conference version in FOCS’10. [doi:10.1145/2528403]

[94]   Jacob T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, 1980. [doi:10.1145/322217.322225]

[95]   Adi Shamir: IP = PSPACE. J. ACM, 39(4):869–877, 1992. Conference version in FOCS’90. [doi:10.1145/146585.146609]

[96]   Amir Shpilka and Ilya Volkovich: Read-once polynomial identity testing. Comput. Complexity, 24(3):477–532, 2015. Conference version in STOC’08. [doi:10.1007/s00037-015-0105-8]

[97]   Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207–388, 2010. [doi:10.1561/0400000039]

[98]   Roman Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. 19th STOC, pp. 77–82. ACM Press, 1987. [doi:10.1145/28395.28404]

[99]   Volker Strassen: Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numerische Mathematik, 20(3):238–251, 1973. [doi:10.1007/BF01436566]

[100]   Éva Tardos: The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141–142, 1988. [doi:10.1007/BF02122563]

[101]   Sébastien Tavenas: Improved bounds for reduction to depth 4 and depth 3. Inform. and Comput., 240:2–11, 2015. Conference version in MFCS’13. [doi:10.1016/j.ic.2014.09.004, arXiv:1304.5777]

[102]   Leslie G. Valiant: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261. ACM Press, 1979. [doi:10.1145/800135.804419]

[103]   Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff: Fast parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641–644, 1983. Preliminary version in MFCS’81. [doi:10.1137/0212043]

[104]   R. Ryan Williams: Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2:1–2:32, 2014. Conference version in CCC’11. [doi:10.1145/2559903]

[105]   R. Ryan Williams: Natural proofs versus derandomization. SIAM J. Comput., 45(2):497–529, 2016. Conference version in STOC’13. [doi:10.1137/130938219, arXiv:1212.1891]

[106]   Andrew Chi-Chih Yao: Separating the polynomial-time hierarchy by oracles (Preliminary version). In Proc. 26th FOCS, pp. 1–10. IEEE Comp. Soc. Press, 1985. [doi:10.1109/SFCS.1985.49]

[107]   Richard Zippel: Probabilistic algorithms for sparse polynomials. In Proc. Internat. Symp. on Symbolic and Algebraic Computation (EUROSAM’79), pp. 216–226. Springer, 1979. [doi:10.1007/3-540-09519-5_73]