Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Tight Bounds for Regular Expression Pattern Matching and Membership (Master thesis)
Speaker:Philipp Schepper
coming from:Fachrichtung Informatik - Saarbr├╝cken
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 16 January 2020
Duration:30 Minutes
Building:E1 4
The classical O(nm) time algorithms for regular expression pattern matching and membership can be improved by a factor of about log^{3/2}(n).

Instead of focusing on general patterns we focus on homogeneous patterns of bounded depth in this thesis only.
For them a classification splitting the types in easy (strongly sub-quadratic) and hard (essentially quadratic time under SETH) is known.
We take a fine-grained look at the hard pattern types from this classification and show that few types allow super-poly-logarithmic improvements while the algorithms for the other pattern types can only be improved by a constant number of log-factors, assuming the Formula-SAT Hypothesis.

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Karl Bringmann, 01/07/2020 07:56 AM -- Created document.