1.2k citations · 2.5k across the 41 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
quant-ph2014★ 1 cited
Query complexity in expectation
Jedrzej Kaniewski, Troy Lee, Ronald de Wolf
We study the query complexity of computing a function f:{0,1}^n-->R_+ in expectation. This requires the algorithm on input x to output a nonnegative random variable whose expectati…
cs.CC2014★ 6 cited
Some upper and lower bounds on PSD-rank
Troy Lee, Zhaohui Wei, Ronald de Wolf
Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic proper…
quant-ph2014
Rational approximations and quantum algorithms with postselection
Urmila Mahadev, Ronald de Wolf
We study the close connection between rational functions that approximate a given Boolean function, and quantum algorithms that compute the same function using postselection. We sh…