An Alternative Proof of an Ω(k) Lower Bound for Testing k-linear Boolean Functions.
Roei Tell · Electronic colloquium on computational complexity · 2014
We provide an alternative proof for a known result stating that Ω(k) queries are needed to test k-sparse linear Boolean functions. Similar to the approach of Blais and Kane (2012), we reduce the proof to the analysis of Hamming weights of vectors in a ne subspaces of the Boolean hypercube. However, we derive our proof from a general result by Linial and Samorodnitsky (2002) that upper bounds the number of vectors with the same Hamming weight in every large a ne subspace of the Boolean hypercube. Our line of argument is reminiscent of a technique that is common in communication complexity, and it allows us to derive the lower bound from Linial and Samorodnitsky's result quite easily. We publish this proof as a self-contained excerpt from a broader work (2014), since it might be of independent interest. In the other work we also extend the result to an Ω(s) lower bound for testing s-sparse polynomials of degree d, for any d ∈ N.