# On Undecided LP, Clustering and Active Learning

## Sariel Har-Peled, University of Illinois

## Date and time: 2pm (New York time), Tuesday, March 2, 2021

## Place: Zoom

*For meeting ID and password see
mailing list announcement or contact the organizers.*

Given a colored point set, covered by (unknown) $k$ balls, which are
monochromatic (i.e., all the points covered by the same ball have the
same color). The access to the color of the points is provided via
colored nearest-neighbor queries. We show that one can correctly
deduce the color of all the points using a polylogarithmic number of
queries, in near linear time, if $k =O(1)$.

To this end, we study the Undecided Linear Programming problem, where
one is given a set of hyperplanes in the $d$-dimensional Euclidean
space. Each hyperplane is associated with two halfspaces, but which
one is the “real” constraint of the LP, can only be deduced by
querying an oracle. The task is to compute a feasible point, for the
“real” LP where all the constraints are committed to which
halfspace they define. We show that this problem can be solved using
$O(d^2 \log n)$ separation oracle calls, if processing time is not an
issue. Otherwise, we present a linear time algorithm that performs $O(
\log^d n)$ oracle queries.

Joint work with Stav Ashur.