Additional Discussion & Typos

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).

Case 3: Added on 5-12-17 in response to helpful comments from Turbo

Informal Discussion: A fixed level of a parameterized problem is a decision problem that is obtained by fixing the value of the parameter.

The complexity of the fixed levels of a parameterized problem may differ from the complexity of the parameterized problem. For example, it is possible that there could exist an efficient algorithm for every fixed level, yet there does not exist an efficient algorithm for the parameterized problem.

One may equivalently view this as the difference between the existence of a non-uniform algorithm vs a uniform algorithm. The existence of a non-uniform algorithm is weaker than the existence of a uniform algorithm.

In this work, we consider the complexity of fixed levels of parameterized problems and the complexity of the parameterized problems themselves. In the latter case, we try to explicitly write the term uniform algorithm and enclose the problem abbreviation in parentheses.

Case 4: Typos found on 9-26-17

Typo: Page 64 under "Exact Time Complexity". It should say, "Intersection non-emptiness problem for 3k unary DFA's can be solved in n^1.4k time by a reduction to triangle finding in a sparse graph." The coeficient "3" was missing in the original sentence.

Recently, an improved algorithm was found running in roughly n^1.19k time. This will appear in an upcoming paper.

Please feel free to send me questions and I will add additional discussion here when appropriate. Thank you very much for reading.

Back to Homepage