Which Regular Expression Patterns are Hard to Match?
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Identifies which regular-expression pattern classes make string matching computationally hard by studying complexity of matching specific operators and pattern constructions. Uses fine-grained complexity methods to classify patterns (e.g., concatenation, union, Kleene star, plus) according to whether matching them admits subquadratic algorithms or is likely conditional-hard, and provides reductions and algorithmic upper bounds connecting these classes to standard hardness conjectures.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:24Regular expression membership
- 2:42Regular expression pattern matching
- 3:24Regular expressions: applications
- 5:30Examples of homogeneous regexp matching
- 6:28Our results: Classification of homogeneous regexps
- 11:09Hardness for type
- 11:45Orthogonal Vectors Conjecture
- 12:13High level idea
- 13:01Simplifying assumptions
- 14:10Vector gadgets
- 16:34Final construction
- 21:37Conclusions