Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DISTRIBUTION-FREE TESTING:
Reports tagged with Distribution-free testing:
TR20-123 | 17th August 2020
Nader Bshouty

An Optimal Tester for k-Linear

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.
We give a non-adaptive distribution-free ... more >>>




ISSN 1433-8092 | Imprint