779 citations · 2.6k across the 35 of their papers we have counts for
1 paper · 2 filters
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…