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 | u_{j} should be v_{j}, and u_{j'} should be v_{j'}. |
37 | Line 5 | The variable t should be from R_{+} rather than from R^{n}_{+} |
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 g_{2k+1}/g_{2k} instead of g_{2k}/g_{2k+1} |
117 | Exercise 6.2 | In the claimed expression for g_{ij}, 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 D_{q} centered at q..." should read as "...disk D_{q} 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 90^{o}." instead of "...at least 90^{o}." |
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} |