4
$\begingroup$

Given a binary $n \times n$ matrix, we would like to decide whether there is a row or a column which consists entirely of $1$s. The caveat is that after we read an entry of the matrix, it is erased. How much space do we need in order to solve this task?

If entries do not get erased, the task can be solved in space $O(\log n)$ by going over the matrix twice. With this restriction, we have the following simple algorithm:

  • Read the matrix row by row, maintaining the AND of all rows read so far. Return "Yes" if an all-$1$ row is ever encountered, or if the final AND contains a $1$ entry.

This algorithm uses $n + O(\log n)$ bits of space. I am counting space in number of bits, rather than number of words.

Can this be improved?

(Question due to Yoav Ben-Dov.)

$\endgroup$

1 Answer 1

5
$\begingroup$

The computation of the erasing machine can be expressed as a read-once branching program.

A branching program is a DAG with a unique source and two sinks, labelled "Yes" and "No". Each non-sink is labelled by an input variable, and has exactly two outgoing edges, labelled $0$ and $1$. Essentially, this is a compressed decision tree, and it computes a function in the same way as a decision tree. A $T$-query space-$S$ algorithm can be converted into a branching program of size $T 2^S$, and so a lower bound on the size of a branching program computing a certain function gives a lower bound on the space needed to compute the function.

A branching program is read-once if every execution path reads every input variable at most once. Equivalently, every source-to-sink path reads every input variable at most once (since each such path corresponds to a possible execution path). An erasing algorithm converts into a read-once branching program.

In the rest of this answer, we give a lower bound of $\Omega(2^n)$ on the size of a read-once branching program solving the task in the question. In our model, we only charge the algorithm a time unit for reading an entry, and so $T \leq n^2$. Therefore every algorithm for the task uses space at least $\log(\Omega(2^n)/n^2) = n - O(\log n)$.

The proof uses an idea due to Tal Roth.


Suppose we are given a read-once branching program solving the given task. Given an input $X$, its execution traces a path $v_0 \to v_1 \to \cdots \to v_N$, where $v_0$ is the source and $v_N$ is a sink. Let $\DeclareMathOperator{\par}{par}\par(X,v_t)$ denote the partial input which corresponds to the nodes queries on the path $v_0 \to \cdots \to v_t$.

In the sequel, we will consider only "No" inputs. For such inputs, some entries can be inferred even if they are not queried directly. This is the case if an entry is the only entry not queried on its row (or column), and all other entries on the same row (or column) are known to be $1$. Let $\inf(X,v_t)$ denote $\par(X,v_t)$ together with these inferred entries.

The partial input $\inf(X,v_t)$ rules out a row (or column) if it contains a $0$ on the row (or column). Let $R(X,v_t)$ be the set of rows rules out by $\inf(X,v_t)$, and let $C(X,v_t)$ be the set of columns ruled out.

The proof is driven by the following crucial observation.

Claim. If $X,Y$ are two "No" inputs whose execution path goes through the same node $v$, then $R(X,v) = R(Y,v)$ and $C(X,v) = C(Y,v)$.

Proof. Let $S_X,S_Y$ be the supports of $\par(X,v),\par(Y,v)$. Every path from $v$ to a sink is not allowed to query $S_X \cup S_Y$.

The proof is by contradiction. Suppose that $R(X,v) \not\subseteq R(Y,v)$, say $i \in R(X,v) \setminus R(Y,v)$. Let $j$ be such that $\inf(X,v)_{i,j} = 0$. We consider several cases.

