[1]   Scott Aaronson: Limitations of quantum advice and one-way communication. Theory of Computing, 1:1–28, 2005. Earlier version in Proc. 19th IEEE Conf. Comput. Complex., 2004 and arxiv:quant-ph/0402095. [doi:10.4086/toc.2005.v001a001]

[2]   Scott Aaronson: Quantum computing, postselection, and probabilistic polynomial-time. In Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., volume A461(2063), pp. 3473–3482, 2005. Earlier version in arxiv:quant-ph/0412187. [doi:10.1098/rspa.2005.1546]

[3]   Scott Aaronson: Lower bounds for local search by quantum arguments. SIAM J. Comput., 35(4):804–824, 2006. Earlier version in STOC ’03 and arxiv:quant-ph/0307149. [doi:10.1137/S0097539704447237]

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

[5]   Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang: Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997. [doi:10.1137/S0097539795293639]

[6]   Dorit Aharonov and Oded Regev: A lattice problem in quantum NP. In Proc. 44th FOCS, pp. 210–219. IEEE Comp. Soc. Press, 2003. Earlier version in arxiv:quant-ph/0307220. [doi:10.1109/SFCS.2003.1238195]

[7]   Dorit Aharonov and Oded Regev: Lattice problems in NP intersect coNP. J. ACM, 52(5):749–765, 2005. Earlier version in FOCS ’04. [doi:10.1145/1089023.1089025]

[8]   Miklós Ajtai: Generating hard instances of lattice problems (extended abstract). In Proc. 28th STOC, pp. 99–108. ACM Press, 1996. [doi:10.1145/237814.237838]

[9]   Miklós Ajtai and Cynthia Dwork: A public-key cryptosystem with worst-case/average-case equivalence. In Proc. 29th STOC, pp. 284–293. ACM Press, 1997. [doi:10.1145/258533.258604]

[10]   Miklós Ajtai and Cynthia Dwork: The first and fourth public-key cryptosystems with worst-case/average-case equivalence. Electron. Colloq. on Comput. Complexity (ECCC), 14(097), 2007. [ECCC:TR07-097]

[11]   Miklós Ajtai, Ravi Kumar, and D. Sivakumar: A sieve algorithm for the shortest lattice vector problem. In Proc. 33rd STOC, pp. 601–610. ACM Press, 2001. [doi:10.1145/380752.380857]

[12]   Noga Alon: On the rigidity of an Hadamard matrix. Manuscript. His proof may be found in [70, Section 15.1.2], 1990.

[13]   Noga Alon and Joel H. Spencer: The Probabilistic Method. Wiley-Interscience, third edition, 2008.

[14]   Andris Ambainis: Quantum lower bounds by quantum arguments. J. Comput. System Sci., 64(4):750–767, 2002. Earlier versions in STOC ’00 and arxiv:quant-ph/0002066. [doi:10.1006/jcss.2002.1826]

[15]   Andris Ambainis: Polynomial degree vs. quantum query complexity. J. Comput. System Sci., 72(2):220–238, 2006. Earlier versions in FOCS ’03 and arxiv:quant-ph/0305028. [doi:10.1016/j.jcss.2005.06.006]

[16]   Andris Ambainis, A. Childs, Ben W. Reichardt, Robert Špalek, and S. 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. Earlier version in FOCS ’07. [doi:10.1137/080712167]

[17]   Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani: Dense quantum coding and quantum finite automata. J. ACM, 49(4):496–511, 2002. Earlier version in STOC ’99. [doi:10.1145/581771.581773]

[18]   László Babai and Péter Frankl: Linear Algebra Methods in Combinatorics, with Applications to Geometry and Computer Science. University of Chicago, 1992. Unpublished manuscript, available from http://www.cs.uchicago.edu/research/publications/combinatorics.

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

[20]   W. Banaszczyk: New bounds in some transference theorems in the geometry of numbers. Math. Ann., 296(4):625–635, 1993. [doi:10.1007/BF01445125]

[21]   Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar: Information theory methods in communication complexity. In Proc. 17th IEEE Conf. Comput. Complex., 2002, pp. 93–102, 2002. [doi:10.1109/CCC.2002.1004344]

[22]   Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar: An information statistics approach to data stream and communication complexity. J. Comput. System Sci., 68(4):702–732, 2004. Earlier version in FOCS ’02. [doi:10.1016/j.jcss.2003.11.006]

[23]   Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Earlier versions in FOCS ’98 and arxiv:quant-ph/9802049. [doi:10.1145/502090.502097]

