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

Abstract:


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.