I will give an overview on recent conditional lower bounds for some
basic (geometric) problems in P, then proceed with our recent upper
bounds for these problems. Particularly, 3SUM, Fréchet Distance, Dynamic
Time
Warping, Geometric Edit Distance,
Dominance Products, and high-dimensional Closest Pair problems. I will
review the results and touch some of the techniques used to obtain
them.
I will finish with our ongoing work towards breaking
the quadratic barrier of some archetypal geometric problems, such as
testing whether there are three collinear points in a set of n points in
the plane.
(All works are joint with Micha Sharir.)