On depth-3 circuits and covering number: an explicit counter-example

Lianna Hambardzumyan, Hamed Hatami, Ndiamé Ndiaye

We give a simple construction of $n\times n$ Boolean matrices with $\Omega (n^{4/3})$ zero entries that are free of $2\times 2$ all-zero submatrices and have covering number $O(\log^4(n…