MPM · Modern Pattern Matching

The advances in technology over the last decade and the massive amount of data passing through the internet has intrigued and challenged computer scientists, as the old models of computation used before this era are nowless relevant or too slow. New computational models have been suggested to tackle these technological advances. In the most basic sense, these modern models allow oneto scan the input only once, possible with small auxiliary memory. Nevertheless, modern techniques have also been introduced such as sparse recovery which has provento be a very useful tool for dealing with modern challenges, and the very popular notion of conditional lower bounds which has provided evidence of hardness for various algorithmic tasks based on very popular conjectures.Pattern matching plays a crucial role in many computing applications that can be seen in day to day life. However, its research community has only recently started gaining insight on what can be done in modern models, and is lagging behind in this respect. In particular, there are no algorithms for pattern matching problems that have utilized ideas from sparse recovery, and only recently has there been progress in proving conditional lower bounds for string problems. Furthermore, conditional lower bounds suffer from the lack of hardness conjectures which address time/space tradeoffs.This proposal will close this gap for many important pattern matching problems within the new models of computation, and will be the first to utilize modern algorithmic techniques, such as sparserecovery, and adapting them into the pattern matching world. Furthermore, this proposal will focus ondeveloping a theory for proving conditional time/space lower bounds, based on new hardness conjectures. This will greatly influence not only the pattern matching sub-field, but the entire algorithmic field at large.