[1]   Leonard M. Adleman: Two theorems on random polynomial time. In Proc. 19th FOCS, pp. 75–83. IEEE Comp. Soc., 1978. [doi:10.1109/SFCS.1978.37]

[2]   Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger: Power from random strings. SIAM J. Comput., 35(6):1467–1493, 2006. [doi:10.1137/050628994]

[3]   Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks: Minimizing disjunctive normal form formulas and AC⁰ circuits given a truth table. SIAM J. Comput., 38(1):63–84, 2008. [doi:10.1137/060664537]

[4]   Eric Allender and Shuichi Hirahara: New insights on the (non-)hardness of circuit minimization and related problems. ACM Trans. Comput. Theory, 11(4):27:1–27, 2019. [doi:10.1145/3349616]

[5]   Eric Allender and Michal Koucký: Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1–36, 2010. [doi:10.1145/1706591.1706594]

[6]    László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complexity, 3(4):307–318, 1993. [doi:10.1007/BF01275486]

[7]   Manuel Blum and Silvio Micali: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13(4):850–864, 1984. [doi:10.1137/0213053]

[8]   Andrej Bogdanov and Luca Trevisan: On worst-case to average-case reductions for NP problems. SIAM J. Comput., 36(4):1119–1159, 2006. [doi:10.1137/S0097539705446974]

[9]   Allan Borodin, Alexander A. Razborov, and Roman Smolensky: On lower bounds for read-k-times branching programs. Comput. Complexity, 3(1):1–18, 1993. [doi:10.1007/BF01200404]

[10]   Harry Buhrman, Lance Fortnow, and Aduri Pavan: Some results on derandomization. Theory Computing Sys., 38(2):211–227, 2005. [doi:10.1007/s00224-004-1194-y]

[11]   Harry Buhrman, Lance Fortnow, and Rahul Santhanam: Unconditional lower bounds against advice. In Proc. 36th Internat. Colloq. on Automata, Languages, and Programming (ICALP’09), pp. 195–209. Springer, 2009. [doi:10.1007/978-3-642-02927-1_18]

[12]   Harry Buhrman and Steven Homer: Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In Proc. 12th Found. Softw. Techn. Theoret. Comp. Sci. Conf. (FSTTCS’92), pp. 116–127. Springer, 1992. [doi:10.1007/3-540-56287-7_99]

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

[14]   Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam: Beyond Natural Proofs: Hardness magnification and locality. J. ACM, 69(4):25:1–49, 2022. Preliminary version in ITCS’20. [doi:10.1145/3538391]

[15]   Lijie Chen, Ce Jin, and R. Ryan Williams: Hardness magnification for all sparse NP languages. In Proc. 60th FOCS, pp. 1240–1255. IEEE Comp. Soc., 2019. [doi:10.1109/FOCS.2019.00077]

[16]   Kuan Cheng and William M. Hoza: Hitting sets give two-sided derandomization of small space. Theory of Computing, 18(21):1–32, 2022. Preliminary version in CCC’20. [doi:10.4086/toc.2022.v018a021]

[17]   Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida: One-tape Turing machine and branching program lower bounds for MCSP. Theory Computing Sys., (10113-9):32 pages, 2022. Preliminary version in MFCS’21. [doi:10.1007/s00224-022-10113-9]

[18]   Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis: Circuit lower bounds for MCSP from local pseudorandom generators. ACM Trans. Comput. Theory, 12(3):21:1–27, 2020. Preliminary version in ICALP’19. [doi:10.1145/3404860]

[19]   Shimon Even, Alan L. Selman, and Yacov Yacobi: The complexity of promise problems with applications to public-key cryptography. Inform. Control, 61(2):159–173, 1984. [doi:10.1016/S0019-9958(84)80056-X]

[20]   Joan Feigenbaum and Lance Fortnow: Random-self-reducibility of complete sets. SIAM J. Comput., 22(5):994–1005, 1993. [doi:10.1137/0222061]

