Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Simon Litsyn:

TR07-098 | 2nd October 2007
Tali Kaufman, Simon Litsyn, Ning Xie

Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of ... more >>>

ISSN 1433-8092 | Imprint