AroraBarak-errata

From CRYPTUTOR

Jump to: navigation, search

Contributed Errata and Suggestions for Arora-Barak webdraft

The version referred to is "Web draft 2007-01-08 21:59."

Contents

1 Contributed Errata and Suggestions for Arora-Barak webdraft
- 1.1 Errata
- 1.2 Some Suggestions

Errata

Chapter 1

Section 1.2.1: In the definition of a TM, $Γ, Q$ are finite sets. After Figure 1.2, it should be $\delta(q,(\sigma_1,\ldots,\sigma_k))$ (not $\delta(q,(\sigma_1,\ldots,\sigma_{k+1}))$ ) and $z\in\{\mathsf{L},\mathsf{S},\mathsf{R}\}$ (not $\{\mathsf{L},\mathsf{SR}\}$ . On the next page, right at the top it says "The machine will be in state $q'$ , and the $k + 1$ heads will move Left, Right or Stay..." The machine only has $k$ heads. Also, may want to explicity say that $k\ge 2$ (first tape being input, and last being output).

Chapter 2

Page 2.10: At the bottom of the page (item 2), it should be $(\triangleright,\triangleright,q_{\mathsf{start}})$ (not $(\triangleright,\square,q_{\mathsf{start}})$ ).

Definition 2.21: $\textrm{coNP} = \{ L : \overline{L} \in \textrm{NP} \}$ , not $\overline{L} \in \textrm{P}$ .
Problem 2.2: The theorem to be proved is 2.9 not 2.
Problem 2.11: "...certificates of $f$ is equal to..." should be "...certificates of $x$ is equal to..."

Chapter 3

Proof of Thm 3.3: Overloading of $f$ .

Chapter 4

Example 4.9: $x = y$ (not $x\not=y$ ).
Section 4.3.1: First paragraph, "PSPACE = NSPACE" should read "PSPACE = NPSPACE".
Theorem 4.11: p4.8 line 2 - the second C' should be C", line 6 - the C' s should be C" s and the last C" should be C'.
Proof of Theorem 4.12: line -3 - the algorithm makes "M" recursive invocations, not "n". (Also M is overloaded in the proof).
Proof of Theorem 4.18: line 3 - reachable from "s", not "u".

Chapter 5

Remark 5.5: $\Pi_1^p = \textrm{coNP}$ (not $\Pi_2^p$ )
Proof of Theorem 5.15, page 98: "using choices $c_1,\dots,x_m$ " should be "using choices $c_1,\dots,c_m$ "

Chapter 6

Definition 6.21: depth $O (log i n)$ (not $O (log d n)$ ), and constant fan-in. Constant fan-in was not mentioned in the definition (perhaps that was the purpose of $d$ ?).
Before Theorem 6.24: "classes AC, NC" should just be NC. Should point out that $A C = N C$ before that.
Problem 6.11: $NC^1 \subseteq L$ (not $N C 1 = L$ ).
Definition 6.28: "i'th but" should be "i'th bit".

Chapter 7

Proof of Theorem 7.10: $k = 8 | x | 2 c + d$ (not $8 | x | 2 d + c$ ). Also, Corollary 7.11 should have $e^{-\frac{\delta^2}{2p}k}$ (not $e^{-\frac{\delta^2}{4}pk}$ ). Then plugging in $p\le 1$ (not $p\ge\frac12$ ), (and $δ = n - c / 2$ ), the bound is $e^{-\frac{n^{-2c}}{8}8n^{2c+d}}$ (not $e^{-\frac1{4n^{-2c}} \frac12 8n^{2c+d}}$ ).
Proof of Theorem 7.18: probability that $B r$ happens is at most $2 - n k$ (not $(1 - 2 - n) k$ ).

Chapter 8

Definition 8.10: The value of the probability expression should be $2 - 2 k$ not $2 - 2 n$ .

Proof of Claim 8.13.1: In the last line, $\frac12 \frac{|S|^2}{2^{2k}}$ (not $\frac12 \frac{|S|^2}{2^{k}}$ ).

Chapter 9

Example 9.1: Should be "induced subgraphs" (not "subgraphs").
Proof of Theorem 9.8: Clause gadget uses a pair of parallel edges (between the two lower nodes). Needs to be fixed by inserting a node with self-loop in the inner edge. XOR gadget seems to have errors: $v'$ should have an outgoing edge and $v$ should have an incoming edge to be consistent with the symbolic representation.
pg 9.12 (before Proof of Lemma 9.18): $φ + ψ(z)$ should be $\left( (z_0=z_{n+1}=\ldots=z_m=0 \wedge \phi(z_1,\ldots, z_n)=0) \vee (z_0=1 \wedge \phi(z_1,\ldots, z_m)=0) \right)$ (assuming $m\ge n$ ).

Other Chapters

Section 18.2.1, Equation (2): $\varphi \not\in {\mathsf{3SAT}}$ (not $\varphi\not\in L$ .
Example 11-6: $f_{k-1}(x_1, \ldots, x_{2^{k-1}-1})$ and $f_{k-1}(x_{2^{k-1}}, \ldots, x_{2^k})$ should be $f_{k-1}(x_1, \ldots, x_{2^{k-1}})$ and $f_{k-1}(x_{2^{k-1}+1}, \ldots, x_{2^k})$ , respectively (i.e, off-by-one). Base case should also be $k = 0$ , not 1.
Theorem 22.1: Should be " $μ(f) - 1$ is a lowerbound" (instead of $μ(f)$ ).

Appendices

A.4.1 Non-Prime Fields, second paragraph, where "For every prime $q$ and $k$ ..." should be "For every prime $q$ and every $k \in \N$ ... "

Some Suggestions

Complexity Zoo: See examples from lectures: 1 2 3
Section 3.3: Suggested figure/explanation for non-deterministic time hierarchy: slide.
Chapter 8: May want to add more details on AM. (e.g., Lecture adapted from Du and Ko; using "Alternating Threshold TMs.")

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/AroraBarak-errata"

Views

Personal tools

Log in / create account

Search

Toolbox