[24]   Richard Beigel: Perceptrons, PP, and the polynomial hierarchy. Comput. Complexity, 4:339–349, 1994. [doi:10.1007/BF01263422]

[25]   Richard Beigel, Nick Reingold, and Daniel Spielman: PP is closed under intersection. J. Comput. System Sci., 50(2):191–202, 1995. [doi:10.1006/jcss.1995.1017]

[26]   Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf: A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In Proc. 49th FOCS, pp. 477–486. IEEE Comp. Soc. Press, 2008. Earlier version in arxiv:quant-ph/0705.3806. [doi:10.1109/FOCS.2008.45]

[27]   Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. Earlier version in arxiv:quant-ph/9701001. [doi:10.1137/S0097539796300933]

[28]   S. N. Bernstein: Démonstration du théorème de Weierstrass fondée sur le calcul des probabilités. Communications de la Société Mathematique de Kharkov, 13:1–2, 1912.

[29]   Gilles Brassard, P. Høyer, Michele Mosca, and Alain Tapp: Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pp. 53–74. American Mathematical Society, 2002. Earlier version in arxiv:quant-ph/0005055.

[30]   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. Earlier version in arxiv:cs.CC/9904019. [doi:10.1109/SFFCS.1999.814607]

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

[32]   Harry Buhrman, P. B. Miltersen, Jaikumar Radhakrishnan, and S. Venkatesh: Are bitvectors optimal? SIAM J. Comput., 31(6):1723–1744, 2002. Earlier version in STOC ’00. [doi:10.1137/S0097539702405292]

[33]   Harry Buhrman, Ilan Newman, Hein Röhrig, and Ronald de Wolf: Robust polynomials and quantum algorithms. Theory Comput. Syst., 40(4):379–395, 2007. Special issue on STACS 2005. Earlier version in arxiv:quant-ph/0309220. [doi:10.1007/s00224-006-1313-z]

[34]   Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf: On computation and communication with small bias. In Proc. 22nd IEEE Conf. Comput. Complex., pp. 24–32, 2007. [doi:10.1109/CCC.2007.18]

[35]   Amit Chakrabarti and Oded Regev: An optimal randomised cell probe lower bound for approximate nearest neighbour searching. In Proc. 45th FOCS, pp. 473–482. IEEE Comp. Soc. Press, 2004. [doi:10.1137/080729955]

[36]   Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Chi-Chih Yao: Informational complexity and the direct sum problem for simultaneous message complexity. In Proc. 42nd FOCS, pp. 270–278. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959901]

[37]   Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan: Private information retrieval. J. ACM, 45(6):965–981, 1998. Earlier version in FOCS ’95. [doi:10.1145/293347.293350]

[38]   Matthias Christandl: A quantum information-theoretic proof of the relation between Horn’s problem and the Littlewood-Richardson coefficients. In Proc. 4th Conf. Computability in Europe (CiE), volume 5028 of Lecture Notes in Comput. Sci., pp. 120–128, 2008. [doi:10.1145/293347.293350]

[39]   Richard Cleve, Wim van Dam, Michael Nielsen, and Alain Tapp: Quantum entanglement and the communication complexity of the inner product function. In Proc. 1st NASA Intern. Conf. Quantum Comput. Quantum Comm., volume 1509 of Lecture Notes in Comput. Sci., pp. 61–74. Springer, 1998. Earlier version in arxiv:quant-ph/9708019. [doi:10.1007/3-540-49208-9_4]

[40]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. Wiley, 1991.

[41]   Mart de Graaf and Ronald de Wolf: On quantum versions of the Yao principle. In Proc. 19th Ann. Symp. Theor. Aspects of Comput. Sci. (STACS), volume 2285 of Lecture Notes in Comput. Sci., pp. 347–358. Springer, 2002. Earlier version in arxiv:quant-ph/0109070. [doi:10.1007/3-540-45841-7_28]

[42]   Ronald de Wolf: Quantum communication and complexity. Theoret. Comput. Sci., 287(1):337–353, 2002. [doi:10.1016/S0304-3975(02)00377-8]

[43]   Ronald de Wolf: Lower bounds on matrix rigidity via a quantum argument. In Proc. 33rd Intern. Colloq. Autom. Lang. Program. (ICALP), volume 4051 of Lecture Notes in Comput. Sci., pp. 62–71, 2006. Earlier version in arxiv:quant-ph/0505188. [doi:10.1007/11786986_7]

