Revisiting Convexity Testing
March 10, 2022, 12:20 in S6
In this talk, we will show that the number of distinct discrete derivatives, as opposed to the input size, is a better input parameter to express the complexity of convexity testing. We will present a nonadaptive convexity tester with query complexity O(log s/epsilon) and complement it with a nearly matching lower bound.
Joint work with Ilan Newman and Nithin Varma. Accepted for presentation at SOSA 2022.