[21]   Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov: A better-than-3n lower bound for the circuit complexity of an explicit function. In Proc. 57th FOCS, pp. 89–98. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.19]

[22]   Michael A. Forbes and Zander Kelley: Pseudorandom generators for read-once branching programs, in any order. In Proc. 59th FOCS, pp. 946–955. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00093]

[23]   Lance Fortnow: Comparing notions of full derandomization. In Proc. 16th IEEE Conf. on Comput. Complexity (CCC’01), pp. 28–34. IEEE Comp. Soc., 2001. [doi:10.1109/CCC.2001.933869]

[24]   Oded Goldreich: On promise problems: A survey. In Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman, editors, Theoretical Computer Science, Essays in Memory of Shimon Even, pp. 254–290. Springer, 2006. [doi:10.1007/11685654_12]

[25]   Oded Goldreich: A sample of samplers: A computational perspective on sampling. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pp. 302–332. Springer, 2011. [doi:10.1007/978-3-642-22670-0_24]

[26]   Oded Goldreich, Shafi Goldwasser, and Silvio Micali: How to construct random functions. J. ACM, 33(4):792–807, 1986. [doi:10.1145/6490.6503]

[27]   Oded Goldreich and Avi Wigderson: On derandomizing algorithms that err extremely rarely. In Proc. 46th STOC, pp. 109–118. ACM Press, 2014. [doi:10.1145/2591796.2591808]

[28]   Oded Goldreich and Avi Wigderson: On the size of depth-three boolean circuits for computing multilinear functions. In Oded Goldreich, editor, Comput. Complexity and Property Testing, LNCS 12050, pp. 41–86. Springer Cham, 2020. (2013). [ECCC:TR13-043]

[29]   Johan Håstad: Computational limitations of small-depth circuits. Ph. D. thesis, MIT, 1986. Available on author’s website, published as a book by MIT Press, 1987.

[30]   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]

[31]   Alexander Healy, Salil P. Vadhan, and Emanuele Viola: Using nondeterminism to amplify hardness. SIAM J. Comput., 35(4):903–931, 2006. [doi:10.1137/S0097539705447281]

[32]   Shuichi Hirahara: Non-black-box worst-case to average-case reductions within NP. In Proc. 59th FOCS, pp. 247–258. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00032]

[33]   Shuichi Hirahara: Characterizing average-case complexity of PH by worst-case meta-complexity. In Proc. 61st FOCS, pp. 50–60. IEEE Comp. Soc., 2020. [doi:10.1109/FOCS46700.2020.00014]

[34]   Shuichi Hirahara: Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions. In Proc. 35th Comput. Complexity Conf. (CCC’20), pp. 20:1–47. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.20]

[35]   Shuichi Hirahara: Unexpected hardness results for Kolmogorov complexity under uniform reductions. In Proc. 52nd STOC, pp. 1038–1051. ACM Press, 2020. [doi:10.1145/3357713.3384251]

[36]   Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam: NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD circuits. In Proc. 33rd Comput. Complexity Conf. (CCC’18), pp. 5:1–31. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.5]

[37]   Shuichi Hirahara and Rahul Santhanam: On the average-case complexity of MCSP and its variants. In Proc. 32nd Comput. Complexity Conf. (CCC’17), pp. 7:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.7]

[38]   Shuichi Hirahara and Osamu Watanabe: Limits of Minimum Circuit Size Problem as oracle. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 18:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.18]

[39]   Shuichi Hirahara and Osamu Watanabe: On nonadaptive security reductions of hitting set generators. In Proc. 24th Internat. Conf. on Randomization and Computation (RANDOM’20), pp. 15:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.APPROX/RANDOM.2020.15]

[40]   John M. Hitchcock and Aduri Pavan: On the NP-completeness of the Minimum Circuit Size Problem. In Proc. 35th Found. Softw. Techn. Theoret. Comp. Sci. Conf. (FSTTCS’15), pp. 236–245. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.FSTTCS.2015.236]

