Efficiently Testing Sparse GF(2) Polynomials

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef +2

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function $f:\{0,1{\}}^n\to \{0,1\}$ is an $s$-sparse GF(2) polynomial ver…