Non-Uniform ACC Circuit Lower Bounds

• p. 2 Section I.A, item 1

  o(2n/3) time algorithm for ACC circuit satisfiability implies

• p. 5 Theorem 3.1

  can be solved in O(2n/3/s(n)) time for every c

• p. 6 Section III, paragraph on [Wil10]

  a 2n/3/nω(1) time algorithm for

• p. 2 Section I.A, item 1

  which could only show that an o(2^{n/3}) time algorithm for ACC circuit satisfiability implies lower bounds [Wil10]

Only the authors can say what is right here.

Judge's note: Checked the page images. Page 2 (left column, item 1) says o(2^{n/3}). Page 5 (Theorem 3.1) requires O(2^{n/3}/s(n)) with s superpolynomial. Page 6 (right column) repeats 2^{n/3}/n^{ω(1)}. These are different hypotheses: o(2^{n/3}) is the weaker one. The introduction is an informal overview, but it states the earlier result's hypothesis differently from the paper's own formal statement of that result. Wording issue only; nothing in Section III depends on it.

Second check: another model agreed

• p. 8 Proof of Theorem 3.2, third paragraph

  A produces an ACC circuit C′x of S(n + c log n) size and n + c log n inputs

• p. 6 Lemma 3.1 statement, second bullet

  prints an ACC circuit C′x with n+d log n inputs, depth d′, and S(n + d log n) size

Judge's note: Pages 6 and 8 confirm the difference. Since c > 2d and S is monotone, the statement in the proof is a valid upper bound once the circuit is padded. The change from d to c is probably made because d means depth in Theorem 3.2, which is itself a clash of notation with the d of Lemma 3.1. This is a consistency point, not an error.

Second check: another model agreed

• p. 7 Proof of Lemma 3.1, EQUIV paragraph

  inputs, depth d′ + O(1), and size O(S(n + O(log n))), the

• p. 7 Proof of Lemma 3.1, definition of E

  S(n + (n + d log n) + d log n + O(1)) ≤ S(3n)

• p. 7 Proof of Lemma 3.1, final paragraph defining EQUIV

  size O(S(n + O(log n)))

• p. 7 Proof of Lemma 3.1, EQUIV step (right column, bottom)

  Since EQUIV(i) has n + d log n inputs, depth d′ + O(1), and size O(S(n + O(log n)))

Only the authors can say what is right here.

Judge's note: I checked page 7 (extract/png/main-p007.png). Left column: E(x,i,j) is guessed as an ACC circuit "of size S(n + (n + d log n) + d log n + O(1)) ≤ S(3n) and depth d′". Right column: EQUIV(i) outputs 1 iff C′x(i) ≠ E(x,i,kn^d+k), so it contains both the guessed C′x (size S(n+d log n)) and a copy of E with x and j fixed. Fixing inputs does not bound the guessed E's size below its stated bound. Reworking the step: size(EQUIV) = O(S(n+d log n) + S(2n+2d log n+O(1))) = O(S(3n)). For a fast-growing admissible S (Theorem 3.2 allows S(n) ≤ 2^{n/4}, e.g. S(t)=2^{t/4}), S(2n)/S(n+O(log n)) tends to infinity, so the printed bound O(S(n+O(log n))) does not follow as printed. The stated lemma still holds: its hypothesis (p.6–7, Lemma 3.1) lets the SAT algorithm handle circuits of depth 2d′+O(1) and size O(S(3n)+S(2n)n), which covers EQUIV at depth d′+O(1) and size O(S(3n)). So the step is faulty but the result stands (S3). The five quoted locations are the same single defect.

Second check: another model agreed

• p. 8 Section IV.A, first paragraph

  of its possible satisfying assignments:

• p. 8 Section IV.A intro

  on all of its possible satisfying assignments

Judge's note: Page 8 (right column) shows the quoted wording. Lemma 4.2 itself, and the text after it, say the circuit is evaluated on all 2^n assignments and the full truth table is printed. Page 9 says "all of its possible assignments". The word 'satisfying' misdescribes what the lemma does.

Second check: another model agreed

• p. 9 Reminder of Theorem 1.2

  ACC circuits of depth d and size 2nδ with MODm gates

• p. 9 Proof of Theorem 1.2

  in 2n−Ω(nδ) time, for some δ > ε

Judge's note: Page 9 shows that the proof concludes E^NP lacks depth-d ACC circuits of size 2^{n^ε}. This proves the theorem with its existential δ set to ε. Reusing δ with a different meaning (and δ > ε) makes it unclear what the proof establishes. Notation only; the result is unaffected.

Second check: another model agreed

• p. 2 Section I.A, paragraph 'Two known facts'

  Informally, this says that L ∈ NTIME[2^n] have

Judge's note: The page 2 image (right column) shows the wording as quoted. The singular subject L takes the plural verb 'have'. Copy-editing slip.

Second check: none (judge only)

• p. 6 Fact 3.2

  there is an ACC circuit Wx of size at most S(3n) with k ≤n + c log n inputs such that the variable assignment zi = W(i)

• p. 9 Section V, definition of succinct satisfying assignments

  there is a circuit Wx of poly(n) size with k ≤ n+c log n inputs such that the variable assignment zi = W(i)

Judge's note: Both page images show W_x introduced and then W(i) used in the same sentence (Fact 3.2 on page 6; the definition of succinct satisfying assignments on page 9). The meaning is clear from context, so this is cosmetic.

Second check: none (judge only)

• p. 11 References

  [Gree95] F. Green. Lower bounds for depth-three circuits with equals and mod-gates.

• p. 11 References

  [Gree95] F. Green. Lower bounds for depth-three circuits with

Judge's note: Searched the text layer: 'Gree95' appears only in the reference list. Green's work is cited only as [GKRST95] ("Green et al." on the related-work page). The page 11 crop confirms the entry. Uncited reference.

Second check: none (judge only)