Robert Spalek

According to our database, Robert Spalek authored at least 17 papers between 2003 and 2013.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2013

Adversary Lower Bound for the Orthogonal Array Problem

Robert Spalek

CoRR, 2013

Adversary lower bound for the k-sum problem.

Aleksandrs Belovs, Robert Spalek

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Span-Program-Based Quantum Algorithm for Evaluating Formulas.

Ben Reichardt, Robert Spalek

Theory Comput., 2012

2011

Quantum Query Complexity of State Conversion.

Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Any AND-OR Formula of Size N Can Be Evaluated in Time N^1/2+o(1) on a Quantum Computer.

Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang

SIAM J. Comput., 2010

2009

A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs.

Andris Ambainis, Robert Spalek, Ronald de Wolf

Algorithmica, 2009

2008

A Dual Polynomial for OR

Robert Spalek

CoRR, 2008

The Multiplicative Quantum Adversary.

Robert Spalek

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

A Direct Product Theorem for Discrepancy.

Troy Lee, Adi Shraibman, Robert Spalek

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.

Hartmut Klauck, Robert Spalek, Ronald de Wolf

SIAM J. Comput., 2007

Negative weights make adversaries stronger.

Peter Høyer, Troy Lee, Robert Spalek

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

All Quantum Adversary Methods are Equivalent.

Robert Spalek, Mario Szegedy

Theory Comput., 2006

Quantum Algorithms for Matching and Network Flows.

Andris Ambainis, Robert Spalek

Proceedings of the STACS 2006, 2006

Quantum verification of matrix products.

Harry Buhrman, Robert Spalek

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

Quantum Fan-out is Powerful.

Peter Høyer, Robert Spalek

Theory Comput., 2005

Lower Bounds on Quantum Query Complexity.

Peter Høyer, Robert Spalek

Bull. EATCS, 2005

2003

Quantum Circuits with Unbounded Fan-out.

Peter Høyer, Robert Spalek

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003