Sankardeep Chakraborty

Optimal Labeling Schemes for $\Gamma$-Free Matrices

We study labeling schemes for $p \times q$ $\Gamma$-free binary matrices, which do not contain a submatrix of the form $\Gamma = \begin{pmatrix} 1&1 \\ 1&0 \end{pmatrix}$. We give a labeling scheme that uses $O(\log^2 N)$-bit labels for rows and columns, where $N=p+q$, such that any matrix entry can be determined from...