Talks
Fall 2015
![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/complexity_logo_final.png?itok=bgRCs3HD)
Fast Combinatorial 3SUM breaks BMM
Tuesday, December 1st, 2015, 2:45 pm–3:30 pm
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.