Towards a characterization of idempotent Schur multipliers

It is conjectured that every idempotent Schur multiplier can be written as a finite sum of contractive idempotents. This conjecture is equivalent to the statement that any boolean matrix $A$ with factorization norm $\parallel A{\parallel }_{{\gamma }_2}$ at most $\gamma$ can be expressed as a signed sum $$A=\sum _{i=1}^L\pm B_i,$$ where, up to permutation of rows and columns, each $B_i$ is a blow-up of an identity matrix, and $L$ depends only on $\gamma$. In this note we show that if $A$ is an $n\times n$ boolean matrix with $\parallel A{\parallel }_{{\gamma }_2}\le \gamma$, then it admits such an expression with $L=2^{O({\gamma }^9)+{\log }^{\ast }\text{\hspace{0.17em}⁣}n}$, where ${\log }^{\ast }$ is the iterated logarithm function. As an application, any sequence of matrices with bounded factorization norm belongs to the complexity class ${\mathrm{P}}^{\mathrm{E}\mathrm{Q}}$ of communication problems with polylogarithmic equality-oracle complexity.