2024-11-08
Talk in the International Workshop on Combinatorics and Geometry about Algorithms for data approximation.
In this talk, we discuss two problems related to data approximation: combinatorial discrepancy and simplicial partitions. We present efficient algorithms to solve them in geometric settings. For the former we build an algorithm based on a new mathematical game that we introduce and the celebrated result from Lovett and Meka that solves the set discrepancy question for abstract set system. For the latter, we present a fast algorithm that heuristically minimizes a potential function that we show lead to low crossing number partitions when they exist.
Slides