# An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

### Wednesday, April 3rd, 2019, 16:10

### Schreiber 309

### An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

### Esther Ezra, BIU

### Abstract:

n 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in R^d and if D\geq 1 is an integer, then there is a d-variate polynomial P of degree at most D so that each connected component of R^d \setminus Z(P) intersects O(n/D^{d-g}) sets from S (where Z(p) is the zero set of P). Such a polynomial is called a "*generalized partitioning polynomial*". We present a randomized algorithm that computes such polynomials efficiently---the expected running time of our algorithm is linear in |S|. Our approach exploits the technique of *quantifier elimination* combined with that of *\epsilon-samples*.

Joint work with Pankaj Agarwal, Boris Aronov, and Josh Zahl