patternMinor
Read-once complexity of a matrix problem
Viewed 0 times
onceproblemreadmatrixcomplexity
Problem
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:
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.)
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.)
Solution
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 m
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 m
Context
StackExchange Computer Science Q#163458, answer score: 5
Revisions (0)
No revisions yet.