# Testing polynomials for vanishing on Cartesian products

### Wednesday, June 3rd, 2020, 16:10

~~Checkpoint 480~~

### Zoom: Request the link from Dan Halperin or Golan Levy

### Testing Polynomials for vanishing on Cartesian products

### Esther Ezra, Bar Ilan University

### Abstract:

The 3SUM problem is to decide, given three sets A, B, C, of real numbers, whether there is a triple a \in A, b \in B, c \in C, which sums to zero.

We consider an extension of 3SUM where A, B, C, are three sets of points in the plane, and the sum function is replaced by a polynomial function of constant degree. This results in a family of problems referred to as "3POL". A central problem in this family is the so-called "collinearity testing" - one of the basic 3SUM-hard problems in computational geometry.

In this talk I will present several 3POL problems, including a few special cases of collinearity testing. I will describe subquadratic solutions for these problems in the algebraic decision tree model, these solutions are based on the polynomial partitioning method of Guth and Katz.

Joint work with Boris Aronov and Micha Sharir.