PhD Seminar • Algorithms and Complexity • Minimizing Discrete Convex Functions

Please note: This PhD seminar will be given online.

Abhinav Bommireddi, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Eric Blais

Minimizing convex functions over convex domains is well studied but relatively little is known about minimizing convex functions over discrete domains. Minimizing convex functions over discrete domains is challenging because we no longer have the property that local minimum implies global minimum, which is crucial for efficient minimization of convex functions over convex domains. 

In this talk, we consider the problem of minimizing convex functions over the hypergrid [n]^d, where [n] = {1, 2, \ldots, n}, and show that there is a polynomial time minimization algorithm in two dimensions, and for any constant dimension greater than two, there is a quasi-polynomial time minimization algorithm.

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