65 citations · 230 across the 37 of their papers we have counts for
Showing quant-phShow all
3 papers · 1 filter
quant-ph2026
Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
Mark Bun, Joao F. Doriguello, John Kallaugher +1
We study the one-way communication complexity of the -Boolean Hidden Partition problem. Here, Alice is given an -bit string and Bob is given disjoint blocks of its ind…
quant-ph2018
Quantum algorithms and approximating polynomials for composed functions with shared inputs
Mark Bun, Robin Kothari, Justin Thaler
We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let be an -bit Boolean function and consider an -b…
quant-ph2017★ 18 cited
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Mark Bun, Robin Kothari, Justin Thaler
The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. Approximate degree is known to be a lowe…