[1]   Amir Abboud, R. Ryan Williams, and Huacheng Yu: More applications of the polynomial method to algorithm design. In Proc. 26th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’15), pp. 218–230. SIAM, 2015. [doi:10.1137/1.9781611973730.17]

[2]   Miklós Ajtai: A non-linear time lower bound for Boolean branching programs. Theory of Computing, 1(8):149–176, 2005. [doi:10.4086/toc.2005.v001a008]

[3]   Josh Alman, Timothy M. Chan, and R. Ryan Williams: Polynomial representations of threshold functions and algorithmic applications. In Proc. 57th FOCS, pp. 467–476. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.57]

[4]   Josh Alman and Lijie Chen: Efficient construction of rigid matrices using an NP oracle. SIAM J. Comput., 54(4):102–134, 2025. Preliminary version in FOCS’19. [doi:10.1137/20M1322297]

[5]   Josh Alman and R. Ryan Williams: Probabilistic polynomials and Hamming nearest neighbors. In Proc. 56th FOCS, pp. 136–150. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.18]

[6]   Josh Alman and R. Ryan Williams: Probabilistic rank and matrix rigidity. In Proc. 49th STOC, pp. 641–652. ACM Press, 2017. [doi:10.1145/3055399.3055484]

[7]   Sanjeev Arora and Boaz Barak: Computational Complexity: A modern approach. Cambridge Univ. Press, 2009. [doi:10.1017/CBO9780511804090]

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

[9]   László Babai, Noam Nisan, and Márió Szegedy: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. System Sci., 45(2):204–232, 1992. [doi:10.1016/0022-0000(92)90047-M]

[10]   Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee: Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM, 50(2):154–195, 2003. [doi:10.1145/636865.636867]

[11]   Richard Beigel and Jun Tarui: On ACC. Comput. Complexity, 4(4):350–366, 1994. [doi:10.1007/BF01263423]

[12]   Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan: Short PCPs verifiable in polylogarithmic time. In Proc. 20th IEEE Conf. on Comput. Complexity (CCC’05), pp. 120–134. IEEE Comp. Soc., 2005. [doi:10.1109/CCC.2005.27]

[13]   Eli Ben-Sasson and Madhu Sudan: Short PCPs with polylog query complexity. SIAM J. Comput., 38(2):551–607, 2008. [doi:10.1137/050646445]

[14]   Eli Ben-Sasson and Emanuele Viola: Short PCPs with projection queries. In picalp14, pp. 163–173, 2014. [doi:10.1007/978-3-662-43948-7_14]

[15]   Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal: Rigid matrices from rectangular PCPs. In Proc. 61st FOCS, pp. 858–869. IEEE Comp. Soc., 2020. [doi:10.1109/FOCS46700.2020.00084]

[16]   Andrej Bogdanov and Emanuele Viola: Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464–2486, 2010. Preliminary version in FOCS’07. [doi:10.1137/070712109]

[17]   Timothy M. Chan and R. Ryan Williams: Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky. In Proc. 27th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’16), pp. 1246–1255. SIAM, 2016. [doi:10.1137/1.9781611974331.87]

[18]   Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton: Multi-party protocols. In Proc. 15th STOC, pp. 94–99. ACM Press, 1983. [doi:10.1145/800061.808737]

[19]   Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty: Fractional pseudorandom generators from any Fourier level, 2021. [doi:10.4230/LIPIcs.CCC.2021.10, arXiv:2008.01316]

[20]   Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett: Pseudorandom generators from polarizing random walks. In Proc. 33rd Comput. Complexity Conf. (CCC’18), pp. 1:1–21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.1, arXiv:2008.01316]

[21]    Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal: Pseudorandom generators from the second fourier level and applications to AC0 with parity gates. In Proc. 10th Innovations in Theoret. Comp. Sci. Conf. (ITCS’19), pp. 22:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.22]

[22]   Lijie Chen: Non-deterministic quasi-polynomial time is average-case hard for ACC circuits. In Proc. 60th FOCS, pp. 1281–1304. IEEE Comp. Soc., 2019. [doi:10.1109/FOCS.2019.00079]

