Selected papers

Homepage
Technical reports:
Adversary Lower Bound for the Orthogonal Array Problem.
Robert Špalek.
Abs Bib PDF
arXiv:1304.0845 [quant‑ph]
A dual polynomial for OR.
Robert Špalek.
Abs Bib PDF
arXiv:0803.4516 [cs.CC]
Conference papers:
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.
Abs Bib PDF
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.
Abs Bib PDF
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.
Abs Bib PDF
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.
Abs Bib PDF
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.
Abs Bib PDF
quant‑ph/0611054 computing Adv
Quantum Algorithms for Matching and Network Flows.
Andris Ambainis and Robert Špalek. In Proceedings of 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS'06), pages 172-183, LNCS 3884, Marseille, France, 2006.
Abs Bib PDF
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.
Abs Bib PDF
quant‑ph/0409035
Journal papers:
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.
Abs Bib PDF
arXiv:0710.2630 [quant‑ph] PDF computing wsize
Bib PDF
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.
Abs Bib PDF
quant‑ph/0703015
Bib PDF
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.
Abs Bib PDF
quant‑ph/0511200
Bib PDF
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.
Abs Bib PDF
quant‑ph/0402123 ECCC TR04-045
Bib PDF
All Quantum Adversary Methods are Equivalent.
Robert Špalek and Mario Szegedy. Theory of Computing, 2(1):1-18, 2006.
Conference version in Proceedings of 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), pages 1299-1311, LNCS 3580, Lisboa, Portugal, 2005.
Abs Bib PDF
quant‑ph/0409116
Bib PDF
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.
Abs Bib PDF
quant‑ph/0509153
Quantum Fan-out is Powerful.
Peter Høyer and Robert Špalek. Theory of Computing, 1(5):83-101, 2005.
Conference version as Quantum Circuits with Unbounded Fan-out in Proceedings of 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS'03), pages 234-246, LNCS 2607, Berlin, Germany, 2003.
Abs Bib PDF
quant‑ph/0208043
Bib PDF
Master's and Doctoral theses:
Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs.
CWI, Amsterdam, and ILLC, Universiteit van Amsterdam, 2006. ISBN 978-90-5776-155-3.
Abs +NL Bib PDF
Quantum Circuits with Unbounded Fan-out.
Faculty of Sciences, Vrije Universiteit, Amsterdam, 2002.
Bib PDF
Space Complexity of Quantum Computation.
Faculty of Mathematics and Physics, Charles University, Prague, 2002.
Bib PDF

My co-authors