How hard is recovering a binary matrix from its check sums?
Parity problem

It is clear that $\sum_i R_i \equiv \sum_j C_j \pmod{2}$ must hold if any solution exists. On the other hand, if this holds then some solution exists. Let $R$ contain $a$ ones, and let $C$ contain $b$ ones. We can assume without loss of generality that $a \geq b$. Arrange the rows and the columns so that
$$
\begin{align*}
&amp;(R_1,C_1) = \cdots = (R_{n-a},C_{n-a}) = (0,0) \\
&amp;(R_{n-a+1},C_{n-a+1}) = \cdots = (R_{n-b},C_{n-b}) = (1,0) \\
&amp;(R_{n-b+1},C_{n-b+1}) = \cdots = (R_n,C_n) = (1,1)
\end{align*}
$$
Note that there is an even number of occurrences of the second type. We now construct a block diagonal matrix with the following blocks:
$$
\begin{pmatrix}
0
\end{pmatrix}
 \times (n-a), \quad
\begin{pmatrix}
1 &amp; 0 \\ 1 &amp; 0
\end{pmatrix}
\times (a-b), \quad
\begin{pmatrix}
1
\end{pmatrix}
\times b
$$

Sum problem

When the actual sums are given, we have the digraph realization problem, which can be solved efficiently.