Please note: This PhD defence will take place online.
Venkata Abhinav Bommireddi, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Eric Blais
Convexity plays a prominent role in both mathematics and computer science. It is defined for sets and functions, and many problems related to them can be solved efficiently given the guarantee that the set/function is convex. In this thesis, we focus on three problems related to convexity where we don’t have that guarantee.
The first problem we consider is the decision problem “Is a given unknown set convex?”. We study it under the framework of property testing, which is an approximate version of the decision problem. In property testing, instead of distinguishing objects that satisfy the property from the ones that do not, we distinguish objects that satisfy the property from the ones that are “far” from satisfying the property. We approach the problem of testing convex sets by studying a closely related problem of robust characterizations of convex sets in which we study different characterizations of convex sets and determine their robustness. We say a characterization is robust, if sets that are “far” from convex are also “far” from satisfying the characterization. We examine the robustness of three characterizations of convex sets: line characterization, convex hull characterization and supporting hyperplane characterization. And we discuss the implications of the robustness/non-robustness of these characterizations on the testing problem.
The second problem we consider is the decision problem “Is a given unknown function over the hypergrid [n]^d convex?”. The function is given via a valuation oracle, which we query to get the function value. Like the above problem, we study this problem also under the framework of property testing. 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 third problem we consider is minimizing convex functions over the hypergrid when given access to the comparison oracle to the function on the points in the hypergrid. The comparison oracle to a function takes as input two points and determines which of them has the lesser function value. The discrete (non-convex) nature of the domain makes the problem challenging, as here we no longer have the property that local minimum implies global minimum, which is crucial for the minimization of convex functions over continuous domains. Despite this, we show that there is a polynomial time and query minimization algorithm in two dimensions, and for any constant dimension greater than two, there is a quasi-polynomial time and query minimization algorithm.