ECCC-Report TR14-114https://eccc.weizmann.ac.il/report/2014/114Comments and Revisions published for TR14-114en-usWed, 27 Aug 2014 16:31:21 +0300
Paper TR14-114
| An Alternative Proof of an $\Omega(k)$ Lower Bound for Testing $k$-linear Boolean Functions |
Roei Tell
https://eccc.weizmann.ac.il/report/2014/114We 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 affine 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 affine 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}$.Wed, 27 Aug 2014 16:31:21 +0300https://eccc.weizmann.ac.il/report/2014/114