Adversary Lower Bound for the Orthogonal Array Problem.
Robert Špalek.
arXiv:1304.0845 [quant‑ph]
A dual polynomial for OR.
Robert Špalek.
arXiv:0803.4516 [cs.CC]
Adversary Lower Bound for the k-sum Problem.
Aleksandrs Belovs and Robert Špalek.
In Proceeding of 4th Annual ACM Conference on Innovations in
Theoretical Computer Science (ITCS'13), pages 323-328,
Berkeley, California, 2013.
arXiv:1206.6528 [quant‑ph]
Quantum query complexity of state conversion.
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario
Szegedy.
In Proceeding of 52nd Annual IEEE Symposium on
Foundations of Computer Science (FOCS'11), pages 344-353,
Palm Springs, California, 2011.
arXiv:1011.3020 [quant‑ph]
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.
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
Span-program-based quantum algorithm for evaluating formulas.
Ben Reichardt and Robert Špalek.
Theory of Computing,
8(13):291-319, 2012.
Conference version 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
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.