Weighted witness fingerprints
On this page · Permalink · Source line 550
CLAIM C07
19.1 A polynomial that distinguishes witnesses
On this page · Permalink · Source line 552
Let \(R:{\{0,1\}}^m\to{\{0,1\}}\) be a Boolean verifier, and let \(K\) be a characteristic-two field. Define the formal polynomial
The variables \(z_i\) in this expression are ordinary polynomial variables, not reduced by \(z_i^2=z_i\).
Theorem 19.1: Exact witness fingerprint
The polynomial \(P_R\) is identically zero if and only if \(R\) has no accepting witness. Its total degree is at most \(m\).
Proof
Different Boolean witnesses have different exponent vectors, so their monomials are distinct. Each accepting witness contributes coefficient one to its own monomial and cannot cancel another witness's term. The polynomial is zero exactly when there are no such terms. Each monomial uses at most \(m\) variables.
This avoids the cancellation of an unweighted parity count. It does not, by itself, give a small circuit for evaluating the sum.