Quantitative Group Testing and the rank of random matrices

Uriel Feige, Amir Lellouche

Given a random Bernoulli matrix $A\in \{0,1{\}}^{m\times n}$, an integer $0<k<n$ and the vector $y:=Ax$, where $x\in \{0,1{\}}^n$ is of Hamming weight $k$, the objective…