40 citations · 40 across the 2 of their papers we have counts for
Showing quant-phShow all
3 papers · 1 filter
quant-ph2003
Robust Polynomials and Quantum Algorithms
Harry Buhrman, Ilan Newman, Hein Roehrig +1
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We co…
quant-ph2002★ 40 cited
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…
quant-ph2002
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…