Time+Place: | Thursday 07/01/2016 14:30 Room 337-8 Taub Bld. |

Title: | Beyond Conditional Lower Bounds: Overcoming the Square Root Phenomenon in Theory and Practice. |

Speaker: | Tsvi Kopelowitz - CS-Lecture http://web.eecs.umich.edu/~tsvi/ |

Affiliation: | University of Michigan, Dept. of EE and CS |

Host: | Roy Schwartz |

It has recently become very popular to prove that there are inherent polynomial barriers to speeding up solutions for algorithmic and data structure problems. Such barriers are demonstrated by proving conditional lower bounds, based on the conjectured hardness of some well established problems, such as 3SUM, APSP (All Pairs Shortest Paths), SETH (Strong Exponential Time Hypothesis) and Combinatorial BMM (Boolean Matrix Multiplication). These conditional lower bounds imply that it is unlikely to solve these problems faster. In particular, this line of research has established connections between several problems that exhibit the square root phenomenon, where the fastest running algorithms have a runtime that depends on the square root of some parameter of the input. In this talk I will show that proving conditional polynomial time lower bounds for such problems is not the end of the story, by introducing approaches for tackling this inherent square root barrier. In particular, I will demonstrate the usefulness of these approaches for problems that arise in practical virus-detection schemes, for approximating the Hamming distance for all alignments of a text and a pattern, and for several other (dynamic) data structure and graph problems. Short Bio: Tsvi Kopelowitz is a postdoctoral fellow at University of Michigan in Ann Arbor, hosted by Seth Pettie. Before this he was a postdoctoral fellow at the Weizmann Institute hosted by Robert Krauthgamer. He completed his Ph.D. at Bar-Ilan university under the supervision of Moshe Lewenstein. His research focuses on dynamic graph algorithms and data structures, pattern matching and text indexing, and algorithms for distributed computing.