Theory of Computational Complexity, 2nd Edition

This method has the following property.

Theorem 11.24

1. a. If L is the table of the linear function with coefficient vector a, Q is the table of the linear function with coefficient matrix , and for all , then the above assignment testing proof system accepts with probability 1.
2. b. For , if a_X, the assignment a restricted to variables X of the original Boolean circuit Ψ, is δ-far from every satisfying assignment to Boolean circuit Ψ, then the above assignment testing proof system rejects with probability at least , independent from L and Q.

To show this theorem, let us first prove a few lemmas.

Lemma 11.25

For any fixed nonzero Boolean matrix M and randomly selected n-dimensional Boolean vectors s and , with probability at most .

Proof

Let M_ij be a nonzero entry of ...