Case 1: $(i,j) \notin S_X$. In this case, $\par(X,v)_{i,j}$ was inferred, and so, without loss of generality, all other entries on row $i$ of $\par(X,v)$ are $1$. Since $i \notin R(Y,v)$, there must be at least two entries on row $i$ not in $S_Y$, and so some entry $(i,j') \notin S_Y$ with $j' \neq j$. This entry is queried on the source-to-$v$ path taken by $X$, and so cannot be queried by any $v$-to-sink path.

Consider the path emanating from $v$ in which we answer all queries on row $i$ by $1$ and all other queries by $0$. On the one hand, this is consistent with the input obtained from $\par(X,v)$ by filling all missing entries on row $i$ with $1$ and all other missing entries with $0$. This is a "Yes" input.

On the other hand, this is consistent with the input obtained from $\par(Y,v)$ by filling all missing entries on row $i$ other than $(i,j')$ (which is not queried) with $1$, and all other missing entries with $0$. We claim that this is a "No" input, and so we reach a contradiction. Indeed, by construction, no row is all-$1$. If column $j''$ is all-$1$ then $\inf(Y,v)_{i,j''} = 0$, which contradicts the assumption $i \notin R(Y,v)$.

Case 2: $(i,j) \in S_X$ and $(i,j) \notin S_Y$. Consider the path emanating from $v$ in which we answer all queries on row $i$ by $1$ and all other queries by $0$. This path is consistent with the input obtained from $\par(Y,v)$ by filling all missing entries on row $i$ with $1$ and all other missing entries with $0$, which is a "Yes" input.

The path is also consistent with the input obtained from $\par(Y,v)$ by filling all missing entries on row $i$ other than $(i,j)$ (which is not queried) with $1$, and all other missing entries with $0$. As in Case 1, this is a "No" input, and so we reach a contradiction.

Case 3: $(i,j) \in S_X$ and $(i,j) \in S_Y$. Consider the path emanating from $v$ in which we answer all queries on row $i$ by $1$ and all other queries by $0$. This path is consistent with the input obtained from $\par(Y,v)$ by filling all missing entries on row $i$ with $1$ and all other missing entries with $0$, which is a "Yes" input.

The path is also consistent with the input obtained from $\inf(X,v)$ by filling all missing entries on row $i$ with $1$, and all other missing entries with $0$. Since $\par(X,v)_{i,j} = 0$, row $i$ is not all-$1$. Clearly other rows are also not all-$1$. We claim that no column is all-$1$. This is because no column in $\inf(X,v)$ can be missing exactly one entry. Hence this is a "No" input, and we reach a contradiction. $\square$


For a permutation $\pi \in S_n$, let $X(\pi)$ be the input given as follows: entries $(1,\pi(1)),\dots,(n,\pi(n))$ are $0$, and all other entries are $1$. When we execute the branching program on $X(\pi)$, the partial input $\inf(X,v)$ is always a subset of $X(\pi)$, and so $C(X(\pi),v) = \pi(R(X(\pi),v))$, and in particular $|R(X(\pi),v)| = |C(X(\pi),v)|$. Furthermore, each query uncovers at most two $0$-entries in the inferred partial input. Therefore for every odd $s \leq n$, some node $v$ on the execution path of $X$ has $|R(X(\pi))| \in \{s-1,s\}$. Let $v_s(\pi)$ be the first such node.

The Claim proven above shows that if $v_s(\alpha) = v_s(\beta)$ then $R(X(\alpha), v_s(\alpha)) = R(X(\beta),v_s(\beta))$ and $C(X(\alpha),v_s(\alpha)) = C(X(\beta),v_s(\beta))$. Denote by $R,C$ the common values. Thus $t := |R| = |C| \in \{s-1,s\}$, and furthermore $C = \alpha(R)$. Hence the number of permutations $\beta$ such that $v_s(\alpha) = v_s(\beta)$ (including $\alpha$ itself) is at most $t! (n-t)!$. It follows that the number of vertices of the form $v_s(\alpha)$ is at least $$ \frac{n!}{\max\{(s-1)! (n-s+1)!, s! (n-s)!\}} = \min \left\{ \binom{n}{s-1}, \binom{n}{s} \right\}. $$

The Claim also shows that vertices of the form $v_s(\alpha)$ are different for different values of $s$, and so we deduce that the total number of vertices is at least $$ \sum_{r=0}^{\lfloor (n-1)/2 \rfloor} \min \left\{ \binom{n}{2r}, \binom{n}{2r+1} \right\} = \Omega(2^n). $$ Explicitly, the sum on the left equals $$ 2^{n-1} - \begin{cases} \binom{n-1}{n/2} & \text{if $n$ is even}, \\ \binom{n-1}{(n+1)/2} & \text{if $n \equiv 1 \pmod{4}$}, \\ \binom{n-1}{(n-1)/2} & \text{if $n \equiv 3 \pmod{4}$}, \end{cases} $$ showing that it is indeed $\Omega(2^n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.