13 citations · 25 across the 15 of their papers we have counts for
Showing 2019 · cs.CCShow all
2 papers · 2 filters
cs.CC2019
Testing convexity of functions over finite domains
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. 1. We provide a simplified version of the no…
cs.CC2019★ 6 cited
Optimal Separation and Strong Direct Sum for Randomized Query Complexity
Eric Blais, Joshua Brody
We establish two results regarding the query complexity of bounded-error randomized algorithms. * Bounded-error separation theorem. There exists a total function $f : \{0,1\}^n \to…