[44]   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. Earlier version in arxiv:quant-ph/0802.1816.

[45]   Ronald de Wolf: Rational degree equals quantum query complexity with postselection. Unpublished note, Oct 2008.

[46]   Andrew Drucker and Ronald de Wolf: Uniform approximation by (quantum) polynomials. Quantum Information and Computation, (3&4):215–225, 2011. http://www.rintonpress.com/journals/qiconline.html\#v11n34. Earlier version in arxiv:1008.1599.

[47]   Klim Efremenko: 3-query locally decodable codes of subexponential length. In Proc. 41st STOC, pp. 39–44. ACM Press, 2009. [doi:10.1145/1536414.1536422]

[48]   H. Ehlich and K. Zeller: Schwankung von Polynomen zwischen Gitterpunkten. Math. Z., 86:41–44, 1964.

[49]   A. Einstein, B. Podolsky, and N. Rosen: Can quantum-mechanical description of physical reality be considered complete? Phys. Rev., 47:777–780, 1935.

[50]   Edward Farhi, Jeffrey Goldstone, and Sam Gutmann: A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4(1):169–190, 2008. Earlier version in arxiv:quant-ph/0702144. [doi:10.4086/toc.2008.v004a008]

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

[52]   Lance Fortnow and Joshua A. Grochow: Complexity classes of equivalence problems revisited, 2009. Earlier version in arXiv:0907.4775.

[53]   Lance Fortnow and Nick Reingold: PP is closed under truth-table reductions. Inform. and Comput., 124(1):1–6, 1996. [doi:10.1137/S0097539791195877]

[54]   Lance Fortnow and John Rogers: Complexity limitations on quantum computation. J. Comput. System Sci., 59(2):240–252, 1999. Earlier version in Proc. 13th IEEE Conf. Comput. Complex., 1998 and arxiv:cs.CC/9811023. [doi:10.1006/jcss.1999.1651]

[55]   Nicolas Gisin, Renato Renner, and Stefan Wolf: Linking classical and quantum key agreement: Is there a classical analog to bound entanglement? Algorithmica, 34(4):389–412, 2002. Earlier version in Crypto ’00. [doi:10.1007/s00453-002-0972-7]

[56]   Oded Goldreich and Shafi Goldwasser: On the limits of nonapproximability of lattice problems. J. Comput. System Sci., 60(3):540–563, 2000. Earlier version in STOC ’98. [doi:10.1137/S0097539702405292]

[57]   Oded Goldreich, Howard Karloff, Leonard J. Schulman, and Luca Trevisan: Lower bounds for linear locally decodable codes and private information retrieval. Comput. Complexity, 15(3):263–296, 2006. Earlier version in Proc. 17th IEEE Conf. Comput. Complex., 2002. [doi:10.1007/s00037-006-0216-3]

[58]   Oded Goldreich, Daniele Micciancio, S. Safra, and J-P. Seifert: Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inform. Process. Lett., 71(2):55–61, 1999. [doi:10.1016/S0020-0190(99)00083-6]

[59]   Lov K. Grover: A fast quantum mechanical algorithm for database search. In Proc. 28th STOC, pp. 212–219. ACM Press, 1996. Earlier version in arxiv:quant-ph/9605043. [doi:10.1145/237814.237866]

[60]   Johan Håstad: The shrinkage exponent of de Morgan formulas is 2. SIAM J. Comput., 27(1):48–64, 1998. [doi:10.1137/S0097539794261556]

[61]   Ishay Haviv and Oded Regev: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In Proc. 39th STOC, pp. 469–477. ACM Press, 2007. [doi:10.1145/1250790.1250859]

[62]   A. S. Holevo: Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9(3):3–11, 1973. English translation in Problems Inform. Transmission, 9:177–183, 1973. http://mi.mathnet.ru/eng/ppi903.

[63]   P. Høyer, Troy Lee, and Robert Špalek: Negative weights make adversaries stronger. In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. Earlier version in arxiv:quant-ph/0611054. [doi:10.1145/1250790.1250867]

[64]   P. Høyer, Michele Mosca, and Ronald de Wolf: Quantum search on bounded-error inputs. In Proc. 30th Intern. Colloq. Autom. Lang. Program. (ICALP), volume 2719 of Lecture Notes in Comput. Sci., pp. 291–299. Springer, 2003. Earlier version in arxiv:quant-ph/0304052. [doi:10.1007/3-540-45061-0_25]

