The PCP Theorem by Gap Amplification
Journal of the ACM, 2007 · paper · Computer science
Gives a new, combinatorial proof of the PCP theorem by repeatedly amplifying the unsatisfied fraction of a constraint system, using graph powering on expanders together with a composition step. It also constructs PCPs of nearly linear length checkable with a constant number of queries.
Checked: PDF from cs.umd.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
7 findings
Substance Lemma 9.2 states "UNSATa∪b(H′) > δ·min(1/16, (β1β2√t/2)ε)", and the proof's conclusion repeats "δ · (β1β2√t/2 · ε)". The first case of the proof only derives "UNSATa∪b(H′) ≥ 1/2 UNSATb(H) ≥ εδ/4 · β1 · β2√t", a factor 2 smaller, and with ≥ rather than >.
- p. 31 Lemma 9.2, second bullet
UNSATa∪b(H′) > δ·min( 1/16, (β1β2√t/2)ε)
- p. 33 Proof of Lemma 9.2, first case
UNSATb(H) ≥εδ/4 · β1 · β2√t.
- p. 33 Proof of Lemma 9.2, conclusion
or at least δ · (β1β2√t/2 · ε)
- p. 32 The Graph G′, third bullet
Since this value was min( 1/16, (β1β2√t/2)ε)
Only the authors can say what is right here.
Judge's note: I reworked the steps on pp.31–33. From (15) and (16), UNSAT_b(H) ≥ εδ/2·β1β2√t. H's constraints carry half the weight of H′, so UNSAT(H′) ≥ εδβ1β2√t/4. The lemma and the closing sentence claim εδβ1β2√t/2, which the proof does not supply. The second case (δ/16) matches. Theorem 9.1 is unaffected because t is chosen large, but the lemma's stated bound is left without proof as printed. The same /2 constant is reused on p.32 (third bullet).
Second check: another model agreed
Report a problem with this finding
Reference or label Section 1.5 says the full definition of an assignment tester 'can be found in Section 9', but the definition is Definition 2.2 (Section 2.4, repeated in Section 5); Section 9 contains no definition.
- p. 8 Section 1.5, Assignment Testers
definition (which can be found in Section 9)
- p. 8 Section 1.5, 'Assignment Testers' paragraph
Without getting into the full definition (which can be found in Section 9)
- p. 11 Section 2.4, Definition 2.2
Definition 2.2 (Assignment Tester) An Assignment Tester with alphabet Σ0 and rejection probability
- p. 28 Section 8.3
that is an assignment tester (also called a PCP of Proximity), as defined in Definition 2.2.
Judge's note: Page 8 image shows the pointer to Section 9. Page 11 image shows Definition 2.2 (Assignment Tester) in Section 2.4. The text extract shows Definition 2.2 repeated in Section 5, and Section 8.3 refers to it 'as defined in Definition 2.2'. A search of Section 9 (pp.30-33) finds Theorem 9.1 and its proof but no definition.
Second check: another model agreed
Report a problem with this finding
Wording Definition 4.1 says 'let Xv be a d-regular graph on vertex set [v] ... (as guaranteed by Lemma 2.1)', but Lemma 2.1 gives d0-regular graphs, and Lemma 4.1 says prep1(G) is '(d0 + 1)-regular' with 'd = d0 + 1'.
- p. 13 Definition 4.1, Edges
let Xv be a d-regular graph on vertex set [v] and edge expansion at least h0 (as guaranteed by Lemma 2.1)
- p. 13 Lemma 4.1
is a (d0 + 1)-regular
- p. 13 Definition 4.1, Edges
Let Xv be a d-regular graph on vertex set [v]
Judge's note: Page 13 image: Xv is called d-regular. Lemma 2.1 on p.8 gives d0-regular expanders. Lemma 4.1 and its proof set d = d0+1 as the degree of G', which is cloud degree d0 plus one external edge. So the cloud expander must be d0-regular. Degree check: d0 + 1 = d requires deg(Xv) = d0.
Second check: another model agreed
Report a problem with this finding
Wording In the LTC test of the Corollary 8.6 proof, "choose a random i ∈ [n] and a random j ∈ {1, 2, . . . , ℓ − 1}, and accept iff wi = wi+j·ℓ" uses stride ℓ. In the code a^ℓ b with a ∈ Σ^n, the copies are n apart, so the index should be i+j·n.
- p. 29 Proof of Corollary 8.6, test step 2
accept iff wi = wi+j·ℓ
- p. 30 Proof of Corollary 8.6
Clearly, every w ∈ CN passes the test with probability 1.
- p. 29 Proof of Corollary 8.6, testing algorithm step 2
choose a random i ∈ [n] and a random j ∈ {1, 2, . . . , ℓ − 1}, and accept iff wi = wi+j·ℓ
Only the authors can say what is right here.
Judge's note: From the p.29 image, C_N = {a^ℓ b : a ∈ C′_n ⊂ Σ^n} and ℓ = 2m/(δn) is the number of copies. Copy j of position i sits at i + j·n. Counterexample: n=2, ℓ=3, a=(0,1). The word is w=010101.., and for i=1, j=1 the test compares w1=0 with w4=1, so it rejects a codeword. That contradicts p.30's 'Clearly, every w ∈ CN passes the test with probability 1'. With the stride changed to j·n the sketch goes through, so the corollary itself stands.
Second check: another model agreed
Report a problem with this finding
Wording The proof of Corollary 9.3 reads "if for some i∗ < k, ε(Pk) ≥ 1/t then for every i > i∗ ε(Pi) ≥ 1/t". The hypothesis should be on ε(P_{i∗}); as printed it assumes the conclusion.
- p. 34 Proof of Corollary 9.3, last paragraph
if for some i∗< k, ε(Pk) ≥1/t then for every i > i∗
- p. 34 Proof of Corollary 9.3, last paragraph
if for some i∗ < k, ε(Pk) ≥ 1/t then for every i > i∗ ε(Pi) ≥ 1/t
Only the authors can say what is right here.
Judge's note: The p.34 image shows the subscript k. The parallel argument on p.12 uses UNSAT(G_{i∗}). With i∗ the argument goes through via item 2, so the result stands.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Lemma 6.4 (p.37) justifies the upper bound on X_a with the lower bound on k: "since n − √n < m and pn − c√n ≤ k it follows that 1 − k/m ≥ 1 − p − (c+1)/√n"; a lower bound on 1 − k/m needs the upper bound k ≤ pn + c√n.
- p. 37 Proof of Lemma 6.4, upper bound on X_a
Similarly, since n − √n < m and pn − c√n ≤ k it follows that 1 − k/m ≥ 1 − p − (c+1)/√n
- p. 37 Proof of Lemma 6.4, upper bound on X_a
since n − √n < m and pn − c√n ≤ k it follows that 1 − k/m ≥ 1 − p − (c+1)/√n
Only the authors can say what is right here.
Judge's note: Read on page image p.37. My reworking: k ≥ pn − c√n bounds k only from below, so it cannot give a lower bound on 1 − k/m. Counterexample to the cited implication: n=10000, p=0.5, c=1, m=9901, k=10000 satisfies pn − c√n ≤ k, but 1 − k/m < 0 < 1 − p − (c+1)/√n = 0.48. The lemma's hypothesis |k − pn| ≤ c√n also gives k ≤ pn + c√n. With m > n − √n, that yields k/m < (p + c/√n)/(1 − 1/√n) ≤ p + (c+1)/√n for n ≥ ((c+1)/(1−p))², so the displayed inequality and the lemma still hold. The step is faulty as written but the stated result stands, so S3.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Proposition B.3 (p.40) states "for every i ∈ [n], E[µ(i)] = τ and E[f(i)µ(i)] = −1 + τ", but the test's definition of µ (p.38) gives E[µ(i)] = −τ, as the paper's own (−τ)^{|α|} and (−τ)^{|α\γ|} terms use.
- p. 40 Proof of Proposition B.3, after the expansion of W
for every i ∈[n], E[µ(i)] = τ and E[f(i)µ(i)] = −1 + τ
- p. 40 Proof of Proposition B.3, after the expansion of W
E[µ(i)] = τ and E[f(i)µ(i)] = −1 + τ
- p. 40 first expectation
ˆA2 α(−τ)|α|
- p. 40 first expectation
Â2α(−τ)|α|
Only the authors can say what is right here.
Judge's note: On p.38, step 2 sets µ(y) = −1 if f(y) = 1, and if f(y) = −1 sets µ(y) = 1 with probability 1−τ and −1 with probability τ. So E[µ] = ½(−1) + ½(1−2τ) = −τ, and E[fµ] = −½ − ½(1−2τ) = −1 + τ, which matches the second value. Page image p.40 shows "E[µ(i)] = τ" with no minus sign, while the displays use (−τ)^{|α|} and (−τ)^{|α\γ|}. The sign slip is only in the stated justification; the computations are unaffected. Checked with τ = 1/100.
Second check: another model agreed
Report a problem with this finding
35 minor (typos and the like; most checked by the judge only)
Reference or label [8] is cited for an NTIME(t) ⊆ PCP[log(t·polylog t), polylog t] result ("Theorem 8.2 ([8, Theorem 2.2])"; "The construction of [8] has shorter proof-length, n · poly log n"). Reference [8] is listed as "E. Ben-Sasson and M. Sudan. Robust locally testable codes and products of codes. In RANDOM ..., 2004."
- p. 27 Theorem 8.2
Theorem 8.2 ([8, Theorem 2.2])
- p. 35 Reference [8]
Robust locally testable codes and products of codes
- p. 7 Section 1.5
The construction of [8] has shorter proof-length, n · poly log n
- p. 7 Section 1.5
The construction of [8] has shorter proof-length, n · poly log n, but the number of queries it requires is poly log n.
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that the quasi-linear PCP with polylog queries is Ben-Sasson & Sudan's 'Simple PCPs with poly-log rate and query complexity' (STOC 2005), not their RANDOM 2004 paper on robust LTCs and products of codes. The images confirm that the entry title and the attributed result are as quoted (p.7, p.27, p.35). The text calls it a 'recent result' cited to its Theorem 2.2. Only the authors can confirm which paper is intended.
Second check: another model agreed
Report a problem with this finding
Reference or label p.15: "We conclude with a stronger corollary of Lemmas 4.1 and 4.2 that will be useful in Section 8." The corollary is used only in Section 9 (proof of Lemma 9.2, p.33).
- p. 15 Before Corollary 4.3
that will be useful in Section 8.
- p. 33 Proof of Lemma 9.2
Indeed, recall Corollary 4.3
Judge's note: Opened both crops. A text search finds Corollary 4.3 only at its statement (p.15) and in the proof of Lemma 9.2 on p.33 ("Indeed, recall Corollary 4.3"). Section 8 (pp.26-29) does not use it; it refers forward to 'the next section' (Section 9) for the assignment-tester variant. Section 8.3 depends on Section 9, so the pointer is loosely defensible, but the corollary is actually used in Section 9.
Second check: another model agreed
Report a problem with this finding
Wording Eq. (6) on p.20 states "|F|/|E| ≤ min(UNSATσ(G), 1/t)", but p.21 says "Combining the above with (6)" to get Ω(√t)·min(UNSATσ(G),1/t) ≤ Ω(√t)·|F|/|E|, which needs the reverse direction.
- p. 20 Equation (6)
|F|/|E| ≤ min(UNSATσ(G), 1/t)
- p. 21 Combining with (6)
Ω(√t) · min(UNSATσ(G), 1/t) ≤ Ω(√t) · |F|/|E|
Only the authors can say what is right here.
Judge's note: Checked pp.20-21. As printed, (6) is true: there is equality when UNSAT<1/t, and otherwise ⌊|E|/t⌋/|E| ≤ 1/t. The chain on p.21 needs a lower bound on |F|/|E|. The only bridge is the remark "equality holds if we ignore the rounding error". The needed bound holds up to a constant when |E| ≥ 2t, which Ω can absorb. So the stated result stands, but the cited inequality points the wrong way for the step.
Second check: another model agreed
Report a problem with this finding
Wording p.20 says σ⃗(v) gives "values for every vertex w within distance t/2 of v". Yet Definition 6.1 (σ⃗(v0)_{v_{i−1}}, σ⃗(vt)_{vi}) and X_{u,ℓ} ("ℓ-step walk from u ends in a vertex w for which σ⃗(w)_u = a", for ℓ ∈ I) use opinions at walk length up to t/2+√(t/2).
- p. 20 Proof of Lemma 6.1
interpreted as values for every vertex w within distance t/2 of v
- p. 20 Definition 6.1
Both ⃗σ(v0)vi−1 = σ(vi−1) and ⃗σ(vt)vi = σ(vi).
- p. 22 Definition of X_{u,ℓ} and (9)
ℓ-step walk from u ends in a vertex w for which ⃗σ(w)u = a
Only the authors can say what is right here.
Judge's note: Checked pp.20-23. For i∈I, p_u uses X_{u,i−1} and p_v uses X_{v,t−i}. Whenever i−1 > t/2 or t−i > t/2 (one of these always happens unless i is near t/2), the walk can end at a vertex farther than t/2 from u, where σ⃗(w)_u is not defined. The paper gives no convention for this case. My reworking: treat undefined opinions as unequal. Then only k∈K matters in (10), and k ≤ pt/2 + c√(t/2) < t/2 for large t, so the argument goes through. The stated lemma therefore survives, but the step refers to undefined quantities as written.
Second check: another model agreed
Report a problem with this finding
Wording p.23: "p_u, p_v > τ/(2|Σ|) because both i − 1, t − i are at most √(t/2) away from t/2". With I = {t/2 − √(t/2) < i ≤ t/2 + √(t/2)}, i − 1 can lie more than √(t/2) below t/2.
- p. 23 End of proof of Lemma 6.2
because both i −1, t −i are at most √t/2 away from t/2
- p. 21 Definition of I
t/2 − √(t/2) < i ≤ t/2 + √(t/2)
- p. 22 Lemma 6.4 hypothesis
ℓ0 < ℓ1 − √ℓ1 ≤ ℓ2 < ℓ1 + √ℓ1
- p. 23 Section 6.2
recall I = { t/2 − √(t/2) < j ≤ t/2 + √(t/2) }
Only the authors can say what is right here.
Judge's note: Checked I on p.21, condition (9) and Lemma 6.4 on p.22, and the claim on p.23. Example: t=10 gives I={3,...,7}; for i=3, i−1=2 and |2−5|=3 > √5≈2.236 (3*3=9>5). So (9), which requires |ℓ−t/2| ≤ √(t/2), does not cover ℓ=i−1 at the lower end. The bound for t−i is fine. This is an off-by-one: widening the window or shifting I repairs it and changes only τ. The j-for-i variable change when I is recalled is immaterial.
Second check: another model agreed
Report a problem with this finding
Wording Proposition 6.5 bounds E[Z_iZ_j] by (|F|/|E|)(|F|/|E| + |λ|^{j−i−1}), but the next display bounds the sum with "|F|/|E| + |λ|^{j−i}" and then sums |λ|^i from i=1.
- p. 23 Proposition 6.5
|λ|j−i−1
- p. 23 Display after Proposition 6.5
|F| |E| + |λ|j−i
- p. 23 Proposition 6.5 statement
|F|/|E| + |λ|^{j−i−1}
- p. 23 Display after Proposition 6.5 (sum over i<j)
|F|/|E| + |λ|^{j−i}
Only the authors can say what is right here.
Judge's note: On the p.23 image, the proposition has exponent j−i−1, and the proof on p.24 ends with |λ|^{j−i−1}. The display uses j−i. With normalised |λ|<1, |λ|^{j−i} < |λ|^{j−i−1}, so the first ≤ does not follow from the proposition as stated. Using the exponent j−i−1 and summing from 0 changes only the constant, so the result Σ = O(√t)|F|/|E| and Lemma 6.3 stand.
Second check: another model agreed
Report a problem with this finding
Wording p.24: "where λ < 1 is the normalized second eigenvalue of the graph G", but the next sentence writes the bound as "|F|/|E| + (|λ|/d)^{j−2}", which divides by d again.
- p. 24 Proof of Proposition 6.5
where λ < 1 is the normalized second eigenvalue of the graph G
- p. 24 same paragraph
is at most |F| |E| + ( |λ| d )j−2
- p. 24 same paragraph, next sentence
is at most |F|/|E| + (|λ|/d)^{j−2}
Judge's note: The p.24 image shows both the declaration of λ as normalised (<1) and the (|λ|/d)^{j−2} term in consecutive sentences. Elsewhere λ is unnormalised (Lemma 6.1: λ < d). The symbol is used with both meanings within one paragraph. The intended bound is clear.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Proposition 7.3, p.26: "Altogether this occurs with probability at least (1 − δ)δ ≥ δ/2". This holds only for δ ≤ 1/2, and the proof places no such restriction on δ = rdist(σ, SAT(ψ)).
- p. 26 Proof of Proposition 7.3
Altogether this occurs with probability at least (1 −δ)δ ≥δ/2
Only the authors can say what is right here.
Judge's note: Checked p.26 and p.25. δ is only said to be > 0 and can be as large as 1, and Theorem 7.1 allows δ∈[0,1]. For δ>1/2, (1−δ)δ < δ/2. My reworking: use a case-split threshold of min(δ/2, 1/4) in place of δ/2. Then the close case gives probability ≥ δ/2 and the far case gives Ω(δ), so Proposition 7.3 still holds. The step is faulty as printed; the stated result stands.
Second check: another model agreed
Report a problem with this finding
Wording Theorem 9.1 is stated two ways. On p.28–29 it reads "one can construct an assignment-tester with the same alphabet and rejection probability at least min(2ε,1/t) ... bounded by at most a constant factor". On p.30 it reads "There exists t ∈ N and |Σ0| > 1 ... with alphabet Σ0 ... C depends only on |Σ|".
- p. 28 Section 8.3, statement of Theorem 9.1
one can construct an assignment-tester with the same alphabet and rejection
- p. 30 Section 9, Theorem 9.1
one can construct an assignment-tester with alphabet Σ0 and
- p. 30 Section 9
construct an assignment-tester with alphabet Σ0 and rejection probability
- p. 28 Section 8.3, Theorem 9.1
construct an assignment-tester with the same alphabet
Only the authors can say what is right here.
Judge's note: I checked pages 28, 29 and 30. The first statement is introduced with 'Formally,' and carries the same label, but it promises the same alphabet Σ. The second, together with the proof's composition step (p.32: 'constraints in G′ are over alphabet Σ0'), yields Σ0. The two versions agree only when Σ = Σ0. Corollary 8.4 still works with the fixed Σ0, so this is a mismatch between the two statements and leaves the paper's results intact.
Second check: another model agreed
Report a problem with this finding
Wording The text says "let C′_n ⊂ Σ^n be an error correcting code with rate and distance Θ(n)". Rate is defined in §2.3 as (1/n)log|C| ≤ 1, so dimension (or rate Θ(1)) is meant.
- p. 29 Proof of Corollary 8.6
be an error correcting code with rate and distance Θ(n)
Judge's note: I checked the p.29 image. Section 2.3 (text layer) defines rate as (1/n)log_|Σ||C| and refers to codes 'for which both the distance and the dimension are Θ(n)'.
Second check: another model agreed
Report a problem with this finding
Wording Equation (14) defines σ2(w)_v for "all v reachable from w by a t/2-step walk in G". Here w ∈ V_H is a vertex of prep(G), and H = (prep(G))^t, so the walk should be in prep(G).
- p. 31 Equation (14)
for all v reachable from w by a t/2-step walk in G
Judge's note: I checked p.31. Step 3 of the comparison test on the same page says 'Take a t/2-step random walk in prep(G)', and the text separates G from prep(G) throughout this section.
Second check: another model agreed
Report a problem with this finding
Wording The proof of Lemma 9.2 justifies combining (15) and (16) with "observing that by assumption 1/t is clearly larger than ε > UNSATb1(prep(G))". The assumption is only ε < 1/t, and nothing bounds UNSATb1(prep(G)) above by ε.
- p. 33 Proof of Lemma 9.2, combining (15) and (16)
1/t is clearly larger than ε > UNSATb1(prep(G)),
Only the authors can say what is right here.
Judge's note: From p.33, (15) gives only a lower bound UNSAT_b1 ≥ εδβ1/2, and b is arbitrary, so UNSAT_b1 can be close to 1, which exceeds ε. The step that is needed, min(1/t, UNSAT_b1) ≥ εδβ1/2 because εδβ1/2 < ε < 1/t, is true, so the derived bound stands. The stated inequality ε > UNSAT_b1, however, is false in general.
Second check: another model agreed
Report a problem with this finding
Typo Past tense written as 'lead' instead of 'led' in three places on p.2: 'but it soon lead to a list', '(see [6, 14, 5]) lead to the following theorem', 'The techniques that lead to the proof were mainly algebraic'.
- p. 2 Introduction, history paragraph
but it soon lead to a list
- p. 2 same paragraph
(see [6, 14, 5]) lead to the following theorem
- p. 2 next paragraph
The techniques that lead to the proof
- p. 2 Introduction
The techniques that lead to the proof were mainly algebraic
Judge's note: Page 2 image shows 'lead' in all three past-tense sentences. Quotes c and d are the same sentence.
Second check: none (judge only)
Report a problem with this finding
Typo Sentence fragment with no main clause: 'Rather than the classical notion of a proof as a sequential object that if erroneous in even one place can easily prove a false statement.'
- p. 2 After Theorem 1.1
Rather than the classical notion of a proof as a sequential object that if erroneous in even one place can easily prove a false statement.
Judge's note: Page 2 image shows a full stop after 'statement', followed by a capitalised 'The PCP theorem provides...'. The 'Rather than' clause has no main clause.
Second check: none (judge only)
Report a problem with this finding
Typo 'discovered by Feige et. al. [12]' has a stray period after 'et'; it should be 'et al.'
- p. 2 Section 1.1
discovered by Feige et. al. [12]
Judge's note: Page 2 image, Section 1.1, shows 'et. al.'.
Second check: none (judge only)
Report a problem with this finding
Typo n is used for the number of variables ('V = {v1, . . . , vn}', indices in [n]) and also for the number of constraints ('C = {c1, . . . , cn}') on pp.2-3.
- p. 2 Definition 1.1 and the following paragraph
Let V = {v1, . . . , vn} be a set of variables
- p. 2 CSP definition
given a system of constraints C = {c1, . . . , cn} over a set of variables V
- p. 3 max-CSP paragraph
Let C = {c1, . . . , cn} be a set of constraints over a set of variables V
Judge's note: Pages 2-3 images confirm the same symbol n in both roles within a few lines. Readers will likely take both as generic sizes, so this is a minor notational overload.
Second check: none (judge only)
Report a problem with this finding
Typo Unclosed parenthesis in the proof of Lemma 1.3: '(where q and c are constants. For each fixed random bit pattern...'
- p. 3 Proof of Lemma 1.3, (⇒)
(where q and c are constants. For each fixed
- p. 3 Proof of Lemma 1.3, (⇒) bullet
decides whether to accept or reject (where q and c are constants. For each fixed
- p. 3
accesses q = O(1) bits from the proof and decides whether to accept or reject (where q and c are constants.
Judge's note: Page 3 image: no closing parenthesis follows 'constants.' anywhere in the bullet.
Second check: none (judge only)
Report a problem with this finding
Typo Missing word: 'the rejection probability of Ver is exactly equal UNSAT(Cx)' should read 'exactly equal to'.
- p. 3 Proof of Lemma 1.3, (⇒) bullet
the rejection probability of V er is exactly equal UNSAT(Cx)
Judge's note: Page 3 image confirms the wording.
Second check: none (judge only)
Report a problem with this finding
Typo Lowercase sentence start after a question mark: 'How do we make the unsat value double? this is done through three operations'.
- p. 5 Section 1.2, paragraph before 'Graph Powering'
How do we make the unsat value double? this is done through three operations
Judge's note: Crop of page 5 confirms the lowercase 'this'.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Theorem 1.5 writes 'β2 = β(λ, d, |Σ|) > 0', whereas Lemma 1.6 and Lemma 6.1 write β2 = β2(λ, d, |Σ|).
- p. 11 Proof of Theorem 1.5, step 2
β2 = β(λ, d, |Σ|) > 0
Judge's note: Page 11 image confirms the missing subscript. The text extract shows β2(λ, d, |Σ|) in Lemma 1.6 and Lemma 6.1. Cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo Definition 4.1 writes 'set V′ = ∪v∈v[v]'; the index set should be V.
- p. 13 Definition 4.1, Vertices
set V′ = ∪v∈v[v]
Judge's note: Page 13 image shows a lowercase v as the index set of the union. The next bullet correctly writes ∪_{v∈V}.
Second check: none (judge only)
Report a problem with this finding
Typo Number disagreement: 'These transformation are described in Definitions 4.1 and 4.2' should read 'These transformations are'.
- p. 13 Section 4, first paragraph
These transformation are described
Judge's note: Page 13 image confirms the wording.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Lemma 4.1 writes 'of the appropriate expander Xdv', but Definition 4.1 names the cloud expander Xv.
- p. 14 Proof of Lemma 4.1, second case
of the appropriate expander Xdv
Judge's note: Page 14 image shows the subscript d_v. Definition 4.1 on p.13 names the expander X_v.
Second check: none (judge only)
Report a problem with this finding
Typo p.17: "Here it is really the ratio between the the probability of rejection" has a duplicated "the".
- p. 17 Remark after Definition 2.2 (repeated)
the ratio between the the probability of rejection
- p. 17
t is really the ratio between the the probability of reje
Judge's note: The page image (crop C017-a) shows "the the". Both quoted locations are the same occurrence.
Second check: code check
Report a problem with this finding
Typo p.17: "such that ℓ ≤ c · log2 Σ" uses the alphabet Σ where its size |Σ| is meant.
- p. 17 Definition of linear dimension, before Definition 5.1
such that ℓ≤c · log2 Σ
Judge's note: The crop shows log_2 Σ without bars. Σ is a set; elsewhere the paper writes the size as |Σ| (e.g. p.28: "log |Σ| = poly log n"). The meaning is clear.
Second check: none (judge only)
Report a problem with this finding
Typo Equation (4), p.19, and the definition of m2^{-1}, p.31, write "max arg_{a∈Σ}" where Equation (2) writes "arg max".
- p. 19 Lemma 6.1, Equation (4)
max arga∈Σ
- p. 31 Section 9, definition of m2^{-1}
max arga∈Σ
Judge's note: Both crops show "max arg" with subscript a∈Σ. The text layer has "arg max" at Eq. (2) on p.13. This is a notational inconsistency; the intended operator is clear.
Second check: none (judge only)
Report a problem with this finding
Typo p.24: "A string A is said to be folded over true if for every f, A(−f) = −A(f)", although in Section 7 A : L → {0,1} and f is {0,1}-valued. The same paragraph uses "1 − f".
- p. 24 Section 7, folded strings
for every f, A(−f) = −A(f)
- p. 24 same paragraph
For every pair f, 1 −f ∈L
Judge's note: The p.24 image confirms the ±1-style notation in a {0,1} setting. The intended condition is A(1−f) = 1 − A(f), as the paragraph's own "For every pair f, 1 − f ∈ L" and the item on p.25 (negate the value of 1 − f) indicate.
Second check: none (judge only)
Report a problem with this finding
Typo p.24: "a second vertex by taking a random walk form v" should read "from v".
- p. 24 End of Section 6
taking a random walk form v
- p. 24 Radhakrishnan modification paragraph
taking a random walk form v that stops
Judge's note: Crop C026-a shows "form v". Both quotes are the same occurrence.
Second check: none (judge only)
Report a problem with this finding
Typo p.26 display: "rdist(σ, SAT(ψ)] = δ" has a parenthesis closed by a square bracket.
- p. 26 Proof of Proposition 7.3
rdist(σ, SAT(ψ)] = δ
Judge's note: The p.26 image shows the mismatched bracket in the display Pr_i[σ(x_i) ≠ a'(x_i)] = rdist(σ,a') ≥ rdist(σ, SAT(ψ)] = δ.
Second check: none (judge only)
Report a problem with this finding
Typo Typo: "can be decoded via m1^{-1} into as assignment for G" should read "into an assignment".
- p. 32 Proof of Lemma 9.2, opening
into as assignment for G
Judge's note: Visible in the p.32 image.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [6] prints "M. Ben-or". The acknowledgements on the same page spell the name "Miki Ben-Or".
- p. 35 Reference [6]
M. Ben-or, S. Goldwasser, J. Kilian, and A. Wigderson.
- p. 35 Acknowledgements
Miki Ben-Or
Judge's note: Both crops show the lowercase 'or' in the reference and 'Ben-Or' in the acknowledgements.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [19] prints "A qualitysize tradeoff for hashing" with the hyphen missing (quality-size).
- p. 36 Reference [19]
A qualitysize tradeoff for hashing
Judge's note: The crop of p.36 shows 'qualitysize' as one word.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [16] prints "A sample of samplers a computational perspective on sampling" with only a blank gap where a separator (dash or colon) appears to have been dropped.
- p. 36 Reference [16]
A sample of samplers a computational perspective on sampling
Judge's note: The crop of p.36 shows a wider gap and no punctuation mark.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [23] prints the URL "http://www.math.ias.edu/ boaz/ExpanderCourse/" with a blank where the tilde (~boaz) should be.
- p. 36 Reference [23]
http://www.math.ias.edu/ boaz/ExpanderCourse/
Judge's note: The crop of p.36 shows a space and no tilde glyph.
Second check: none (judge only)
Report a problem with this finding
Typo Footnote 6 (p.38) reads "since due to the stronger property of having the rejection probability proportional to the distance"; the word "since" is superfluous.
- p. 38 Footnote 6
since due to the stronger property
Judge's note: Footnote 6 on page image p.38 contains "since due to", which is ungrammatical. Deleting "since" fixes it.
Second check: none (judge only)