Please note: This PhD seminar will be given online.
Abhinav Bommireddi, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Eric Blais
Testing convexity of functions is an approximate version of the decision problem “Is a given unknown function convex?”. In this, given an unknown function, we need to determine if it is convex or “far” from convex. The unknown function is given via a valuation oracle which we query to get the function value at a point. We refer to an algorithm that performs the testing task as non-adaptive if it submits all its queries before looking at the function value on any of the points, and adaptive otherwise.
We show that any non-adaptive algorithm that tests convexity of functions f : [n]^d \to \mathbb{R} for d \geq 2, has query complexity that is linear in n and exponential in d. To understand if adaptivity helps, we consider the problem of testing convexity of functions over a stripe, [3] x [n], and show that there exists an adaptive testing algorithm that does exponentially better than any non-adaptive one.
The results in this talk are from the following paper: Testing Convexity of Functions Over Finite Domains. Joint work with: Aleksandrs Belovs, Eric Blais. In, SODA 2020.