[65]   Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Shigeru Yamashita: Unbounded-error classical and quantum communication complexity. In Proc. 18th Intern. Symp. Algorithms Comput. (ISAAC), volume 4835 of Lecture Notes in Comput. Sci., pp. 100–111. Springer, 2007. Earlier version in arXiv:0709.2761. [doi:10.1007/978-3-540-77120-3_11]

[66]   D. Jackson: Über die Genauigkeit der Annäherung stetiger Funktionen durch ganze rationale Funktionen gegebenen Grades und trigonometrische Summen gegebener Ordnung. PhD thesis, University of Göttingen, 1911.

[67]   T. S. Jayram, S. Kopparty, and P. Raghavendra: On the communication complexity of read-once AC⁰ formulae. In Proc. 24th IEEE Conf. Comput. Complex., pp. 329–340, 2009. [doi:10.1109/CCC.2009.39]

[68]   T. S. Jayram, Ravi Kumar, and D. Sivakumar: Two applications of information complexity. In Proc. 35th STOC, pp. 673–682. ACM Press, 2003. [doi:10.1145/780542.780640]

[69]   III John T. Gill: Probabilistic Turing Machines and Complexity of Computation. PhD thesis, UC Berkeley, Berkeley, California, 1972.

[70]   Stasys Jukna: Extremal Combinatorics, With Applications in Computer Science. EATCS Series. Springer, 2001.

[71]   B. Kashin and Alexander A. Razborov: Improved lower bounds on the rigidity of Hadamard matrices. Mat. Zametki, 63(4):535–540, 1998. In Russian.

[72]   Jonathan Katz and Luca Trevisan: On the efficiency of local decoding procedures for error-correcting codes. In Proc. 32nd STOC, pp. 80–86. ACM Press, 2000. [doi:10.1145/335305.335315]

[73]   Iordanis Kerenidis: Quantum multiparty communication complexity and circuit lower bounds. In Proc. 4th Ann. Conf. Theory and Appl. Models of Comput. (TAMC), volume 4484 of Lecture Notes in Comput. Sci., pp. 306–317. Springer, 2007. Earlier version in arxiv:quant-ph/0504087. [doi:10.1007/978-3-540-72504-6_28]

[74]   Iordanis Kerenidis and Ronald de Wolf: Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. System Sci., 69(3):395–420, 2004. Earlier versions in STOC ’03 and arxiv:quant-ph/0208062. [doi:10.1016/j.jcss.2004.04.007]

[75]   Subhash Khot: Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789–808, 2005. Earlier version in FOCS ’04. [doi:10.1145/1089023.1089027]

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

[77]   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. Earlier version in FOCS ’04 and arxiv:quant-ph/0402123. [doi:10.1137/05063235X]

[78]   Greg Kuperberg: Random words, quantum statistics, central limits, random matrices. Methods Appl. Anal., 9(1):99–118, 2002. http://www.intlpress.com/MAA/p/2002/09_1/MAA-09-1-099-118.pdf. Earlier version in arxiv:math/9909104.

[79]   Greg Kuperberg: A tracial quantum central limit theorem. Trans. Amer. Math. Soc., 357:459–471, 2005. Earlier version in arxiv:math-ph/0202035. [doi:10.1090/S0002-9947-03-03449-4]

[80]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge University Press, 1997.

[81]   J. C. Lagarias, H. W. Lenstra, Jr., and C.-P. Schnorr: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica, 10(4):333–348, 1990. [doi:10.1007/BF02128669]

[82]   Sophie Laplante, Troy Lee, and Mario Szegedy: The quantum adversary method and classical formula size lower bounds. Comput. Complexity, 15(2):163–196, 2006. Earlier version in Proc. 20th IEEE Conf. Comput. Complex., 2005. [doi:10.1007/s00037-006-0212-7]

[83]   Sophie Laplante and Frederic Magniez: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In Proc. 19th IEEE Conf. Comput. Complex., pp. 294–304, 2004. Earlier version in arxiv:quant-ph/0311189. [doi:10.1109/CCC.2004.1313852]

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

[85]   Troy Lee, Gideon Schechtman, and Adi Shraibman: Lower bounds on quantum multiparty communication complexity. In Proc. 24th IEEE Conf. Comput. Complex., pp. 254–262, 2009. [doi:10.1109/CCC.2009.24]

[86]   A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász: Factoring polynomials with rational coefficients. Math. Ann., 261(4):515–534, 1982.

