Personal tools
You are here: Home CG seminar 2020 Testing polynomials for vanishing on Cartesian products
« September 2020 »
Log in

Forgot your password?

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


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.
Document Actions