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

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

2008

A Dual Polynomial for OR

Robert Spalek

CoRR, 2008

Span-program-based quantum algorithm for evaluating formulas.

Ben Reichardt, Robert Spalek

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 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

Negative weights make adversaries stronger.

Peter Høyer, Troy Lee, Robert Spalek

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

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

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

2006

A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs.

Andris Ambainis, Robert Spalek, Ronald de Wolf

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 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

All Quantum Adversary Methods Are Equivalent.

Robert Spalek, Mario Szegedy

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

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

Hartmut Klauck, Robert Spalek, Ronald de Wolf

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

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