All reports by Author Nader Bshouty:

__
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

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