[1]   Scott Aaronson: The polynomial method in quantum and classical computing. In Proc. 49th FOCS, p. 3. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.91]

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

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

[4]   Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang: Any AND-OR formula of size N can be evaluated in time N^1∕2+o(1) on a quantum computer. SIAM J. Comput., 39(6):2513–2530, 2010. Preliminary version in FOCS’07. [doi:10.1137/080712167]

[5]   James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich: The expressive power of voting polynomials. Combinatorica, 14(2):135–148, 1994. Preliminary version in STOC’91. [doi:10.1007/BF01215346]

[6]   Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary version in FOCS’98. [doi:10.1145/502090.502097]

[7]   Richard Beigel: The polynomial method in circuit complexity. In Proc. 8th IEEE Conf. on Structure in Complexity Theory (SCT’93), pp. 82–95. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SCT.1993.336538]

[8]   Richard Beigel: Perceptrons, PP, and the polynomial hierarchy. Comput. Complexity, 4(4):339–349, 1994. Preliminary version in SCT’92. [doi:10.1007/BF01263422]

[9]   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. Press, 1999. [doi:10.1109/SFFCS.1999.814607]

[10]   Harry Buhrman and Ronald de Wolf: Complexity measures and decision tree complexity: A survey. Theoret. Comput. Sci., 288(1):21–43, 2002. [doi:10.1016/S0304-3975(01)00144-X]

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

[12]   Harry Buhrman and Ronald de Wolf: Communication complexity lower bounds by polynomials. In Proc. 16th IEEE Conf. on Computational Complexity (CCC’01), pp. 120–130. IEEE Comp. Soc. Press, 2001. [doi:10.1109/CCC.2001.933879]

[13]   Mark Bun and Justin Thaler: Dual lower bounds for approximate degree and Markov-Bernstein inequalities. In Proc. 40th Internat. Colloq. on Automata, Languages and Programming (ICALP’13). Springer, 2013. To appear. Preprint available at arXiv.

[14]   Dmitry Gavinsky and Alexander A. Sherstov: A separation of NP and coNP in multiparty communication complexity. Theory of Computing, 6(1):227–245, 2010. [doi:10.4086/toc.2010.v006a010]

[15]   Peter Høyer, Michele Mosca, and Ronald de Wolf: Quantum search on bounded-error inputs. In Proc. 30th Internat. Colloq. on Automata, Languages and Programming (ICALP’03), pp. 291–299. Springer, 2003. [doi:10.1007/3-540-45061-0_25]

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

[17]   Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio: Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777–1805, 2008. Preliminary version in FOCS’05. [doi:10.1137/060649057]

[18]   Hartmut Klauck, Robert Špalek, and Ronald de Wolf: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM J. Comput., 36(5):1472–1493, 2007. Preliminary version in FOCS’04. [doi:10.1137/05063235X]

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

[20]   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. Preliminary version in STOC’94. [doi:10.1016/S0304-3975(96)00019-9]

[21]   Matthias Krause and Pavel Pudlák: Computing Boolean functions by polynomials and threshold circuits. Comput. Complexity, 7(4):346–370, 1998. Preliminary version in FOCS’95. [doi:10.1007/s000370050015]

[22]   Nathan Linial and Noam Nisan: Approximate inclusion-exclusion. Combinatorica, 10(4):349–365, 1990. Preliminary version in STOC’90. [doi:10.1007/BF02128670]

[23]   Marvin L. Minsky and Seymour A. Papert: Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, Mass., 1969.

[24]   Saburo Muroga: Threshold Logic and Its Applications. John Wiley & Sons, New York, 1971.

[25]   Noam Nisan and Mario Szegedy: On the degree of Boolean functions as real polynomials. Comput. Complexity, 4(4):301–313, 1994. Preliminary version in STOC’92. [doi:10.1007/BF01263419]

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

[27]   Ramamohan Paturi and Michael E. Saks: Approximating threshold circuits by rational functions. Inform. and Comput., 112(2):257–272, 1994. Preliminary version in FOCS’90. [doi:10.1006/inco.1994.1059]

[28]   Alexander A. Razborov: Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145–159, 2003. [doi:10.1070/IM2003v067n01ABEH000422]

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

[30]   Ben W. Reichardt: Reflections for quantum query algorithms. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 560–569. ACM Press, 2011. SIAM. [ACM:2133080]

[31]   Michael E. Saks: Slicing the hypercube. In Keith Walker, editor, Surveys in Combinatorics, 1993, volume 187 of London Mathematical Society Lecture Note Series, pp. 211–256. Cambridge Univ. Press, 1993. [doi:10.1017/CBO9780511662089.009]

[32]   Alexander A. Sherstov: Communication lower bounds using dual polynomials. Bulletin of the EATCS, 95:59–93, 2008. EATCS.

[33]   Alexander A. Sherstov: Approximate inclusion-exclusion for arbitrary symmetric functions. Comput. Complexity, 18(2):219–247, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0274-4]

[34]   Alexander A. Sherstov: The intersection of two halfspaces has high threshold degree. In Proc. 50th FOCS, pp. 343–362. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.18]

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

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

[37]   Alexander A. Sherstov: The multiparty communication complexity of set disjointness. In Proc. 44th STOC, pp. 525–548. ACM Press, 2012. [doi:10.1145/2213977.2214026]

[38]   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’11. [doi:10.1137/110842661]

[39]   Alexander A. Sherstov: Making polynomials robust to noise. Theory of Computing, 9(18):593–615, 2013. Preliminary version in STOC’12. [doi:10.4086/toc.2013.v009a018]

[40]   Yaoyun Shi: Approximating linear restrictions of Boolean functions. Manuscript. Available at author’s home page, 2002.

[41]   Kai-Yeung Siu, Vwani P. Roychowdhury, and Thomas Kailath: Rational approximation techniques for analysis of neural networks. IEEE Trans. Inform. Theory, 40(2):455–466, 1994. Preliminary version in NIPS’92. [doi:10.1109/18.312168]

[42]   Jun Tarui and Tatsuie Tsukiji: Learning DNF by approximating inclusion-exclusion formulae. In Proc. 14th IEEE Conf. on Computational Complexity (CCC’99), pp. 215–221. IEEE Comp. Soc. Press, 1999. [doi:10.1109/CCC.1999.766279]

[43]   Ronald de Wolf: A note on quantum algorithms and the minimal degree of ϵ-error polynomials for symmetric functions. Quantum Inf. Comput., 8(10):943–950, 2008. QIC. [ACM:2016989]