# New Algorithms for Some Classical Problems in P

### Sunday, July 7th, 2019, 16:10

### Schreiber 309

### New Algorithms for Some Classical Problems in P

### Omer Gold, TAU

### Abstract:

The search for optimal algorithms is at the core of computer science since its emergence as a field. Yet for the majority of the studied problems we do not know whether state-of-the-art algorithms are the best possible.

Among the most popular problems in P are those that have standard algorithms that run in quadratic time or cubic time, such as 3SUM (quadratic time) and All-Pairs-Shortest-Paths (cubic time). Quadratic-time algorithms are also used in solving many basic matching problems between strings, curves, and point-sequences. In this thesis, we present improved algorithms and decision trees for the following core problems.

1) Improved decision tree for k-SUM and improved subquadratic-time algorithm for 3SUM.

2) The first subquadratic-time algorithms for computing Dynamic Time Warping and Geometric Edit Distance between two point-sequences on the line, breaking the 50-year old quadratic time barrier of these problems. Our algorithms work also for higher dimensions, when the underlying metric is polyhedral.

3) The first strongly-polynomial subcubic algorithm for computing high-dimensional closest pair under the L-infinity metric.

4) Showing that every directed unweighted graph has various subgraphs of subquadratic size that preserve the diameter of the original graph within an approximation factor less than 2. We call these subgraphs "diameter spanners", and we show efficient algorithms to construct them.

The talk is based on work developed as part of my Ph.D. studies under the supervision of Prof. Micha Sharir.