| 2011 | FOCS | Quantum Query Complexity of State Conversion. | Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy |
| 2008 | STOC | Span-program-based quantum algorithm for evaluating formulas. | Ben Reichardt, Robert Spalek |
| 2007 | FOCS | Any AND-OR Formula of Size N can be Evaluated in time N | Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang |
| 2007 | STOC | Negative weights make adversaries stronger. | Peter Hyer, Troy Lee, Robert Spalek |
| 2006 | SODA | Quantum verification of matrix products. | Harry Buhrman, Robert Spalek |
| 2006 | STOC | A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs. | Andris Ambainis, Robert Spalek, Ronald de Wolf |
| 2006 | STACS | Quantum Algorithms for Matching and Network Flows. | Andris Ambainis, Robert Spalek |
| 2005 | ICALP | All Quantum Adversary Methods Are Equivalent. | Robert Spalek, Mario Szegedy |
| 2004 | FOCS | Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. | Hartmut Klauck, Robert Spalek, Ronald de Wolf |
| 2003 | STACS | Quantum Circuits with Unbounded Fan-out. | Peter Hyer, Robert Spalek |