The MATRIX PACKING DOWN problem asks to find a row permutation of a given (0,1)-matrix in such a way that the total sum of the first non-zero column indexes is maximized. We study the computational complexity of this problem. We prove that the MATRIX PACKING DOWN problem is NP-complete even when restricted to zero trace symmetric (0,1)-matrices or to (0,1)-matrices with at most two 1's per column. Also, as intermediate results, we introduce several new simple graph layout problems which...

Bref survol du théorème de non-plongement de J. Cheeger et B. Kleiner pour le groupe d’Heisenberg dans $L^1$.

We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class $f\mathit{\text{-PAD}}$ of all $f$-padded sets, if it is a subset of $\{x{10}^{f\left(\right|x\left|\right)-\left|x\right|-1};x\in {\{0,1\}}^{*}\}$). This is a continuation of the research of reducibilities to sparse and tally sets that were studied in many previous papers (for a good survey see [HOW1]). We show necessary and sufficient conditions to collapse and separate classes of bounded truth-table reducibilities to padded sets. We prove that depending on two properties of a...