56 citations · 98 across the 6 of their papers we have counts for
4 papers · 1 filter
Quantum Zero-Error Algorithms Cannot be Composed
Harry Buhrman, Ronald de Wolf
We exhibit two black-box problems, both of which have an efficient quantum algorithm with zero-error, yet whose composition does not have an efficient quantum algorithm with zero-e…
Combinatorics and Quantum Nonlocality
Harry Buhrman, Peter Hoyer, Serge Massar +1
We use techniques for lower bounds on communication to derive necessary conditions (in terms of detector efficiency or amount of super-luminal communication) for being able to repr…
On the Importance of Having an Identity or, is Consensus really Universal?
Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri +1
We show that Naming-- the existence of distinct IDs known to all-- is a hidden but necessary assumption of Herlihy's universality result for Consensus. We then show in a very preci…
Quantum Property Testing
H. Buhrman, L. Fortnow, I. Newman +1
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x…