[41]   Russell Impagliazzo: Hard-core distributions for somewhat hard problems. In Proc. 36th FOCS, pp. 538–545. IEEE Comp. Soc., 1995. [doi:10.1109/SFCS.1995.492584]

[42]   Russell Impagliazzo: A personal view of average-case complexity. In Proc. 10th IEEE Conf. Structure in Complexity Theory (SCT’95), pp. 134–147. IEEE Comp. Soc., 1995. [doi:10.1109/SCT.1995.514853]

[43]   Russell Impagliazzo: Relativized separations of worst-case and average-case complexities for NP. In Proc. 26th IEEE Conf. on Comput. Complexity (CCC’11), pp. 104–114. IEEE Comp. Soc., 2011. [doi:10.1109/CCC.2011.34]

[44]   Russell Impagliazzo and Avi Wigderson: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proc. 29th STOC, pp. 220–229. ACM Press, 1997. [doi:10.1145/258533.258590]

[45]   Valentine Kabanets and Jin-yi Cai: Circuit minimization problem. In Proc. 32nd STOC, pp. 73–79. ACM Press, 2000. [doi:10.1145/335305.335314]

[46]   Richard M. Karp and Richard J. Lipton: Turing machines that take advice. Enseign. Math., 28:191–209, 1982. [doi:10.5169/seals-52237]

[47]   Adam R. Klivans and Rocco A. Servedio: Boosting and hard-core set construction. Machine Learning, 51(3):217–238, 2003. [doi:10.1023/A:1022949332276]

[48]   Adam R. Klivans and Dieter van Melkebeek: Graph nonisomorphism has subexponential size proofs unless the Polynomial-time Hierarchy collapses. SIAM J. Comput., 31(5):1501–1526, 2002. [doi:10.1137/S0097539700389652]

[49]   Ker-I Ko: On the complexity of learning minimum time-bounded Turing machines. SIAM J. Comput., 20(5):962–986, 1991. [doi:10.1137/0220059]

[50]   Leonid A. Levin: Randomness conservation inequalities; Information and independence in mathematical theories. Inform. Control, 61(1):15–37, 1984. [doi:10.1016/S0019-9958(84)80060-1]

[51]   Leonid A. Levin: Average case complete problems. SIAM J. Comput., 15(1):285–286, 1986. [doi:10.1137/0215020]

[52]   William J. Masek: Some NP-complete set covering problems. Master’s thesis, MIT CS Lab, 1978. Cited in the NP-completeness column by David Johnson.

[53]   Dylan M. McKay, Cody D. Murray, and R. Ryan Williams: Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In Proc. 51st STOC, pp. 1215–1225. ACM Press, 2019. [doi:10.1145/3313276.3316396]

[54]   Cody D. Murray and R. Ryan Williams: On the (non) NP-hardness of computing circuit complexity. Theory of Computing, 13(4):1–22, 2017. [doi:10.4086/toc.2017.v013a004]

[55]   Noam Nisan: Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. [doi:10.1007/BF01305237]

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

[57]   Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam: Hardness magnification near state-of-the-art lower bounds. Theory of Computing, 17(11):1–38, 2021. Preliminary version in CCC’19. [doi:10.4086/toc.2021.v017a011]

[58]   Igor Carboni Oliveira and Rahul Santhanam: Hardness magnification for natural problems. In Proc. 59th FOCS, pp. 65–76. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00016]

[59]   Rafail Ostrovsky: One-way functions, hard on average problems, and statistical zero-knowledge proofs. In Proc. 6th IEEE Conf. Structure in Complexity Theory (SCT’91), pp. 133–138. IEEE Comp. Soc., 1991. [doi:10.1109/SCT.1991.160253]

[60]   Aduri Pavan, Rahul Santhanam, and N. V. Vinodchandran: Some results on average-case hardness within the Polynomial Hierarchy. In Proc. 26th Found. Softw. Techn. Theoret. Comp. Sci. Conf. (FSTTCS’06), pp. 188–199. Springer, 2006. [doi:10.1007/11944836_19]