[87]   Nikos Leonardos and Michael Saks: Lower bounds on the randomized communication complexity of read-once functions. Comput. Complexity, 19(2):153–181, 2010. [doi:10.1007/s00037-010-0292-2]

[88]   Ming Li and Paul Vitányi: An Introduction to Kolmogorov Complexity and its Applications. Springer, Berlin, third edition, 2008.

[89]   Nati Linial and Adi Shraibman: Learning complexity vs communication complexity. Combin. Probab. Comput., 18(1-2):227–245, 2009. Earlier version in Proc. 22nd IEEE Conf. Computat. Complex., 2008. [doi:10.1017/S0963548308009656]

[90]   Nati Linial and Adi Shraibman: Lower bounds in communication complexity based on factorization norms. Random Structures Algorithms, 34(3):368–394, 2009. Earlier version in STOC ’07. [doi:10.1002/rsa.20232]

[91]   Richard Lipton: Erds and the quantum method, March 28, 2009. Blog entry http://rjlipton.wordpress.com/2009/03/28/erds-and-the-quantum-method/.

[92]   Satyanarayana V. Lokam: Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity. J. Comput. System Sci., 63(3):449–473, 2001. Earlier version in FOCS ’95. [doi:10.1006/jcss.2001.1786]

[93]   Satyanarayana V. Lokam: Quadratic lower bounds on matrix rigidity. In Proc. 3rd Ann. Conf. Theory and Appl. Models of Comput. (TAMC), volume 3959 of Lecture Notes in Comput. Sci., pp. 295–307. Springer, 2006. [doi:10.1007/11750321_28]

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

[95]   Daniele Micciancio: Almost perfect lattices, the covering radius problem, and applications to Ajtai’s connection factor. SIAM J. Comput., 34(1):118–169, 2004. [doi:10.1137/S0097539703433511]

[96]   Daniele Micciancio and Shafi Goldwasser: Complexity of Lattice Problems: A cryptographic perspective. Volume 671 of Kluwer Internat. Ser. Engrg. Comput. Sci. Kluwer Academic Publishers, Boston, Massachusetts, 2002.

[97]   Daniele Micciancio and Oded Regev: Lattice-based cryptography. In D. J. Bernstein, J. Buchmann, and E. Dahmen, editors, Post-quantum Cryptography, pp. 147–191. Springer, 2009. [doi:10.1007/978-3-540-88702-7_5]

[98]   Gatis Midrijanis: Three lines proof of the lower bound for the matrix rigidity. Technical report, Arxiv e-print, June 2005. [arXiv:cs.CC/0506081]

[99]   Marvin Minsky and Seymour Papert: Perceptrons. MIT Press, Cambridge, MA, 1968. Second, expanded edition 1988.

[100]   Ashwin Nayak: Optimal lower bounds for quantum automata and random access codes. In Proc. 40th FOCS, pp. 369–376. IEEE Comp. Soc. Press, 1999. Earlier version in arxiv:quant-ph/9904093. [doi:10.1109/SFFCS.1999.814608]

[101]   Ashwin Nayak and Julia Salzman: Limits on the ability of quantum states to convey classical messages. J. ACM, 53(1):184–206, 2006. Earlier version in STOC ’02. [doi:10.1145/1120582.1120587]

[102]   Michael Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[103]   Ryan O’Donnell and Rocco Servedio: New degree bounds for polynomial threshold functions. In Proc. 35th STOC, pp. 325–334. ACM Press, 2003. [doi:10.1145/780542.780592]

[104]   Ramamohan Paturi: On the degree of polynomials that approximate symmetric Boolean functions. In Proc. 24th STOC, pp. 468–474. ACM Press, 1992. [doi:10.1145/129712.129758]

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

[106]   Chris Peikert: Public-key cryptosystems from the worst-case shortest vector problem. In Proc. 41st STOC, pp. 333–342. ACM Press, 2009. [doi:10.1145/1536414.1536461]

[107]   Jaikumar Radhakrishnan, Pranab Sen, and S. Venkatesh: The quantum complexity of set membership. Algorithmica, 34(4):462–479, 2002. Earlier versions in FOCS ’00 and arvix:quant-ph/0007021. [doi:10.1007/s00453-002-0979-0]

[108]   Alexander A. Razborov: Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Sciences, Mathematics, 67(1):145–159, 2003. Earlier version in arxiv:quant-ph/0204025. [doi:10.1070/IM2003v067n01ABEH000422]

