Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-114 | 27th August 2014 16:29

#### An Alternative Proof of an $\Omega(k)$ Lower Bound for Testing $k$-linear Boolean Functions

TR14-114
Authors: Roei Tell
Publication: 27th August 2014 16:31
We provide an alternative proof for a known result stating that $\Omega(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 affi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ffine 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 $\Omega(s)$ lower bound for testing $s$-sparse polynomials of degree $d$, for any $d\in\mathbb{N}$.