Abstract
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.
Thesis Completion
2021
Semester
Spring
Thesis Chair/Advisor
Thankachan, Sharma
Degree
Bachelor of Science (B.S.)
College
College of Engineering and Computer Science
Department
Computer Science
Degree Program
Computer Science
Language
English
Access Status
Open Access
Length of Campus-only Access
1 year
Release Date
5-1-2022
Recommended Citation
Hoppenworth, Gary Thomas, "Fine-grained Lower Bounds for Problems on Strings and Graphs" (2021). Honors Undergraduate Theses. 1012.
https://stars.library.ucf.edu/honorstheses/1012