37 citations · 143 across the 23 of their papers we have counts for
Showing 2016 · cs.CCShow all
2 papers · 2 filters
cs.CC2016★ 3 cited
Randomized query complexity of sabotaged and composed functions
Shalev Ben-David, Robin Kothari
We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple B…
cs.CC2016★ 6 cited
Low-Sensitivity Functions from Unambiguous Certificates
Shalev Ben-David, Pooya Hatami, Avishay Tal
We provide new query complexity separations against sensitivity for total Boolean functions: a power separation between deterministic (and even randomized or quantum) query com…