All reports by Author Nader Bshouty:

__
TR20-123
| 17th August 2020
__

Nader Bshouty#### An Optimal Tester for k-Linear

__
TR19-156
| 7th November 2019
__

Nader Bshouty#### Almost Optimal Testers for Concise Representations

__
TR09-067
| 18th August 2009
__

Hanna Mazzawi, Nader Bshouty#### On Parity Check $(0,1)$-Matrix over $Z_p$

Revisions: 1

Nader Bshouty

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 >>>

Nader Bshouty

We give improved and almost optimal testers for several classes of Boolean functions on $n$ inputs that have concise representation in the uniform and distribution-free model. Classes, such as $k$-Junta, $k$-Linear Function, $s$-Term DNF, $s$-Term Monotone DNF, $r$-DNF, Decision List, $r$-Decision List, size-$s$ Decision Tree, size-$s$ Boolean Formula, size-$s$ Branching ... more >>>

Hanna Mazzawi, Nader Bshouty

We prove that for every prime $p$ there exists a $(0,1)$-matrix

$M$ of size $t_p(n,m)\times n$ where

$$t_p(n,m)=O\left(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})}\right)$$ such that every

$m$ columns of $M$ are linearly independent over $\Z_p$, the field

of integers modulo $p$ (and therefore over any field of

characteristic $p$ and over the real ...
more >>>