@STRING{PRL = {Phys. Rev. Lett.}}

@STRING{QIC = {Quantum Information and Computation}}

@STRING{SICOMP = {SIAM J. Computing}}

@STRING{JACM = {J. ACM}}

@STRING{JCSS = {J. Comput. Sys. Sci.}}

@STRING{TCS = {Theoretical Computer Sci.}}

@STRING{IPL = {Inform. Proc. Lett.}}

@INPROCEEDINGS{aar:col,
  AUTHOR = {S. Aaronson},
  TITLE = {Quantum lower bound for the collision problem},
  BOOKTITLE = {Proc. 34th ACM STOC},
  PAGES = {635-642},
  YEAR = {2002},
  EPRINT = {stoc:509907.509999, quant-ph/0111102}
}

@INPROCEEDINGS{aar:advconf,
  AUTHOR = {S. Aaronson},
  TITLE = {Limitations of quantum advice and one-way communication},
  BOOKTITLE = {19th IEEE Conf. Comput. Complexity (CCC)},
  PAGES = {320-332},
  YEAR = {2004},
  EPRINT = {ccc:10.1109/CCC.2004.1313854, quant-ph/0402095}
}

@UNPUBLISHED{aar:pp,
  AUTHOR = {S. Aaronson},
  TITLE = {Quantum computing, postselection, and probabilistic polynomial-time},
  YEAR = {2004},
  EPRINT = {quant-ph/0412187},
  NOTE = {Submitted}
}

@ARTICLE{adh,
  AUTHOR = {L. Adleman and J. DeMarrais and M.-D. Huang},
  TITLE = {Quantum computability},
  JOURNAL = SICOMP,
  VOLUME = {26},
  NUMBER = {5},
  PAGES = {1524-1540},
  YEAR = {1997},
  eprint = {sicomp:10.1137/S0097539795293639}
}

@ARTICLE{antv,
  AUTHOR = {A. Ambainis and A. Nayak and A. Ta-Shma and U. V. Vazirani},
  TITLE = {Quantum dense coding and quantum finite automata},
  JOURNAL = JACM,
  VOLUME = {49},
  PAGES = {496-511},
  YEAR = {2002},
  NOTE = {Earlier version in 31st ACM STOC, 1999, pp. 376-383},
  EPRINT = {jacm:581771.581773, quant-ph/9804043}
}

@INPROCEEDINGS{bjk,
  AUTHOR = {Z. Bar-Yossef and T. S. Jayram and I. Kerenidis},
  TITLE = {Exponential separation of quantum and classical one-way communication complexity},
  BOOKTITLE = {36th ACM STOC},
  PAGES = {128-137},
  YEAR = {2004},
  eprint = {stoc:1007352.1007379, eccc:TR04-036}
}

@ARTICLE{bbcmw,
  AUTHOR = {R. Beals and H. Buhrman and R. Cleve and M. Mosca and Wolf, R. de},
  TITLE = {Quantum lower bounds by polynomials},
  JOURNAL = JACM,
  VOLUME = {48},
  NUMBER = {4},
  PAGES = {778-797},
  YEAR = {2001},
  NOTE = {Earlier version in 39th IEEE FOCS, 1998, pp. 352-361.},
  eprint = {jacm:502090.502097, quant-ph/9802049}
}

@ARTICLE{bbbv,
  AUTHOR = {C. Bennett and E. Bernstein and G. Brassard and U. Vazirani},
  TITLE = {Strengths and weaknesses of quantum computing},
  JOURNAL = SICOMP,
  VOLUME = {26},
  NUMBER = {5},
  PAGES = {1510-1523},
  YEAR = {1997},
  EPRINT = {sicomp:30093, quant-ph/9701001}
}

