Abstract

We prove conditional hardness results for a number of string problems. Amongst others, this includes hardness for regular expression pattern matching, dynamic exact mathing with wildcards and two pattern indexing. The results are based on ongoing work with Clifford and Grønlund, and previous results with Munro, Nielsen and Thankachan.

Video Recording