Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
| Page | Location | Description |
| 5 | Line -5 before What is Polynomial Time? | The comma after the word algorithms should not be separated from the word by a space |
| 34 | First equation, last term on the left-hand side | uj should be vj, and uj' should be vj'. |
| 37 | Line 5 | The variable t should be from R+ rather than from Rn+ |
| 82 | Line 2 of Lemma 5.3.5 | The number of feasibility problems to be solved should be log 1/ε + 1 instead of log 1/ε (where the logarithm is binary) |
| 88 | Line 3 of Proposition 5.5.6 | "Then, for all k=1,2,.." should be "Then, for all k=2,3,..." |
| 95 | First equation | In the second term, the second quotient should be g2k+1/g2k instead of g2k/g2k+1 |
| 117 | Exercise 6.2 | In the claimed expression for gij, the ∇ symbol in the numerator should be removed |
| 144 | 8.3.25 | +ε should be -ε |
| 146 | 8.3.31 | The left hand side of the inequality should be divided by |E| |
| 147 | 8.3.37, line 4 of third bullet | The part "...disk Dq centered at q..." should read as "...disk Dq centered at q and disjoint from C..." |
| 158 | 9.1.11 | The upper bound on the required number of colors was further decreased by Kawarabayashi and Thorup in 2012 |
| 159 | Second º bullet | It is known at least since 1996 that vector and strict vector chromatic number may differ. An example can be found in Theorem 6.1.3. of the following diploma thesis: Clemens Gröpel, Über Approximationsalgorithmen zur Färbung k-färbbarer Graphen, die vektorchromatische Zahl und andere Varianten der Theta-Funktion, Humbold-University Berlin, 1996. |
| 160 | 9.3.2, second º bullet | The "3" should be in the numerator, not in the denominator. |
| 166 | Second-to-last line | The word "with" should be removed |
| 175 | 10.4.7 | There is a mistake in the calculation with the constants; the square root of 1/10 should have been taken, and this would spoil the result. A possible fix is to write 1/30 instead of 1/10 in the chain of inequalities in the fifth bullet of 10.4.6 (which is valid, just by a more precise calculation with the constants) and then have 2/√ 30 instead of the first 1/5 and 2/30 instead of the second one, which works. The factor of 2 in front of RA can actually be dropped with a bit more care. |
| 177 | Line 1 | The sentence should end as "...for which the correlation is at least 1/3 of the correlation of an optimal clustering." |
| 201 | 12.3.10, second bullet | The sentence should end as "...at most 90o." instead of "...at least 90o." |
| 201 | 12.3.10, third bullet | The inequality in the equation should be reversed, i.e. ≥ instead of ≤ |
| 225 | 13.3.31, second bullet | ...for all i,j... should be replaced by ...for all i≠j... |
| 234 | tenth-to-last line | The set {-1,1} should be {-1,1}d |