@InProceedings{Aaronson,
  author = {S. Aaronson},
  title = {Quantum lower bound for the collision problem},
  booktitle = {Proceedings of STOC'02}, 
  pages = {635--642},
  year = 2002,
  eprint = {stoc:509907.509999, quant-ph/0111102}
}

@Article{AS,
  author = {S. Aaronson and Y. Shi},
  title = {Quantum lower bounds for the collision and the element distinctness problems},
  journal = {Journal of ACM}, 
  volume = {51},
  number = 4,
  pages = {595--605},
  year = {2004}, 
  note = {Earlier versions in \cite{Aaronson} and \cite{Shi}},
  eprint = {jacm:1008731.1008735}
}

@Article{AmbainisAdv,
  author = {A. Ambainis},
  title = {Quantum lower bounds by quantum arguments},
  journal = {Journal of Computer and System Sciences},
  volume = {64},
  pages = {750--767},
  year = {2002},
  eprint = {jcss:10.1006/jcss.2002.1826, quant-ph/0002066}
}

@InProceedings{AmbainisPoly,
 author = {A. Ambainis},
 title = {Polynomial degree vs. quantum query complexity},
 booktitle = {Proceedings of FOCS'03}, 
 pages = {230--239},
 year = 2003,
 eprint = {focs:10.1109/SFCS.2003.1238197, quant-ph/0305028},
}

@InProceedings{Ambainis,
 author = {A. Ambainis},
 title = {Quantum walk algorithm for element distinctness},
 booktitle = {Proceedings of FOCS'04}, 
 pages = {22--31},
 year = 2004,
 eprint = {focs:10.1109/FOCS.2004.54,quant-ph/0311001}
}

@Article{Beals,
 author = {R. Beals and H. Buhrman and R. Cleve and M. Mosca and R. de Wolf},
 title = {Quantum lower bounds by polynomials},
 journal = {Journal of ACM}, 
 volume = {48},
 pages = {778--797}, 
 year = {2001},
 note = {Earlier version at FOCS'98},
 eprint = {jacm:502090.502097, quant-ph/9802049}
}

@InProceedings{BCW,
 author = {H. Buhrman and R. Cleve and A. Wigderson},
 title = {Quantum vs. classical communication and computation},
 booktitle = {Proceedings of STOC'98}, 
 pages = {63--68},
 year = 1998,
 eprint = {stoc:276698.276713},
}

@InProceedings{BDistinct,
 author = {H. Buhrman and C. Durr and M. Heiligman and P. H\o yer 
          and F. Magniez and M. Santha and R. de Wolf},
 title = {Quantum algorithms for element distinctness},
 booktitle = {16th IEEE Annual Conference on Computational 
              Complexity (CCC'01)}, 
 pages = {131--137},
 year = 2001,
 eprint = {ccc:10.1109/CCC.2001.933880, quant-ph/0007016}
}

@Article{BCollision,
 author = {G. Brassard and P. H\o yer and A. Tapp},
 title = {Quantum algorithm for the collision problem},
 journal = {SIGACT News}, 
 volume = 28,
 pages = {14--19}, 
 year = 1997, 
 eprint = {quant-ph/9705002}
}

@InProceedings{Counting,
 author = {G. Brassard and P. H\o yer and A. Tapp},
 title = {Quantum counting},
 booktitle = {Proceedings of ICALP'98}, 
 pages = {820--831},
 year = 1998,
 eprint = {icalp:ap2mrf08d8gcqppe, quant-ph/9805082}
}

@UnPublished{BS,
 author = {H. Buhrman and R. \v{S}palek},
 title = {Quantum verification of matrix products},
 eprint = {quant-ph/0409035}
}

@Article{BWSurvey,
 author = {H. Buhrman and R. de Wolf},
 title = {Complexity measures and decision tree complexity: a survey},
 journal = {Theoretical Computer Science},
 volume = {288},
 pages = {21--43},
 year = 2002,
 eprint = {tcs:10.1016/S0304-3975(01)00144-X}
}

@Book{CLR,
 author = {T. Cormen and C. Leiserson and R. Rivest and C. Stein},
 title = {Introduction to Algorithms, 2nd edition},
 publisher = {The MIT Press and McGraw-Hill Book Company},
 year = 2001
}

@InProceedings{Grover,
 author = {L. Grover},
 title = {A fast quantum mechanical algorithm for database search},
 booktitle = {Proceedings of STOC'96}, 
 pages = {212--219},
 year = 1996,
 eprint = {stoc:237814.237866, quant-ph/9605043}
}

@InProceedings{Grover97,
 author = {L. Grover},
 title = {A framework for fast quantum mechanical algorithms},
 booktitle = {Proceedings of STOC'98}, 
 pages = {53--62},
 year = 1998,
 eprint = {stoc:276698.276712, quant-ph/9711043}
}

@Article{HNS,
 author = {P. Hoyer and J. Neerbek and Y. Shi},
 title = {Quantum lower bounds of ordered searching, sorting and element 
distinctness},
 journal = {Algorithmica}, 
 volume = 34,
 pages = {429--448},
 year = 2002, 
 note = {Earlier version at ICALP'01},
 eprint={algorithmica:25gl9elr5rxr3q6a, quant-ph/0102078} 
}

@Article{Kutin,
 author = {S. Kutin},
 title = {Quantum lower bound for the collision problem},
 journal = {Theory of Computing}, 
 volume = 1,
 number = 2,
 pages = {29--36}, 
 year = 2005,
 eprint = {toc:v001/a002, quant-ph/0304162}
}

@InProceedings{MSS,
 author = {F. Magniez and M. Santha and M. Szegedy},
 title = {Quantum algorithms for the triangle problem},
 booktitle = {Proceedings of SODA'05},
 year = 2005,
 eprint = {quant-ph/0310134}
}

@InProceedings{NW,
 author = {A. Nayak and F. Wu},
 title = {The quantum query complexity of approximating the median and related
statistics},
 booktitle = {Proceedings of STOC'99}, 
 pages = {384--393}, 
 year = 1999,
 eprint = {stoc:301250.301349, quant-ph/9804066}
}

@Article{NS,
 author = {N. Nisan and M. Szegedy},
 title = {On the degree of Boolean functions as real polynomials},
 journal = {Computational Complexity}, 
 volume = 4,
 pages = {301--313}, 
 year = 1994,
}

@InProceedings{Shi,
 author = {Y. Shi},
 title = {Quantum lower bounds for the collision and the 
          element distinctness problems},
 booktitle = {Proceedings of FOCS'02}, 
 pages = {513--519},
 year = 2002,
 eprint = {focs:10.1109/SFCS.2002.1181975, quant-ph/0112086}
}

@Unpublished{Shi1,
 author = {Y. Shi},
 title = {Approximating linear restrictions of Boolean functions},
 note = {Manuscript}
}