@STRING{siamjc   = "SIAM Journal on Computing"}
@STRING{eatcsbul = "EATCS Bulletin"}
@STRING{springer = "Springer"}
@STRING{cup      = "Cambridge University Press"}

@ARTICLE(ambainis:lowerb,
    author = "A. Ambainis",
    title = "Quantum lower bounds by quantum arguments",
    journal = "Journal of Computer and System Sciences",
    year = "2002",
    volume = "64",
    number=4,
    pages = "750--767",
    note = "Earlier version in STOC '00",
    comment = "quant-ph/0002066",
    eprint="jcss:10.1006/jcss.2002.1826,stoc:335305.335394,arxiv:quant-ph/0002066"
    )
@INPROCEEDINGS(ambainis:degree-vs-qc,
    author = "A. Ambainis",
    title = "Polynomial degree {vs.} quantum query complexity",
    booktitle = "Proc. of 44th IEEE FOCS",
    year = "2003",
    pages = "230--239",
    eprint="focs:10.1109/SFCS.2003.1238197,arxiv:quant-ph/0305028"
    )

@INPROCEEDINGS(ambainis:eldist,
    author = "A. Ambainis",
    title = "Quantum walk algorithm for element distinctness",
    booktitle = "Proc. of 45th IEEE FOCS",
    year = 2004,
    pages = "22--31",
    comment = "quant-ph/0311001",
    eprint="arxiv:quant-ph/0311001"
    )
@ARTICLE(ambainis:collision,
    author = "A. Ambainis",
    title = "Polynomial Degree and Lower Bounds in Quantum Complexity:
    Collision and Element Distinctness with Small Range",
    journal = "Theory of Computing",
    volume = 1,
    pages = "37--46",
    year = 2005,
    comment = "quant-ph/0305179",
    eprint="toc:v001/a003,arxiv:quant-ph/0305179"
    )
@ARTICLE(as:collision,
    author = "S. Aaronson and Y. Shi",
    title = "Quantum lower bounds for the collision and the element distinctness problem",
    journal = jacm,
    volume = "51",
    number = "4",
    pages = "595--605",
    year = "2004",
    comment = "quant-ph/0111102",
    eprint="jacm:1008731.1008735,arxiv:quant-ph/0111102"
    )
@ARTICLE(bbbv:hybrid,
    author = "H. Bennett and E. Bernstein and G. Brassard and U. Vazirani",
    title = "Strengths and Weaknesses of Quantum Computing",
    journal = siamjc,
    volume = 26,
    number = 5,
    pages = "1510--1523",
    year = "1997",
    comment = "quant-ph/9701001",
    eprint="sicomp:30093,arxiv:quant-ph/9701001"
    )
@ARTICLE{bbcmw:polynomialsj,
  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 FOCS '98",
  comment   = "quant-ph/9802049",
  eprint="jacm:502090.502097,focs:10.1109/SFCS.1998.743485,arxiv:quant-ph/9802049"
}
@ARTICLE(bs:q-read-once,
    author = "H. Barnum and M. Saks",
    title = "A lower bound on the quantum query complexity of read-once functions",
    journal = jcss,
    volume = 69,
    number = 2,
    pages = "244--258",
    year = 2004,
    comment = "quant-ph/0201007",
    eprint="jcss:10.1016/j.jcss.2004.02.002,arxiv:quant-ph/0201007"
    )
@INPROCEEDINGS{bs:matrix,
 AUTHOR    = "H. Buhrman and R. {\v{S}}palek",
 TITLE     = "Quantum Verification of Matrix Products",
 BOOKTITLE = "Proc. of 17th ACM-SIAM SODA",
 YEAR      = 2006,
 PAGES     = "880--889",
 comment   = "quant-ph/0409035",
 eprint="soda:1109557.1109654,arxiv:quant-ph/0409035"
}
@INPROCEEDINGS(bss:semidef,
    author = "H. Barnum and M. Saks and M. Szegedy",
    title = "Quantum decision trees and semidefinite programming",
    booktitle = "Proc. of 18th IEEE Complexity",
    year = "2003",
    pages = "179--193",
    eprint="ccc:10.1109/CCC.2003.1214419"
    )
@ARTICLE{buhrman&wolf:dectreesurvey,
  AUTHOR    = "H. Buhrman and Wolf, R. {de}",
  TITLE     = "Complexity Measures and Decision Tree Complexity: {A} Survey",
  JOURNAL   = tcs,
  VOLUME    = 288,
  NUMBER    = 1,
  PAGES     = "21--43",
  YEAR      = 2002,
  eprint="tcs:10.1016/S0304-3975(01)00144-X",
  ps="http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.ps"
}
@INPROCEEDINGS{grover:search,
  AUTHOR    = "L. K. Grover",
  TITLE     = "A Fast Quantum Mechanical Algorithm for Database Search",
  BOOKTITLE = "Proc. of 28th ACM STOC",
  PAGES     = "212--219",
  YEAR      = 1996,
  comment   = "quant-ph/9605043",
  eprint="stoc:237814.237866,arxiv:quant-ph/9605043"
}
@INPROCEEDINGS(hmw:berror-search,
    author = "P. H{\o}yer and M. Mosca and Wolf, R. {de}",
    title = "Quantum Search on Bounded-Error Inputs",
    booktitle = "Proc. of 30th ICALP",
    pages = "291--299",
    year = "2003",
    note = "LNCS 2719",
    comment = "quant-ph/0304052",
    eprint="icalp:214dhep41d6vk3d2,arxiv:quant-ph/0304052"
    )
