[1]   Scott Aaronson and Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595–605, 2004. [doi:10.1145/1008731.1008735]

[2]   Miklos Ajtai and Michael Ben-Or: A theorem on probabilistic constant depth computations. In Proc. 16th STOC, pp. 471–474. ACM Press, 1984. [doi:10.1145/800057.808715]

[3]   Eric Allender: A note on the power of threshold circuits. In Proc. 30th FOCS, pp. 580–584. IEEE Comp. Soc., 1989. [doi:10.1109/SFCS.1989.63538]

[4]   Andris Ambainis: Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing, 1(3):37–46, 2005. [doi:10.4086/toc.2005.v001a003]

[5]   László Babai, Péter Frankl, and Janos Simon: Complexity classes in communication complexity theory (preliminary version). In Proc. 27th FOCS, pp. 337–347. IEEE Comp. Soc., 1986. [doi:10.1109/SFCS.1986.15]

[6]   Paul Beame and Widad Machmouchi: The quantum query complexity of AC⁰. Quantum Inf. Comput., 12(7-8):670–676, 2012. [doi:10.26421/QIC12.7-8-11]

[7]   Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson: Bounded indistinguishability and the complexity of recovering secrets. In Proc. 36th Ann. Internat. Cryptology Conf. (CRYPTO’16), pp. 593–618. Springer, 2016. [doi:10.1007/978-3-662-53015-3_21, ECCC:TR15-182]

[8]   Andrej Bogdanov and Christopher Williamson: Approximate bounded indistinguishability. In Proc. 44th Internat. Colloq. on Automata, Languages, and Programming (ICALP’17), pp. 53:1–11. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ICALP.2017.53]

[9]   Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan: On the power of statistical zero knowledge. SIAM J. Comput., 49(4):FOCS17:1–58, 2019. Preliminary version in FOCS’17. [doi:10.1137/17M1161749, ECCC:TR16-140, arXiv:1609.02888]

[10]   Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka: Bounds for small-error and zero-error quantum algorithms. In Proc. 40th FOCS, pp. 358–368. IEEE Comp. Soc., 1999. [doi:10.1109/SFFCS.1999.814607, arXiv:cs/9904019]

[11]   Harry Buhrman, Nikolai K. Vereshchagin, and Ronald de Wolf: On computation and communication with small bias. In Proc. 22nd IEEE Conf. on Comput. Complexity (CCC’07), pp. 24–32. IEEE Comp. Soc., 2007. [doi:10.1109/CCC.2007.18]

[12]   Mark Bun, Robin Kothari, and Justin Thaler: The polynomial method strikes back: Tight quantum query bounds via dual polynomials. Theory of Computing, 16(10):1–71, 2020. Preliminary version in STOC’18. [doi:10.4086/toc.2020.v016a010]

[13]   Mark Bun and Justin Thaler: Dual lower bounds for approximate degree and Markov–Bernstein inequalities. Inform. Comput., 243:2–25, 2015. Preliminary version in ICALP’13. [doi:10.1016/j.ic.2014.12.003]

[14]   Mark Bun and Justin Thaler: Hardness amplification and the approximate degree of constant-depth circuits. In Proc. 42nd Internat. Colloq. on Automata, Languages, and Programming (ICALP’15), pp. 268–280. Springer, 2015. [doi:10.1007/978-3-662-47672-7_22, arXiv:1311.1616]

[15]   Mark Bun and Justin Thaler: Improved bounds on the sign-rank of AC⁰. In Proc. 43rd Internat. Colloq. on Automata, Languages, and Programming (ICALP’16), pp. 37:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.37]

[16]   Mark Bun and Justin Thaler: Approximate degree and the complexity of depth three circuits. In Proc. 22nd Internat. Workshop on Randomization and Computation (RANDOM’18), pp. 35:1–18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.35, ECCC:TR16-121]

[17]   Mark Bun and Justin Thaler: The large-error approximate degree of AC⁰. In Proc. 23rd Internat. Workshop on Randomization and Computation (RANDOM’19), pp. 55:1–16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.55]

[18]   Mark Bun and Justin Thaler: A nearly optimal lower bound on the approximate degree of AC⁰. SIAM J. Comput., 49(4):FOCS17:59–96, 2019. Preliminary version in FOCS’17. [doi:10.1137/17M1161737]

[19]   Kuan Cheng, Yuval Ishai, and Xin Li: Near-optimal secret sharing and error correcting codes in AC⁰. In Proc. Theory of Cryptography Conf. (TCC’17), pp. 424–458. Springer, 2017. [doi:10.1007/978-3-319-70503-3_14]

[20]   Vitaly Feldman: Evolvability from learning algorithms. In Proc. 40th STOC, pp. 619–628. ACM Press, 2008. [doi:10.1145/1374376.1374465]

[21]    Jürgen Forster: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. System Sci., 65(4):612–625, 2002. Preliminary version in CCC’01. [doi:10.1016/S0022-0000(02)00019-3]

[22]   Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon: Relations between communication complexity, linear arrangements, and computational complexity. In Proc. 21st Found. Softw. Techn. Theoret. Comp. Sci. Conf. (EFSTTCS’01), pp. 171–182. Springer, 2001. [doi:10.1007/3-540-45294-X_15]

[23]   Mikael Goldmann, Johan Håstad, and Alexander A. Razborov: Majority gates vs. general weighted threshold gates. Comput. Complexity, 2(4):277–300, 1992. [doi:10.1007/BF01200426]

