1.2k citations · 3.7k across the 62 of their papers we have counts for
5 papers · 1 filter
Communication Complexity Lower Bounds by Polynomials
Harry Buhrman, Ronald de Wolf
The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower boun…
Bounds for Small-Error and Zero-Error Quantum Algorithms
H. Buhrman, R. Cleve, R. de Wolf +1
We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-o…
Quantum Bounded Query Complexity
Harry Buhrman, Wim van Dam
We combine the classical notions and techniques for bounded query classes with those developed in quantum computing. We give strong evidence that quantum queries to an oracle in th…
Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method
Harry Buhrman, Jaap-Henk Hoepman, Paul Vitanyi
We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies. In most models fo…
Mutual Search
Harry Buhrman, Matthew Franklin, Juan A. Garay +3
We introduce a search problem called ``mutual search'' where \agents, arbitrarily distributed over sites, are required to locate one another by posing queries of the form `…