A dual polynomial for OR.
Robert Špalek.
arXiv:0803.4516 [cs.CC]
The Multiplicative Quantum Adversary.
Robert Špalek.
In Proceedings of 23rd Annual IEEE Conference on Computational
Complexity (CCC'08),
pages 237-248, College Park, Maryland, 2008.
quant-ph/0703237
A direct product theorem for discrepancy.
Troy Lee, Adi Shraibman, and Robert Špalek.
In Proceedings of 23rd Annual IEEE Conference on Computational
Complexity (CCC'08),
pages 71-80, College Park, Maryland, 2008.
Span-program-based quantum algorithm for evaluating formulas.
Ben Reichardt and Robert Špalek.
In Proceedings of 40th Annual ACM Symposium on Theory of Computing
(STOC'08),
pages 103-112, Victoria, British Columbia, 2008.
arXiv:0710.2630 [quant-ph] computing wsize
Negative weights make adversaries stronger.
Peter Høyer, Troy Lee, and Robert Špalek.
In Proceedings of 39th Annual ACM Symposium on Theory of Computing
(STOC'07),
pages 526-535, San Diego, California, 2007.
quant-ph/0611054 computing Adv
Quantum Algorithms for Matching and Network Flows.
quant-ph/0508205
Quantum Verification of Matrix Products.
Harry Buhrman and Robert Špalek.
In Proceedings of 17th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA'06),
pages 880-889, Miami, Florida, 2006.
quant-ph/0409035
Any AND-OR formula of size N can be evaluated in time
N½+o(1) on a quantum computer.
Andris Ambainis, Andrew Childs, Ben Reichardt, Robert Špalek, and Shengyu Zhang.
SIAM Journal on Computing,
39(6):2513-2530, 2010.
Special issue of FOCS'07.
Conference version in Proceeding of 48th Annual IEEE Symposium on
Foundations of Computer Science (FOCS'07), pages 363-372, Providence,
Rhode Island, 2007.
quant-ph/0703015
A New Quantum Lower Bound Method, with Applications to
Direct Product Theorems and Time-Space Tradeoffs.
Andris Ambainis, Robert Špalek, and Ronald de Wolf.
Algorithmica,
55(3):422–461, 2009.
Conference version in Proceedings of 38th Annual ACM Symposium on Theory of Computing
(STOC'06),
pages 618-633, Seattle, Washington, 2006.
quant-ph/0511200
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.
Hartmut Klauck, Robert Špalek, and Ronald de Wolf.
SIAM Journal on Computing,
36(5):1472-1493, 2007.
Conference version in Proceeding of 45th Annual IEEE Symposium on
Foundations of Computer Science
(FOCS'04), pages
12-21, Rome, Italy, 2004.
quant-ph/0402123 ECCC TR04-045
All Quantum Adversary Methods are Equivalent.
Robert Špalek and Mario Szegedy.
Theory of Computing,
2(1):1-18, 2006.
quant-ph/0409116
Lower Bounds on Quantum Query Complexity.
Peter Høyer and Robert Špalek.
Survey. Bulletin
of the European Association for Theoretical Computer
Science, 87:78-103, October 2005.
quant-ph/0509153
Quantum Fan-out is Powerful.
Peter Høyer and Robert Špalek.
Theory of Computing,
1(5):83-101, 2005.
quant-ph/0208043
Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs.
CWI, Amsterdam, and ILLC, Universiteit van Amsterdam, 2006.
ISBN 978-90-5776-155-3.
+NL
Quantum Circuits with Unbounded Fan-out.
Faculty of Sciences, Vrije Universiteit, Amsterdam, 2002.
Space Complexity of Quantum Computation.
Faculty of Mathematics and Physics, Charles University, Prague, 2002.