Revisiting Convexity Testing

Abhiruk Lahiri

Charles University

March 10, 2022, 12:20 in S6

Abstract

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.