PhD Seminar • Algorithms and Complexity • Testing Convexity of Functions Over Finite Domains

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.

To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/5935948458.