[1]   Scott Aaronson: Limitations of quantum advice and one-way communication. Theory of Computing, 1(1):1–28, 2005. Preliminary version in CCC’04. [doi:10.4086/toc.2005.v001a001]

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

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

[5]   Paul Beame and Dang-Trinh Huynh-Ngoc: Multiparty communication complexity and threshold circuit size of AC⁰. SIAM Journal on Computing, 41(3):484–518, 2012. Preliminary version in FOCS’09. [doi:10.1137/100792779]

[6]   Richard Beigel, Nick Reingold, and Daniel A. Spielman: PP is closed under intersection. J. Comput. System Sci., 50(2):191–202, 1995. Preliminary version in STOC’91. [doi:10.1006/jcss.1995.1017]

[7]   Mark Braverman and Anup Rao: Towards coding for maximum errors in interactive communication. In Proc. 43rd STOC, pp. 159–166. ACM Press, 2011. [doi:10.1145/1993636.1993659]

[8]   Harry Buhrman, Richard Cleve, and Avi Wigderson: Quantum vs. classical communication and computation. In Proc. 30th STOC, pp. 63–68. ACM Press, 1998. [doi:10.1145/276698.276713]

[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, Ilan Newman, Hein Röhrig, and Ronald de Wolf: Robust polynomials and quantum algorithms. Theory Comput. Syst., 40(4):379–395, 2007. Preliminary version in STACS’05. [doi:10.1007/s00224-006-1313-z]

[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. (See also SAGA’07.). [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]   Elliott W. Cheney: Introduction to Approximation Theory. Chelsea Publishing, New York, 2nd edition, 1982.

[14]   Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, and Jaikumar Radhakrishnan: A tight lower bound for parity in noisy communication networks. In Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’08), pp. 1056–1065. ACM Press, 2008. [ACM:1347198]

[15]   Chinmoy Dutta and Jaikumar Radhakrishnan: Lower bounds for noisy wireless networks using sampling algorithms. In Proc. 49th FOCS, pp. 394–402. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.72]

[16]   Alexandre Eremenko and Peter Yuditskii: Uniform approximation of sgn x by polynomials and entire functions. J. d’Analyse Mathématique, 101(1):313–324, 2007. [doi:10.1007/s11854-007-0011-3]

[17]   William S. Evans and Nicholas Pippenger: Average-case lower bounds for noisy Boolean decision trees. SIAM J. Comput., 28(2):433–446, 1998. Preliminary version in STOC’96. [doi:10.1137/S0097539796310102]

[18]   William S. Evans and Leonard J. Schulman: Signal propagation and noisy circuits. IEEE Trans. Inform. Theory, 45(7):2367–2373, 1999. Preliminary version in FOCS’93. [doi:10.1109/18.796377]

[19]   Uriel Feige: On the complexity of finite random functions. Inform. Process. Lett., 44(6):295–296, 1992. [doi:10.1016/0020-0190(92)90102-2]

[20]   Uriel Feige and Joe Kilian: Finding OR in a noisy broadcast network. Inform. Process. Lett., 73(1-2):69–75, 2000. [doi:10.1016/S0020-0190(00)00002-8]

[21]   Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal: Computing with noisy information. SIAM J. Comput., 23(5):1001–1018, 1994. Preliminary version in STOC’90. [doi:10.1137/S0097539791195877]

[22]   Péter Gács and Anna Gál: Lower bounds for the complexity of reliable Boolean circuits with noisy gates. IEEE Trans. Inform. Theory, 40(2):579–583, 1994. Preliminary version in FOCS’91. [doi:10.1109/18.312190]

[23]   Robert G. Gallager: Finding parity in a simple broadcast network. IEEE Trans. Inform. Theory, 34(2):176–180, 1988. [doi:10.1109/18.2626]

[24]   Ran Gelles, Ankur Moitra, and Amit Sahai: Efficient and explicit coding for interactive communication. In Proc. 52nd FOCS, pp. 768–777. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.51]

[25]   Navin Goyal, Guy Kindler, and Michael E. Saks: Lower bounds for the noisy broadcast problem. SIAM J. Comput., 37(6):1806–1841, 2008. Preliminary version in FOCS’05. [doi:10.1137/060654864]

[26]   Ronald L. Graham, Donald E. Knuth, and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Boston, Mass., USA, 2nd edition, 1994.

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

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

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

[30]   Daniel J. Kleitman, Frank Thomson Leighton, and Yuan Ma: On the design of reliable Boolean circuits that contain partially unreliable gates. J. Comput. System Sci., 55(3):385–401, 1997. Preliminary version in FOCS’94. [doi:10.1006/jcss.1997.1531]

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

[32]    Adam R. Klivans and Alexander A. Sherstov: Unconditional lower bounds for learning intersections of halfspaces. Machine Learning, 69(2-3):97–114, 2007. Preliminary version in COLT’06. [doi:10.1007/s10994-007-5010-1]

[33]    Adam R. Klivans and Alexander A. Sherstov: Lower bounds for agnostic learning via approximate rank. Comput. Complexity, 19(4):581–604, 2010. Preliminary version in COLT’07. [doi:10.1007/s00037-010-0296-y]

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

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

[36]   Eyal Kushilevitz and Yishay Mansour: Computation in noisy radio networks. SIAM J. Discrete Math., 19(1):96–108, 2005. Preliminary version in SODA’98. [doi:10.1137/S0895480103434063]

[37]   Vladimir A. Markov: On functions of least deviation from zero in a given interval. Russian Academy of Sciences, St. Petersburg, 1892. In Russian.

[38]   Ilan Newman: Computing in fault tolerant broadcast networks and noisy decision trees. Random Structures & Algorithms, 34(4):478–501, 2009. Preliminary version in CCC’04. [doi:10.1002/rsa.20240]

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

[40]   Nicholas Pippenger: On networks of noisy gates. In Proc. 26th FOCS, pp. 30–38. IEEE Comp. Soc. Press, 1985. [doi:10.1109/SFCS.1985.41]

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

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

[43]   Rüdiger Reischuk and Bernd Schmeltz: Reliable computation with noisy circuits and decision trees–a general nlog n lower bound. In Proc. 32nd FOCS, pp. 602–611. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SFCS.1991.185425]

[44]   Theodore J. Rivlin: An Introduction to the Approximation of Functions. Dover Publications, New York, 1981.

[45]   Leonard J. Schulman: Communication on noisy channels: A coding theorem for computation. In Proc. 33rd FOCS, pp. 724–733. IEEE Comp. Soc. Press, 1992. [doi:10.1109/SFCS.1992.267778]

[46]   Leonard J. Schulman: Coding for interactive communication. IEEE Trans. Inform. Theory, 42(6):1745–1756, 1996. Preliminary versions in FOCS’92 and STOC’93. [doi:10.1109/18.556671]

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

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

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

[50]   Alexander A. Sherstov: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. In Proc. 42nd STOC, pp. 523–532. ACM Press, 2010. [doi:10.1145/1806689.1806762]

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

[52]   Daniel A. Spielman: Highly fault-tolerant parallel computation. In Proc. 37th FOCS, pp. 154–163. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548474]

[53]   Mario Szegedy and Xiaomin Chen: Computing Boolean functions from multiple faulty copies of input bits. Theoret. Comput. Sci., 321(1):149–170, 2004. Preliminary version in LATIN’02. [doi:10.1016/j.tcs.2003.07.001]

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