Robert Spalek
- Research Area(s)
- Algorithms and Theory
Google Publications
-
Adversary Lower Bound for the k-sum Problem
Aleksandrs Belovs, Robert Spalek
Proceeding of 4th Annual ACM Conference on Innovations in Theoretical Computer Science (ITCS'13) (2013), pp. 323-328
-
Span-program-based quantum algorithm for evaluating formulas
Ben Reichardt, Robert Spalek
Theory of Computing, vol. 8(13) (2012), pp. 291-319
-
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben Reichardt, Robert Spalek, Mario Szegedy
Proceeding of 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS'11) (2011), pp. 344-353
Previous Publications
-
Any AND-OR formula of size N can be evaluated in time N^(½+o(1)) on a quantum computer.
Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Spalek, Shengyu Zhang
SIAM Journal on Computing, vol. 39(6) (2010), pp. 2513-2530
-
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
Andris Ambainis, Robert Spalek, Ronald de Wolf
Algorithmica, vol. 55(3) (2009), 422–461
-
A direct product theorem for discrepancy
Troy Lee, Adi Shraibman, Robert Spalek
Proc. of 23rd IEEE Complexity (CCC'08) (2008), pp. 71-80
-
The Multiplicative Quantum Adversary
Proc. of 23rd IEEE Complexity (2008)