@ARTICLE(hns:ordered-search,
    author = "P. H{\o}yer and J. Neerbek and Y. Shi",
    title = "Quantum complexities of ordered searching, sorting, and element distinctness",
    journal = "Algorithmica",
    volume = "34",
    number = "4",
    pages = "429--448",
    year = "2002",
    note = "Special issue on Quantum Computation and Cryptography",
    comment = "quant-ph/0102078",
    CommentBooktitle = "Proc. of 28th ICALP",
    CommentPages = "346--357",
    CommentYear = "2001",
    CommentNote = "LNCS 2076",
    commenteprint="icalp:0ybn6v2nywvtkpua",
    eprint="algorithmica:25gl9elr5rxr3q6a,arxiv:quant-ph/0102078"
    )
@ARTICLE{hs:survey-lb,
  author = "P. H{\o}yer and R. {\v{S}}palek",
  title = "Lower Bounds on Quantum Query Complexity",
  journal = eatcsbul,
  volume = 87,
  pages = "78--103",
  year = "October, 2005",
  eprint="arxiv:quant-ph/0509153"
}
@INPROCEEDINGS(lls:formulas,
    author = "S. Laplante and T. Lee and M. Szegedy",
    title = "The quantum adversary method and formula size lower bounds",
    booktitle = "Proc. of 20th IEEE Complexity",
    year = 2005,
    pages = "76--90",
    comment = "quant-ph/0501057",
    eprint="ccc:10.1109/CCC.2005.29,arxiv:quant-ph/0501057"
    )
@INPROCEEDINGS(lm:kolmogorov-lb,
    author = "S. Laplante and F. Magniez",
    title = "Lower bounds for randomized and quantum query complexity using {Kolmogorov} arguments",
    booktitle = "Proc. of 19th IEEE Complexity",
    pages = "294--304",
    year = "2004",
    comment = "quant-ph/0311189",
    eprint="ccc:10.1109/CCC.2004.1313852,arxiv:quant-ph/0311189"
    )
@UNPUBLISHED(lovasz:semidef,
    author = "L. Lov\'asz",
    title = "Semidefinite programs and combinatorial optimization",
    year = 2000,
    note = "\url{http://research.microsoft.com/users/lovasz/semidef.ps}",
    ps="http://research.microsoft.com/users/lovasz/semidef.ps"
    )
@BOOK{li&vitanyi:kolm,
  AUTHOR    = "M. Li and P. M. B. Vit{\'{a}}nyi",
  TITLE     = "An Introduction to {K}olmogorov Complexity and its Applications",
  EDITION   = "Second",
  PUBLISHER = springer,
  ADDRESS   = "Berlin",
  YEAR      = 1997,
}
@ARTICLE(mathias:spectral-norm,
    author = "R. Mathias",
    title = "The spectral norm of a nonnegative matrix",
    journal = "Linear Algebra and its Applications",
    volume = "139",
    pages = "269--284",
    year = 1990,
    eprint="laa:10.1016/0024-3795(90)90403-Y",
    ps="http://www.math.wm.edu/~mathias/preprints/ps_zips/nonneg.ps.gz"
    )
@INPROCEEDINGS(mss:triangle,
    author = "F. Magniez and M. Santha and M. Szegedy",
    title = "Quantum Algorithms for the Triangle Problem",
    booktitle = "Proc. of 16th ACM-SIAM SODA",
    year = "2005",
    pages = "1109--1117",
    comment = "quant-ph/0310134",
    eprint="soda:1070432.1070591,arxiv:quant-ph/0310134"
    )
@BOOK{nielsen&chuang:qc,
  AUTHOR    = "M. A. Nielsen and I. L. Chuang",
  TITLE     = "Quantum Computation and Quantum Information",
  PUBLISHER = cup,
  YEAR      = 2000,
}
@ARTICLE(santha:and-or,
    author = "M. Santha",
    title = "On the {M}onte {C}arlo decision tree complexity 
    of read-once formulae",
    journal = "Random Structures and Algorithms",
    volume = 6,
    number = 1,
    pages = "75--87",
    year = 1995,
    comment = "Earlier version in Structures '91",
    ps="http://www.lri.fr/~santha/Papers/s95.ps.gz"
    )
@ARTICLE(snir:dec,
    author = "M. Snir",
    title = "Lower bounds on probabilistic decision trees",
    journal = "Theoretical Computer Science",
    volume = 38,
    pages = "69--82",
    year = 1985,
    eprint="tcs:10.1016/0304-3975(85)90210-5"
    )
@INPROCEEDINGS(sw:and-or,
    author = "M. Saks and A. Wigderson",
    title = "Probabilistic {Boolean} decision trees and the complexity of evaluating games trees",
    booktitle = "Proc. of 27th IEEE FOCS",
    pages = "29--38",
    year = "1986",
    ps="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/VW85A/VW85A.ps",
    pdf="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf"
    )
@UNPUBLISHED(szegedy:triangle,
    author = "M. Szegedy",
    title = "On the Quantum Query Complexity of Detecting Triangles in Graphs",
    year = "2003",
    note = "quant-ph/0310107",
    eprint="arxiv:quant-ph/0310107"
    )
@ARTICLE(zhang:ambainis,
    author = "S. Zhang",
    title = "On the power of {Ambainis}'s lower bounds",
    journal = "Theoretical Computer Science",
    volume = 339,
    number = "2--3",
    year = 2005,
    pages = "241--256",
    note = "Earlier version in ICALP'04",
    commbooktitle = "Proc. of 31st ICALP",
    commpages = "1238--1250",
    commyear = "2004",
    comment = "quant-ph/0311060",
    eprint="tcs:10.1016/j.tcs.2005.01.019,icalp:gm2ff6wpc0q39v3x,arxiv:quant-ph/0311060"
    )