[109]   Oded Regev: New lattice based cryptographic constructions. J. ACM, 51(6):899–942, 2004. Earlier version in STOC ’03. [doi:10.1145/1039488.1039490]

[110]   Oded Regev: Quantum computation and lattice problems. SIAM J. Comput., 33(3):738–760, 2004. Earlier version in FOCS ’02. [doi:10.1137/S0097539703440678]

[111]   Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009. Earlier version in STOC ’05. [doi:10.1145/1568318.1568324]

[112]   Ben W. Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proc. 50th FOCS, pp. 544–551. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.55]

[113]   Ben W. Reichardt: Span programs and quantum query algorithms. Technical report, ECCC Report TR10–110, 2010. [ECCC:TR10-110]

[114]   Renato Renner and Stefan Wolf: New bounds in secret-key agreement: The gap between formation and secrecy extraction. In Proc. Advances in Cryptology — Eurocrypt, volume 2656 of Lecture Notes in Comput. Sci., pp. 562–577. Springer, 2003. [doi:10.1007/3-540-39200-9_35]

[115]   Theodore J. Rivlin: An Introduction to the Approximation of Functions. Blaisdell Publishing Company, 1969.

[116]   Theodore J. Rivlin and E. W. Cheney: A comparison of uniform approximations on an interval and a finite subset thereof. SIAM J. Numer. Anal., 3(2):311–320, 1966.

[117]   Pranab Sen and S. Venkatesh: Lower bounds for predecessor searching in the cell probe model. J. Comput. System Sci., 74(3):364–385, 2008. [doi:10.1016/j.jcss.2007.06.016]

[118]   Alexander A. Sherstov: Approximate inclusion-exclusion for arbitrary symmetric functions. In Proc. 23rd IEEE Conf. Comput. Complex., pp. 112–123, 2008. [doi:10.1109/CCC.2008.18]

[119]   Alexander A. Sherstov: Halfspace matrices. Comput. Complexity, 17(2):149–178, 2008. [doi:10.1007/s00037-008-0242-4]

[120]   Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 2010. To appear. Earlier version in STOC ’08.

[121]   Peter W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. Earlier versions in FOCS ’94 and arxiv:quant-ph/9508027. [doi:10.1137/S0097539795293172]

[122]   Daniel R. Simon: On the power of quantum computation. SIAM J. Comput., 26(5):1474–1483, 1997. Earlier version in FOCS ’94. [doi:10.1137/S0097539796298637]

[123]   Luca Trevisan: Some applications of coding theory in computational complexity. Quad. Mat., 13:347–424, 2004.

[124]   Koji Tsuda, Gunnar Rätsch, and Manfred Warmuth: Matrix exponentiated gradient updates for on-line learning and Bregman projection. J. Mach. Learn. Res., 6:995–1018, 2005. http://www.jmlr.org/papers/volume6/tsuda05a/tsuda05a.pdf.

[125]   Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In Proc. 6th Conf. Math. Found. Comput. Sci. (MFCS), volume 53 of Lecture Notes in Comput. Sci., pp. 162–176. Springer, 1977. [doi:10.1007/3-540-08353-7_135]

[126]   Stephanie Wehner and Ronald de Wolf: Improved lower bounds for locally decodable codes and private information retrieval. In Proc. 32nd Intern. Colloq. Autom. Lang. Program. (ICALP), volume 3580 of Lecture Notes in Comput. Sci., pp. 1424–1436, 2005. Earlier version in arxiv:quant-ph/0403140. [doi:10.1007/11523468_115]

[127]   Karl Weierstrass: Über die analytische Darstellbarkeit sogenannter willkürlicher Funktionen reeller Argumente. In Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften zu Berlin, II, volume 3. 1885.

[128]   David P. Woodruff: New lower bounds for general locally decodable codes. Technical report, ECCC Report TR07–006, 2007. [ECCC:TR07-006]

[129]   David P. Woodruff: A quadratic lower bound for three-query linear locally decodable codes over any field. In Proc. 13th Intern. Workshop Approx. Randomization Comb. Optim. (APPROX), Lecture Notes in Comput. Sci., pp. 766–779. Springer, 2010. [doi:10.1007/978-3-642-15369-3_57]

[130]   Andrew Chi-Chih Yao: Some complexity questions related to distributive computing. In Proc. 11th STOC, pp. 209–213. ACM Press, 1979. [doi:10.1145/800135.804414]

[131]   Sergey Yekhanin: Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1), 2008. Earlier version in STOC ’07. [doi:10.1145/1326554.1326555]