56 citations · 98 across the 6 of their papers we have counts for
5 papers · 1 filter
Individual Communication Complexity
Harry Buhrman, Hartmut Klauck, Nikolai Vereshchagin +1
We initiate the theory of communication complexity of individual inputs held by the agents, rather than worst-case or average-case. We consider total, partial, and partially correc…
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…
New Applications of the Incompressibility Method: Part I
Tao Jiang, Ming Li, Paul Vitanyi
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…
New Applications of the Incompressibility Method: Part II
Harry Buhrman, Tao Jiang, Ming Li +1
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…