[23]   Lijie Chen, Xin Lyu, and R. Ryan Williams: Almost everywhere circuit lower bounds from non-trivial derandomization. In Proc. 61st FOCS. IEEE Comp. Soc., 2020. [doi:10.1109/FOCS46700.2020.00009]

[24]   Lijie Chen and Hanlin Ren: Strong average-case circuit lower bounds from non-trivial derandomization. SIAM J. Comput., 51(3):115–173, 2022. Preliminary version in STOC’20. [doi:10.1137/20M1364886]

[25]   Lijie Chen and R. Ryan Williams: Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 19:1–43. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.19]

[26]   Ruiwen Chen, Igor Carboni Oliveira, and Rahul Santhanam: An average-case lower bound against acc⁰. In Proc. Latin American Symp. on Theoretical Informatics (LATIN’18), pp. 317–330. Springer, 2018. [doi:10.1007/978-3-319-77404-6_24]

[27]   Fan R. K. Chung and Prasad Tetali: Communication complexity and quasi randomness. SIAM J. Discr. Math., 6(1):110–123, 1993. [doi:10.1137/0406009]

[28]   Stephen A. Cook: A hierarchy for nondeterministic time complexity. J. Comput. System Sci., 7(4):343–353, 1973. [doi:10.1016/S0022-0000(73)80028-5]

[29]   Henry Corrigan-Gibbs and Dmitry Kogan: The function-inversion problem: Barriers and opportunities. Electron. Colloq. Comput. Complexity, TR18-182, 2018. [ECCC]

[30]   Zeev Dvir, Alexander Golovnev, and Omri Weinstein: Static data structure lower bounds imply rigidity. In Proc. 51st STOC, pp. 967–978. ACM Press, 2019. [doi:10.1145/3313276.3316348]

[31]   Oded Goldreich, Noam Nisan, and Avi Wigderson: On Yao’s XOR lemma. In Studies in Complexity and Cryptography, LNCS 6650, pp. 273–301. Springer, 2011. Preliminary version ECCC TR95–050 (1995). [doi:10.1007/978-3-642-22670-0_23]

[32]   Alexander Golovnev, Alexander S. Kulikov, and R. Ryan Williams: Circuit depth reductions. In Proc. 12th Innovations in Theoret. Comp. Sci. Conf. (ITCS’21), pp. 24:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. Preliminary version in ECCC TR18–192 (2018–2020). [doi:10.4230/LIPIcs.ITCS.2021.24]

[33]   Aryeh Grinberg, Ronen Shaltiel, and Emanuele Viola: Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. In Proc. 59th FOCS, pp. 956–966. IEEE Comp. Soc., 2018. Available at author’s website. [doi:10.1109/FOCS.2018.00094]

[34]   András Hajnal, Wolfgang Maass, Pavel Pudlák, Márió Szegedy, and György Turán: Threshold circuits of bounded depth. J. Comput. System Sci., 46(2):129–154, 1993. [doi:10.1016/0022-0000(93)90001-D]

[35]   Johan Håstad: Computational Limitations of Small-Depth Circuits. MIT Press, 1987. Available at DSpace@MIT.

[36]   Johan Håstad and Mikael Goldmann: On the power of small-depth threshold circuits. Comput. Complexity, 1(2):113–129, 1991. [doi:10.1007/BF01272517]

[37]   Xuangui Huang and Emanuele Viola: Average-case rigidity lower bounds. In Proc. 16th Comp. Sci. Symp. in Russia (CSR’21), pp. 186–205. Springer, 2021. Available at author’s website.

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

[39]   Hamid Jahanjou, Eric Miles, and Emanuele Viola: Local reductions. Inform. Comput., 261(2):281–295, 2018. Preliminary version in ICALP15, available at author’s website. [doi:10.1016/j.ic.2018.02.009]

[40]   Stasys Jukna: Boolean Function Complexity: Advances and Frontiers. Springer, 2012. [doi:10.1007/978-3-642-24508-4]

[41]   Adam R. Klivans: On the derandomization of constant depth circuits. In Proc. 5th Internat. Workshop on Randomization and Computation (RANDOM’01), pp. 249–260. Springer, 2001. [doi:10.1007/3-540-44666-4_28]

