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

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

Campus Access

Length of Campus-only Access

1 year

Release Date

5-1-2022

Share

COinS