[24]   András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario 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]

[25]   Jeff Kahn, Nathan Linial, and Alex Samorodnitsky: Inclusion-exclusion: Exact and approximate. Combinatorica, 16(4):465–477, 1996. [doi:10.1007/BF01271266]

[26]   Hartmut Klauck: Lower bounds for quantum communication complexity. SIAM J. Comput., 37(1):20–46, 2007. Preliminary version in FOCS’01. [doi:10.1137/S0097539702405620, arXiv:quant-ph/0106160]

[27]   Adam R. Klivans and Rocco A. Servedio: Learning DNF in time 2^Õ(n1∕3) . J. Comput. System Sci., 68(2):303–318, 2004. [doi:10.1016/j.jcss.2003.07.007]

[28]   Swastik Kopparty: AC⁰ lower bounds and pseudorandomness, 2013. Lecture notes of “Topics in Complexity Theory and Pseudorandomness (Spring 2013)” at Rutgers University.

[29]   Matthias Krause: On the computational power of Boolean decision lists. Comput. Complexity, 14(4):362–375, 2006. [doi:10.1007/s00037-005-0203-0]

[30]   Matthias Krause and Pavel Pudlák: On the computational power of depth-2 circuits with threshold and modulo gates. Theoret. Comput. Sci., 174(1–2):137–156, 1997. [doi:10.1016/S0304-3975(96)00019-9]

[31]   Troy Lee: A note on the sign degree of formulas, 2009. [arXiv:0909.4607]

[32]   Nati Linial and Adi Shraibman: Learning complexity vs communication complexity. Combin. Probab. Comput., 18(1–2):227–245, 2009. [doi:10.1017/S0963548308009656]

[33]   Marvin Minsky and Seymour Papert: Perceptrons: An Introduction to Computational Geometry. MIT Press, 1969. [doi:10.7551/mitpress/11301.001.0001]

[34]   Noam Nisan: The communication complexity of threshold gates. In Combinatorics, Paul Erds is Eighty, pp. 301–315. János Bolyai Math. Soc., Budapest, 1994.

[35]   Ryan O’Donnell and Rocco A. Servedio: New degree bounds for polynomial threshold functions. Combinatorica, 30(3):327–358, 2010. Preliminary version in STOC’03. [doi:10.1007/s00493-010-2173-3]

[36]   Ramamohan Paturi and Janos Simon: Probabilistic communication complexity. J. Comput. System Sci., 33(1):106–123, 1986. [doi:10.1016/0022-0000(86)90046-2]

[37]   Vladimir V. Podolskii: Perceptrons of large weight. Probl. Info. Transmission, 45:46–53, 2009. Preliminary version in CSR’07. [doi:10.1134/S0032946009010062]

[38]   Alexander A. Razborov and Alexander A. Sherstov: The sign-rank of AC⁰. SIAM J. Comput., 39(5):1833–1855, 2010. [doi:10.1137/080744037]

[39]   Alexander A. Sherstov: Separating AC⁰ from depth-2 majority circuits. SIAM J. Comput., 38(6):2113–2129, 2009. [doi:10.1137/08071421X]

[40]   Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 40(6):1969–2000, 2011. Preliminary version in STOC’08. [doi:10.1137/080733644]

[41]   Alexander A. Sherstov: Strong direct product theorems for quantum communication and query complexity. SIAM J. Comput., 41(5):1122–1165, 2012. Preliminary version in STOC’14. [doi:10.1137/110842661]

[42]   Alexander A. Sherstov: The intersection of two halfspaces has high threshold degree. SIAM J. Comput., 42(6):2329–2374, 2013. Preliminary version in FOCS’09. [doi:10.1137/100785260]

[43]   Alexander A. Sherstov: Breaking the Minsky-Papert barrier for constant-depth circuits. SIAM J. Comput., 47(5):1809–1857, 2018. Preliminary version in STOC’14. [doi:10.1137/15M1015704]

[44]   Alexander A. Sherstov: The power of asymmetry in constant-depth circuits. SIAM J. Comput., 47(6):2362–2434, 2018. Preliminary version in FOCS’15. [doi:10.1137/100785260]

[45]   Alexander A. Sherstov: Algorithmic polynomials. SIAM J. Comput., 49(6):1173–1231, 2020. Preliminary version in STOC’18. [doi:10.1137/19M1278831, arXiv:1801.04607]

[46]   Alexander A. Sherstov and Pei Wu: Near-optimal lower bounds on the threshold degree and sign-rank of AC⁰. SIAM J. Comput., online:STOC19:1–86, 2021. Preliminary version in STOC’19. [doi:10.1137/20M1312459, arXiv:1901.00988]

[47]   Yaoyun Shi and Yufan Zhu: Quantum communication complexity of block-composed functions. Quantum Inf. Comput., 9(5):444–460, 2009. [doi:10.26421/QIC9.5-6-7]

[48]   Leslie G. Valiant: Evolvability. J. ACM, 56(1):3:1–21, 2009. [doi:10.1145/1462153.1462156]

[49]   Emanuele Viola: On approximate majority and probabilistic time. Comput. Complexity, 18(3):337–375, 2009. Preliminary version in CCC’07. [doi:10.1007/s00037-009-0267-3]

[50]   Robert Špalek: A dual polynomial for OR, 2008. [arXiv:0803.4516]