Description: There have been a few cases where readers have requested additional information or clarification in regards to something in my doctoral dissertation. This document was created to provide additional information, clarifications, and address any typos.

Case 1: Found by VZN on 2-21-17

At the end of page 2 continuing on to the next page, the following is stated:

"Then, Karakostas, Lipton, and Viglas (2003) connected the hardness of intersection non-emptiness to the hardness of Boolean Satisfiability [36]. They showed that if the parameterized intersection problem for k DFA's is solvable in n^o(k) time, then the exponential time hypothesis is false."

Correction: Karakostas, Lipton, and Viglas (2003) showed that if intersection non-emptiness is solvable in n^o(k) time, then for every e > 0, SUBSET SUM is solvable in 2^{en} time and NTIME(n) is a subset of DTIME(2^{en}). However, they do not explicitly connect intersection non-emptiness to Boolean Satisfiability or ETH.

More recently, in Fernau and Krebs (2016), it is shown that if intersection non-emptiness is solvable in n^o(k) time, then ETH fails. We expand on this result in both subsections 7.2.2 and 7.2.3 of the dissertation.

Case 2: Typos found on 3-23-17

Typo: On page 47 near the top of the page, it says, "Let a c-uniform hypergraph H with vertices {v_i}_[n] be given." The family of vertices should be written as {v_i}_{i \in [n]} meaning the family of vectors of the form v_i for all i in [n].

Typo: On page 47 near the bottom of the page, it says, "The reduction is related to the reductions from Theorem 8 and 9." It is referring to Theorems 8 and 9 from reference [69]. These theorems can also be found in Chapter 7 (see Theorems 7.22 and 7.23).