@ARTICLE{bbcjpy,
  AUTHOR = {C. H. Bennett and G. Brassard and C. Cr\'{e}peau and R. Jozsa and A. Peres and W. Wootters},
  TITLE = {Teleporting an unknown quantum state by dual classical and {EPR} channels},
  JOURNAL = PRL,
  VOLUME = {70},
  PAGES = {1895-1898},
  YEAR = {1993},
  eprint = {prl:10.1103/PhysRevLett.70.1895}
}

@ARTICLE{bg,
  AUTHOR = {C. H. Bennett and J. Gill},
  TITLE = {Relative to a random oracle {A}, {$P^{A}\neq NP^{A}\neq coNP^{A}$} with probability 1},
  JOURNAL = SICOMP,
  VOLUME = {10},
  NUMBER = {1},
  PAGES = {96-113},
  YEAR = {1981},
  eprint = {sicomp:10/0210008}
}

@ARTICLE{bernstein,
  AUTHOR = {S. N. Bernstein},
  TITLE = {Sur l'ordre de la meilleure approximation des fonctions continues par les polyn\^{o}mes de degr\'{e} donn\'{e}},
  JOURNAL = {Mem. Cl. Sci. Acad. Roy. Belg.},
  VOLUME = {4},
  PAGES = {1-103},
  YEAR = {1912},
  NOTE = {French},
  URL = {http://www.math.technion.ac.il/hat/fpapers/ber2.pdf}
}

@ARTICLE{bcww,
  AUTHOR = {H. Buhrman and R. Cleve and J. Watrous and Wolf, R. de},
  TITLE = {Quantum fingerprinting},
  JOURNAL = PRL,
  VOLUME = {87},
  NUMBER = {16},
  YEAR = {2001},
  NOTE = {4 pages.},
  eprint = {prl:10.1103/PhysRevLett.87.167902, quant-ph/0102001}
}

@ARTICLE{bw,
  AUTHOR = {H. Buhrman and Wolf, R. de},
  TITLE = {Complexity measures and decision tree complexity: a survey},
  JOURNAL = TCS,
  VOLUME = {288},
  PAGES = {21-43},
  eprint= {tcs:10.1016/S0304-3975(01)00144-X},
  YEAR = {2002},
  URL = {http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.ps}
}

@INPROCEEDINGS{dhrs,
  AUTHOR = {P. Duri\v{s} and J. Hromkovi\v{c} and J. D. P. Rolim and G. Schnitger},
  TITLE = {Las {V}egas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations},
  BOOKTITLE = {14th Symp. Theoret. Aspects of Comp.Sci. (STACS)},
  PAGES = {117-128},
  YEAR = {1997}
}

@ARTICLE{ez,
  AUTHOR = {H. Ehlich and K. Zeller},
  TITLE = {Schwankung von {P}olynomen zwischen {G}itterpunkten},
  JOURNAL = {Mathematische Zeitschrift},
  VOLUME = {86},
  PAGES = {41-44},
  YEAR = {1964}
}

@ARTICLE{fr,
  AUTHOR = {L. Fortnow and J. Rogers},
  TITLE = {Complexity limitations on quantum computation},
  JOURNAL = JCSS,
  VOLUME = {59},
  NUMBER = {2},
  PAGES = {240-252},
  YEAR = {1999},
  eprint = {jcss:10.1006/jcss.1999.1651, cs.CC/9811023}
}

@UNPUBLISHED{goldreich:qc,
  AUTHOR = {O. Goldreich},
  TITLE = {On quantum computing},
  YEAR = {2004. 1 page},
  URL = {http://www.wisdom.weizmann.ac.il/~oded/on-qc.html}
}

@ARTICLE{hht,
  AUTHOR = {Y. Han and L. Hemaspaandra and T. Thierauf},
  TITLE = {Threshold computation and cryptographic security},
  JOURNAL = SICOMP,
  VOLUME = {26},
  NUMBER = {1},
  PAGES = {59-78},
  YEAR = {1997},
  eprint = {sicomp:24046}
}

@ARTICLE{holevo,
  AUTHOR = {A. S. Holevo},
  TITLE = {Some estimates of the information transmitted by quantum communication channels},
  JOURNAL = {Problems of Information Transmission},
  VOLUME = {9},
  PAGES = {177-183},
  YEAR = {1973},
  NOTE = {English translation}
}

@INPROCEEDINGS{klauck:cc,
  AUTHOR = {H. Klauck},
  TITLE = {Quantum communication complexity},
  BOOKTITLE = {27th Int'l. Colloq. on Automata, Languages, and Programming (ICALP)},
  PAGES = {241-252},
  YEAR = {2000},
  EPRINT = {quant-ph/0005032}
}

@INPROCEEDINGS{klauck:ts,
  AUTHOR = {H. Klauck},
  TITLE = {Quantum time-space tradeoffs for sorting},
  BOOKTITLE = {35th ACM STOC},
  PAGES = {69-76},
  YEAR = {2003},
  EPRINT = {stoc:780542.780553, quant-ph/0211174}
}

@INPROCEEDINGS{ksw,
  AUTHOR = {H. Klauck and R. \v{S}palek and Wolf, R. de},
  TITLE = {Quantum and classical strong direct product theorems and optimal time-space tradeoffs},
  BOOKTITLE = {45th IEEE FOCS},
  PAGES = {12-21},
  YEAR = {2004},
  EPRINT = {focs:10.1109/FOCS.2004.52, quant-ph/0402123},
}

@BOOK{kn,
  AUTHOR = {E. Kushilevitz and N. Nisan},
  TITLE = {Communication Complexity},
  PUBLISHER = {Cambridge},
  YEAR = {1997}
}

@ARTICLE{aamarkov,
  AUTHOR = {A. A. Markov},
  TITLE = {On a question by {D}. {I}. {M}endeleev},
  JOURNAL = {Zapiski Imperatorskoi Akademii Nauk},
  VOLUME = {SP6},
  NUMBER = {62},
  PAGES = {1-24},
  YEAR = {1890},
  NOTE = {Russian.  English translation at \url{http://www.math.technion.ac.il/hat/fpapers/markov4.pdf}}
}

@ARTICLE{vamarkov,
  AUTHOR = {V. A. Markov},
  TITLE = {{\"{U}}ber {P}olynome, die in einem gegebenen {I}ntervalle m\"{o}glichst wenig von {N}ull abweichen},
  JOURNAL = {Math. Ann.},
  VOLUME = {77},
  PAGES = {213-258},
  YEAR = {1916},
  NOTE = {German.  Originally written in 1892},
  URL = {http://www.math.technion.ac.il/hat/fpapers/vmar.pdf}
}

@BOOK{mp,
  AUTHOR = {M. Minsky and S. Papert},
  TITLE = {Perceptrons (2nd edition)},
  PUBLISHER = {MIT Press},
  YEAR = {1988},
  NOTE = {First appeared in 1968}
}

@INPROCEEDINGS{nayak,
  AUTHOR = {A. Nayak},
  TITLE = {Optimal lower bounds for quantum automata and random access codes},
  BOOKTITLE = {40th IEEE FOCS},
  PAGES = {369-377},
  YEAR = {1999},
  EPRINT = {focs:10.1109/SFFCS.1999.814608, quant-ph/9904093}
}

@BOOK{nc,
  AUTHOR = {M. Nielsen and I. Chuang},
  TITLE = {Quantum Computation and Quantum Information},
  PUBLISHER = {Cambridge University Press},
  YEAR = {2000}
}

@ARTICLE{ns,
  AUTHOR = {N. Nisan and M. Szegedy},
  TITLE = {On the degree of {B}oolean functions as real polynomials},
  JOURNAL = {Computational Complexity},
  VOLUME = {4},
  NUMBER = {4},
  PAGES = {301-313},
  YEAR = {1994},
  URL = {http://www.cs.huji.ac.il/~noam/degree.ps}
}

@ARTICLE{ny,
  AUTHOR = {H. Nishimura and T. Yamakami},
  TITLE = {Polynomial time quantum computation with advice},
  JOURNAL = IPL,
  VOLUME = {90},
  PAGES = {195-204},
  YEAR = {2003},
  eprint = {ipl:10.1016/j.ipl.2004.02.005, eccc:TR03-059, quant-ph/0305100}
}

@UNPUBLISHED{ry,
  AUTHOR = {M. Rabin and A. C-C. Yao},
  YEAR = {1979},
  NOTE = {Manuscript, cited in \cite{yao:cc}}
}

@BOOK{rivlin,
  AUTHOR = {T. J. Rivlin},
  TITLE = {Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory},
  PUBLISHER = {Wiley},
  YEAR = {1990}
}

@ARTICLE{rc,
  AUTHOR = {T. J. Rivlin and E. W. Cheney},
  TITLE = {A comparison of uniform approximations on an interval and a finite subset thereof},
  JOURNAL = {SIAM J. Numerical Analysis},
  VOLUME = {3},
  NUMBER = {2},
  PAGES = {311-320},
  YEAR = {1966},
  eprint = {sinum:03/0703024}
}

@ARTICLE{sauer,
  AUTHOR = {N. Sauer},
  TITLE = {On the density of families of sets},
  JOURNAL = {J. Combinatorial Theory Series A},
  VOLUME = {13},
  PAGES = {145-147},
  YEAR = {1972},
  eprint = {jcombtha:10.1016/0097-3165(72)90019-2}
}

@ARTICLE{shi:gate,
  AUTHOR = {Y. Shi},
  TITLE = {Both {T}offoli and controlled-{NOT} need little help to do universal quantum computation},
  JOURNAL = QIC,
  VOLUME = {3},
  NUMBER = {1},
  PAGES = {84-92},
  YEAR = {2002},
  EPRINT = {quant-ph/0205115},
  url = {http://www.rintonpress.com/journals/qiconline.html#v3n1}
}

@INPROCEEDINGS{watrous,
  AUTHOR = {J. Watrous},
  TITLE = {Succinct quantum proofs for properties of finite groups},
  BOOKTITLE = {41st IEEE FOCS},
  PAGES = {537-546},
  YEAR = 2000,
  eprint = {focs:10.1109/SFCS.2000.892141, cs.CC/0009002},
}

@INCOLLECTION{winter,
  AUTHOR = {A. Winter},
  TITLE = {Quantum and classical message identification via quantum channels},
  BOOKTITLE = {Quantum Information, Statistics, Probability (A. S. Holevo festschrift)},
  PUBLISHER = {Rinton},
  EDITOR = {O. Hirota},
  PAGES = {172-189},
  YEAR = {2004},
  EPRINT = {quant-ph/0401060}
}

@INPROCEEDINGS{yao:fing,
  AUTHOR = {A. C-C. Yao},
  TITLE = {On the power of quantum fingerprinting},
  BOOKTITLE = {35th ACM STOC},
  PAGES = {77-81},
  YEAR = {2003},
  eprint = {stoc:780542.780554, eccc:TR02-074}
}

@INPROCEEDINGS{yao:cc,
  AUTHOR = {A. C-C. Yao},
  TITLE = {Some complexity questions related to distributive computing},
  BOOKTITLE = {11th ACM STOC},
  PAGES = {209-213},
  YEAR = {1979},
  eprint = {stoc:804414}
}

@MISC{yao:hw,
  AUTHOR = {A. C-C. Yao},
  TITLE = {{P}rinceton {U}niversity course assignment},
  YEAR = {2001},
  URL = {http://www.cs.princeton.edu/courses/archive/spr01/cs598a/assignments/hw3.ps}
}