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.