Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DISTRIBUTION-FREE TESTING:
Reports tagged with Distribution-free testing:
TR20-123 | 17th August 2020
A Boolean function $f:\{0,1\}^n\to \{0,1\}$ is $k$-linear if it returns the sum (over the binary field $F_2$) of $k$ coordinates of the input. In this paper, we study property testing of the classes $k$-Linear, the class of all $k$-linear functions, and $k$-Linear$^*$, the class $\cup_{j=0}^kj$-Linear.