Why a short candidate parity row rejects many remaining false positives
A candidate is an ordered list of P independent pairs (e_j,c_j), each a uniform clause index and independent uniform bit. Repeated indices and zero coefficients remain part of the list; combine them modulo two only to form the resulting row. A remaining false positive violates at least m/P clauses, so the chance that no selected index hits its support is at most (1-1/P)^P<=exp(-1)<1/2. Given a hit, choose one hit position and fix all other coefficients. Its free uniform bit makes the row parity uniform, even with repeated indices. Hence each false positive is rejected with probability at least 1/4. Lists, not distinct resulting rows, carry the uniform distribution.
0
1
Tags
Math