Theory of Computing, Volume 1

Volume 1, Number 1, 2005

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