Robert Spalek

Aleksandrs Belovs, Robert Spalek: Adversary lower bound for the k-sum problem. ITCS 2013: 323-328

Robert Spalek: Adversary Lower Bound for the Orthogonal Array Problem. CoRR abs/1304.0845 (2013)

Ben Reichardt, Robert Spalek: Span-Program-Based Quantum Algorithm for Evaluating Formulas. Theory of Computing 8(1): 291-319 (2012)

Aleksandrs Belovs, Robert Spalek: Adversary Lower Bound for the k-sum Problem. CoRR abs/1206.6528 (2012)

Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy: Quantum Query Complexity of State Conversion. FOCS 2011: 344-353

Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang: Any AND-OR Formula of Size N Can Be Evaluated in Time N^1/2+o(1) on a Quantum Computer. SIAM J. Comput. 39(6): 2513-2530 (2010)

Andris Ambainis, Robert Spalek, Ronald de Wolf: A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. Algorithmica 55(3): 422-461 (2009)

Troy Lee, Adi Shraibman, Robert Spalek: A Direct Product Theorem for Discrepancy. IEEE Conference on Computational Complexity 2008: 71-80

Robert Spalek: The Multiplicative Quantum Adversary. IEEE Conference on Computational Complexity 2008: 237-248

Ben Reichardt, Robert Spalek: Span-program-based quantum algorithm for evaluating formulas. STOC 2008: 103-112

Robert Spalek: A Dual Polynomial for OR. CoRR abs/0803.4516 (2008)

Hartmut Klauck, Robert Spalek, Ronald de Wolf: Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. SIAM J. Comput. 36(5): 1472-1493 (2007)

Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang: Any AND-OR Formula of Size N can be Evaluated in time N^1/2+o(1) on a Quantum Computer. FOCS 2007: 363-372

Peter Høyer, Troy Lee, Robert Spalek: Negative weights make adversaries stronger. STOC 2007: 526-535

Robert Spalek, Mario Szegedy: All Quantum Adversary Methods are Equivalent. Theory of Computing 2(1): 1-18 (2006)

Harry Buhrman, Robert Spalek: Quantum verification of matrix products. SODA 2006: 880-889

Andris Ambainis, Robert Spalek: Quantum Algorithms for Matching and Network Flows. STACS 2006: 172-183

Andris Ambainis, Robert Spalek, Ronald de Wolf: A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs. STOC 2006: 618-633

Peter Høyer, Robert Spalek: Lower Bounds on Quantum Query Complexity. Bulletin of the EATCS 87: 78-103 (2005)

Peter Høyer, Robert Spalek: Quantum Fan-out is Powerful. Theory of Computing 1(1): 81-103 (2005)

Robert Spalek, Mario Szegedy: All Quantum Adversary Methods Are Equivalent. ICALP 2005: 1299-1311

Andris Ambainis, Robert Spalek, Ronald de Wolf: A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. CoRR abs/quant-ph/0511200 (2005)

Hartmut Klauck, Robert Spalek, Ronald de Wolf: Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. FOCS 2004: 12-21

Hartmut Klauck, Robert Spalek, Ronald de Wolf: Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. CoRR quant-ph/0402123 (2004)

Hartmut Klauck, Robert Spalek, Ronald de Wolf: Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. Electronic Colloquium on Computational Complexity (ECCC)(045) (2004)

Peter Høyer, Robert Spalek: Quantum Circuits with Unbounded Fan-out. STACS 2003: 234-246

Peter Høyer, Robert Spalek: Quantum Circuits with Unbounded Fan-out. CoRR quant-ph/0208043 (2002)