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.
Bachelor of Science (B.S.)
College of Engineering and Computer Science
Length of Campus-only Access
Hoppenworth, Gary Thomas, "Fine-grained Lower Bounds for Problems on Strings and Graphs" (2021). Honors Undergraduate Theses. 1012.