[42]   Swastik Kopparty and Srikanth Srinivasan: Certifying polynomials for AC[] circuits, with applications to lower bounds and circuit compression. Theory of Computing, 14(12):1–24, 2018. [doi:10.4086/toc.2018.v014a012]

[43]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge Univ. Press, 1997. [doi:10.1017/CBO9780511574948]

[44]   Satyanarayana V. Lokam: Complexity lower bounds using linear algebra. Found. Trends Theor. Comp. Sci., 4(1–2):1–155, 2009. [doi:10.1561/0400000011]

[45]   Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, and Huacheng Yu: Beating brute force for systems of polynomial equations over finite fields. In Proc. 28th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’17), pp. 2190–2202. SIAM, 2017. [doi:10.1137/1.9781611974782.143]

[46]   Shachar Lovett: Unconditional pseudorandom generators for low-degree polynomials. Theory of Computing, 5(3):69–82, 2009. [doi:10.4086/toc.2009.v005a003]

[47]   Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson: On data structures and asymmetric communication complexity. J. Comput. System Sci., 57(1):37–49, 1998. [doi:10.1006/jcss.1998.1577]

[48]   Cody D. Murray and R. Ryan Williams: Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma. SIAM J. Comput., 49(5):300–322, 2020. Preliminary version in STOC’18. [doi:10.1137/18M1195887]

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

[50]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014. [doi:10.1017/CBO9781139814782]

[51]   Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan: Parity helps to compute majority. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 23:1–17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.23]

[52]   Orr Paradise: Smooth and strong PCPs. Comput. Complexity, 30(1):1–77, 2021. Preliminary version in ITCS’20 and ECCC TR19-023. [doi:10.1007/s00037-020-00199-3]

[53]   Ninad Rajgopal, Rahul Santhanam, and Srikanth Srinivasan: Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds. In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCS’18), pp. 78:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.MFCS.2018.78]

[54]   Sivaramakrishnan Natarajan Ramamoorthy and Cyrus Rashtchian: Equivalence of systematic linear data structures and matrix rigidity. In Proc. 11th Innovations in Theoret. Comp. Sci. Conf. (ITCS’20), pp. 35:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ITCS.2020.35]

[55]   Anup Rao and Amir Yehudayoff: Communication Complexity. Cambridge Univ. Press, 2019. [doi:10.1017/9781108671644]

[56]   Ran Raz: The BNS-Chung criterion for multi-party communication complexity. Comput. Complexity, 9(2):113–122, 2000. [doi:10.1007/PL00001602]

[57]   Alexander 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. Russian original available at Mathnet.ru. [doi:10.1007/BF01137685]

[58]   Alexander Razborov: On rigid matrices (Russian), 1989. Available in Russian at author’s website.

[59]   Joel I. Seiferas, Michael J. Fischer, and Albert R. Meyer: Separating nondeterministic time complexity classes. J. ACM, 25(1):146–167, 1978. [doi:10.1145/322047.322061]

[60]   Rocco A. Servedio and Emanuele Viola: On a special case of rigidity. Electron. Colloq. Comput. Complexity, TR12-144, 2012. Update available at author’s website. [ECCC]

[61]   Ronen Shaltiel and Emanuele Viola: Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122–3154, 2010. Preliminary version in STOC’08. [doi:10.1137/080735096]

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

[63]   Roman Smolensky: On representations by low-degree polynomials. In Proc. 34th FOCS, pp. 130–138. IEEE Comp. Soc., 1993. [doi:10.1109/SFCS.1993.366874]

[64]   Srikanth Srinivasan: On improved degree lower bounds for polynomial approximation. In Proc. 33rd Found. Softw. Techn. Theoret. Comp. Sci. Conf. (FSTTCS’13), pp. 201–212. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2013. [doi:10.4230/LIPIcs.FSTTCS.2013.201]

[65]   Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh: On the probabilistic degrees of symmetric Boolean functions. SIAM J. Discr. Math., 35(3):2070–2092, 2021. [doi:10.1137/19M129416, arXiv:1910.02465]

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

[67]   Suguru Tamaki: A satisfiability algorithm for depth two circuits with a sub-quadratic number of symmetric and threshold gates. Electron. Colloq. Comput. Complexity, TR16-100, 2016. [ECCC]

