Theory of Computing, Volume 1

Volume 1, Number 1, 2005

• Scott Aaronson:
  Limitations of Quantum Advice and One-Way Communication. 1-28
  Electronic Edition (link) BibTeX
• Samuel Kutin:
  Quantum Lower Bound for the Collision Problem with Small Range. 29-36
  Electronic Edition (link) BibTeX
• Andris Ambainis:
  Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range. 37-46
  Electronic Edition (link) BibTeX
• Scott Aaronson, Andris Ambainis:
  Quantum Search of Spatial Regions. 47-79
  Electronic Edition (link) BibTeX
• Peter Høyer, Robert Spalek:
  Quantum Fan-out is Powerful. 81-103
  Electronic Edition (link) BibTeX
• Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour:
  Combining Online Algorithms for Acceptance and Rejection. 105-117
  Electronic Edition (link) BibTeX
• Johan Håstad, Subhash Khot:
  Query Efficient PCPs with Perfect Completeness. 119-148
  Electronic Edition (link) BibTeX
• Miklós Ajtai:
  A Non-linear Time Lower Bound for Boolean Branching Programs. 149-176
  Electronic Edition (link) BibTeX
• Noga Alon, Asaf Shapira:
  Linear Equations, Arithmetic Progressions and Hypergraph Property Testing. 177-216
  Electronic Edition (link) BibTeX