The motivation of this thesis is to present new lower bounds for important computational problems on strings and graphs, conditioned on plausible conjectures in theoretical computer science. These lower bounds, called conditional lower bounds, are a topic of immense interest in the field of fine-grained complexity, which aims to develop a better understanding of the hardness of problems that can be solved in polynomial time. In this thesis, we give new conditional lower bounds for four interesting computational problems: the median and center string edit distance problems, the pattern matching on labeled graphs problem, and the subtree isomorphism problem. These problems are of interest in the applied topics of computational biology and information retrieval, as well as in theoretical computer science more broadly.
Identifer | oai:union.ndltd.org:ucf.edu/oai:stars.library.ucf.edu:honorstheses-2112 |
Date | 01 January 2021 |
Creators | Hoppenworth, Gary Thomas |
Publisher | STARS |
Source Sets | University of Central Florida |
Language | English |
Detected Language | English |
Type | text |
Format | application/pdf |
Source | Honors Undergraduate Theses |
Page generated in 0.0015 seconds