##### Personal tools
You are here: Home 2020 Testing polynomials for vanishing on Cartesian products
« September 2020 »
September
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
27282930

# Testing polynomials for vanishing on Cartesian products

### 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.