62 citations
9 papers
Quantum Algorithms for Matching and Network Flows
Andris Ambainis, Robert Spalek
We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrt{m+n} log n), finding a maximal non-bipartite matching in time…
Tight adversary bounds for composite functions
Peter Hoyer, Troy Lee, Robert Spalek
The quantum adversary method is a versatile method for proving lower bounds on quantum algorithms. It yields tight bounds for many computational problems, is robust in having many…
Self-Organized Forest-Fires near the Critical Time
J. van den Berg, R. Brouwer
We consider a forest-fire model which, somewhat informally, is described as follows: Each site (vertex) of the square lattice is either vacant or occupied by a tree.Vacant sites be…
All Quantum Adversary Methods are Equivalent
Robert Spalek, Mario Szegedy
The quantum adversary method is one of the most versatile lower-bound methods for quantum algorithms. We show that all known variants of this method are equivalent: spectral advers…
A Comparative Study of Arithmetic Constraints on Integer Intervals
Krzysztof R. Apt, Peter Zoeteweij
We propose here a number of approaches to implement constraint propagation for arithmetic constraints on integer intervals. To this end we introduce integer interval arithmetic. Ea…
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
Hartmut Klauck, Robert Spalek, Ronald de Wolf
A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overa…