Please note: This PhD seminar will be given online.
Abhinav Bommireddi, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Eric Blais
A body K ⊂ Rn is convex if and only if the line segment between any two points in K is completely contained within K or, equivalently, if and only if the convex hull of a set of points in K is contained within K.
We show that neither of those characterizations of convexity are robust: there are bodies in Rn that are far from convex — in the sense that the volume of the symmetric difference between the set K and any convex set C is a constant fraction of the volume of K — for which a line segment between two randomly chosen points x, y ∈ K or the convex hull of a random set X of points in K is completely contained within K except with exponentially small probability. These results show that any algorithms for testing convexity based on the natural line segment and convex hull tests have exponential query complexity.
The results in this talk are from the following paper: On Testing and Robust Characterization of Convexity. Joint work with Eric Blais. In, RANDOM 2020.