Title: (Geometric structure) Point location: an interface between geometry, machine learning and complexity

Abstract:
Point location is a basic problem in discrete and computational geometry. A given set of hyperplanes in d-dimensional space partitions the space into cells. Given an input point, the goal is to find as efficiently as possible to which cell it belongs. This problem is tightly connected to the problem of active learning in machine learning, where the goal is to infer the labels of unlabeled data points, while making a small number of queries; and to complexity theory, in particular to the complexity of certain key problems (such as 3-SUM) in the linear decision tree model. In this talk, I will describe these connections, some recent results and the challenges that remain.

Based on joint works with Max Hopkins, Daniel Kane, Gaurav Mahajan, Shay Moran and Jiapeng Zhang.

Live broadcast (and recording) link: 
https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=424913ee-0af1-4496-b66d-ae67005ed4c5