[61]   Ran Raz, Omer Reingold, and Salil P. Vadhan: Extracting all the randomness and reducing the error in Trevisan’s extractors. J. Comput. System Sci., 65(1):97–128, 2002. [doi:10.1006/jcss.2002.1824]

[62]   Alexander A. Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math. Notes. Acad. Sci. USSR (English translation), 41(4):333–338, 1987. [doi:10.1007/BF01137685]

[63]   Alexander A. Razborov and Steven Rudich: Natural Proofs. J. Comput. System Sci., 55(1):24–35, 1997. [doi:10.1006/jcss.1997.1494]

[64]   Omer Reingold, Luca Trevisan, and Salil P. Vadhan: Notions of reducibility between cryptographic primitives. In Proc. Theory of Cryptography Conf. (TCC’04), pp. 1–20. Springer, 2004. [doi:10.1007/978-3-540-24638-1_1]

[65]   Rahul Santhanam: Pseudorandomness and the Minimum Circuit Size Problem. In Proc. 11th Innovations in Theoret. Comp. Sci. Conf. (ITCS’20), pp. 68:1–26. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ITCS.2020.68]

[66]   Ronen Shaltiel and Emanuele Viola: Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122–3154, 2010. [doi:10.1137/080735096]

[67]   Madhu Sudan: Decoding of Reed Ssolomon codes beyond the error-correction bound. J. Complexity, 13(1):180–193, 1997. [doi:10.1006/jcom.1997.0439]

[68]   Madhu Sudan, Luca Trevisan, and Salil P. Vadhan: Pseudorandom generators without the XOR lemma. J. Comput. System Sci., 62(2):236–266, 2001. [doi:10.1006/jcss.2000.1730]

[69]   Boris A. Trakhtenbrot: A survey of Russian approaches to Perebor (brute-force searches) algorithms. IEEE Annals of the History of Computing, 6(4):384–400, 1984. [doi:10.1109/MAHC.1984.10036]

[70]    Luca Trevisan: List-decoding using the XOR lemma. In Proc. 44th FOCS, pp. 126–135. IEEE Comp. Soc., 2003. [doi:10.1109/SFCS.2003.1238187]

[71]   Luca Trevisan and Salil P. Vadhan: Pseudorandomness and average-case complexity via uniform reductions. Comput. Complexity, 16(4):331–364, 2007. [doi:10.1007/s00037-007-0233-x]

[72]   Luca Trevisan and Tongke Xue: A derandomized Switching Lemma and an improved derandomization of AC0. In Proc. 28th IEEE Conf. on Comput. Complexity (CCC’13), pp. 242–247. IEEE Comp. Soc., 2013. [doi:10.1109/CCC.2013.32]

[73]   Salil P. Vadhan: An unconditional study of Computational Zero Knowledge. SIAM J. Comput., 36(4):1160–1214, 2006. [doi:10.1137/S0097539705447207]

[74]   Salil P. Vadhan: Pseudorandomness. Found. Trends Theor. Comp. Sci., 7(1–3):1–336, 2012. [doi:10.1561/0400000010]

[75]   Leslie G. Valiant and Vijay V. Vazirani: NP is as easy as detecting unique solutions. Theoret. Comput. Sci., 47:85–93, 1986. [doi:10.1016/0304-3975(86)90135-0]

[76]   Emanuele Viola: The complexity of constructing pseudorandom generators from hard functions. Comput. Complexity, 13(3–4):147–188, 2005. [doi:10.1007/s00037-004-0187-1]

[77]   Andrew Chi-Chih Yao: Theory and applications of trapdoor functions (extended abstract). In Proc. 23rd FOCS, pp. 80–91. IEEE Comp. Soc., 1982. [doi:10.1109/SFCS.1982.45]

[78]   Sergey Yekhanin: Locally decodable codes. Found. Trends Theor. Comp. Sci., 6(3):139–255, 2012. [doi:10.1561/0400000030]