[68]   Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCS’77), pp. 162–176. Springer, 1977. [doi:10.1007/3-540-08353-7_135]

[69]   Emanuele Viola: The complexity of hardness amplification and derandomization. Electron. Colloq. Comput. Complexity, 2006. PhD Thesis, Harvard University. Available at ECCC and author’s website.

[70]   Emanuele Viola: New correlation bounds for GF(2) polynomials using Gowers uniformity. Electron. Colloq. Comput. Complexity, TR06-097, 2006. [ECCC]

[71]   Emanuele Viola: On the power of small-depth computation. Found. Trends Theor. Comp. Sci., 5(1):1–72, 2009. [doi:10.1561/0400000033]

[72]   Emanuele Viola: The sum of d small-bias generators fools polynomials of degree d. Comput. Complexity, 18(2):209–217, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0273-5]

[73]   Emanuele Viola: Challenges in computational lower bounds. SIGACT News, Open Problems Column, 48(1), 2017. [doi:10.1145/3061640.3061648]

[74]   Emanuele Viola: Constant-error pseudorandomness proofs from hardness require majority. ACM Trans. Comput. Theory, 11(4):19:1–11, 2019. Available at author’s website. [doi:10.1145/3322815]

[75]   Emanuele Viola: Lower bounds for data structures with space close to maximum imply circuit lower bounds. Theory of Computing, 15(18):1–9, 2019. [doi:10.4086/toc.2019.v015a018]

[76]   Emanuele Viola: Fourier conjectures, correlation bounds, and Majority. In Proc. 48th Internat. Colloq. on Automata, Languages, and Programming (ICALP’21), pp. 111:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPICS.ICALP.2021.111]

[77]   Emanuele Viola: New lower bounds for probabilistic degree and ac0 with parity gates. Electron. Colloq. Comput. Complexity, TR20-015, 2021. [ECCC]

[78]   Emanuele Viola and Avi Wigderson: Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing, 4(7):137–168, 2008. Preliminary version in CCC’07. [doi:10.4086/toc.2008.v004a007]

[79]   Nikhil Vyas and R. Ryan Williams: Lower bounds against sparse symmetric functions of ACC circuits: Expanding the reach of #SAT algorithms. In Proc. 37th Symp. Theoret. Aspects of Comp. Sci. (STACS’20), pp. 59:1–17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.STACS.2020.59]

[80]   R. Ryan Williams: Guest column: A casual tour around a circuit complexity bound. SIGACT News, 42(3):54–76, 2011. [doi:10.1145/2034575.2034591]

[81]   R. Ryan Williams: Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218–1244, 2013. [doi:10.1137/10080703X]

[82]   R. Ryan Williams: Natural proofs versus derandomization. In Proc. 45th STOC, pp. 21–30. ACM Press, 2013. [doi:10.1145/2488608.2488612]

[83]   R. Ryan Williams: New algorithms and lower bounds for circuits with linear threshold gates. In Proc. 46th STOC, pp. 194–202. ACM Press, 2014. [doi:10.1145/2591796.2591858]

[84]   R. Ryan Williams: Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2:1–32, 2014. [doi:10.1145/2559903]

[85]   R. Ryan Williams: Limits on representing Boolean functions by linear combinations of simple functions: Thresholds, relus, and low-degree polynomials. In Proc. 33rd Comput. Complexity Conf. (CCC’18), pp. 6:1–24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.CCC.2018.6]

[86]   Henning Wunderlich: On a theorem of Razborov. Comput. Complexity, 21(3):431–477, 2012. [doi:10.1007/s00037-011-0021-5]

[87]   Andrew Chi-Chih Yao: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In Proc. 18th FOCS, pp. 222–227. IEEE Comp. Soc., 1977. [doi:10.1109/SFCS.1977.24]

[88]   Andrew Chi-Chih Yao: On ACC and threshold circuits. In Proc. 31st FOCS, pp. 619–627. IEEE Comp. Soc., 1990. [doi:10.1109/FSCS.1990.89583]

[89]   Stanislav Zák: A Turing machine time hierarchy. Theoret. Comput. Sci., 26:327–333, 1983. [doi:10.1016/0304-3975(83)90015-4]