fixed a typo
Source Link

Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it be computed by linear size OR-circuits?

More formally, $f$ is a function from $n$ to $n$ bits. The $i$-th output of $f$ is $\bigvee_{i=1}^{n}(A_{ij} \land x_j)$$\bigvee_{j=1}^{n}(A_{ij} \land x_j)$ (i.e., an OR of the subset of input bits given by the $i$-th row of $A$).

Note that $O(n)$ 0's split the rows of $A$ into $O(n)$ ranges (subsets consisting of consecutive elements of $[n]$). This makes it possible to employ known range query data structures. E.g., a sparse table data structure can be turned into an OR-circuit of size $O(n\log n)$. Yao's algorithm for range semigroup operator queries can be turned into an almost linear circuit (of size $O(\alpha(n) \cdot n)$ where $\alpha(n)$ is inverse Ackermann)

In particular, I don't even know how to construct a linear size circuit for a special case where each row of $A$ contains exactly two zeros. While the case of exactly one zero in each row is easy. (Each output function can be computed by an OR of a prefix $[1..k-1]$ and a suffix $[k+1..n]$, which can be precomputed by $2n$ OR-gates.)

Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it be computed by linear size OR-circuits?

More formally, $f$ is a function from $n$ to $n$ bits. The $i$-th output of $f$ is $\bigvee_{i=1}^{n}(A_{ij} \land x_j)$ (i.e., an OR of the subset of input bits given by the $i$-th row of $A$).

Note that $O(n)$ 0's split the rows of $A$ into $O(n)$ ranges (subsets consisting of consecutive elements of $[n]$). This makes it possible to employ known range query data structures. E.g., a sparse table data structure can be turned into an OR-circuit of size $O(n\log n)$. Yao's algorithm for range semigroup operator queries can be turned into an almost linear circuit (of size $O(\alpha(n) \cdot n)$ where $\alpha(n)$ is inverse Ackermann)

In particular, I don't even know how to construct a linear size circuit for a special case where each row of $A$ contains exactly two zeros. While the case of exactly one zero in each row is easy. (Each output function can be computed by an OR of a prefix $[1..k-1]$ and a suffix $[k+1..n]$, which can be precomputed by $2n$ OR-gates.)

Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it be computed by linear size OR-circuits?

More formally, $f$ is a function from $n$ to $n$ bits. The $i$-th output of $f$ is $\bigvee_{j=1}^{n}(A_{ij} \land x_j)$ (i.e., an OR of the subset of input bits given by the $i$-th row of $A$).

Note that $O(n)$ 0's split the rows of $A$ into $O(n)$ ranges (subsets consisting of consecutive elements of $[n]$). This makes it possible to employ known range query data structures. E.g., a sparse table data structure can be turned into an OR-circuit of size $O(n\log n)$. Yao's algorithm for range semigroup operator queries can be turned into an almost linear circuit (of size $O(\alpha(n) \cdot n)$ where $\alpha(n)$ is inverse Ackermann)

In particular, I don't even know how to construct a linear size circuit for a special case where each row of $A$ contains exactly two zeros. While the case of exactly one zero in each row is easy. (Each output function can be computed by an OR of a prefix $[1..k-1]$ and a suffix $[k+1..n]$, which can be precomputed by $2n$ OR-gates.)

Tweeted twitter.com/StackCSTheory/status/947080743326494720
Source Link

OR-circuit complexity of a dense linear operator

Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it be computed by linear size OR-circuits?

More formally, $f$ is a function from $n$ to $n$ bits. The $i$-th output of $f$ is $\bigvee_{i=1}^{n}(A_{ij} \land x_j)$ (i.e., an OR of the subset of input bits given by the $i$-th row of $A$).

Note that $O(n)$ 0's split the rows of $A$ into $O(n)$ ranges (subsets consisting of consecutive elements of $[n]$). This makes it possible to employ known range query data structures. E.g., a sparse table data structure can be turned into an OR-circuit of size $O(n\log n)$. Yao's algorithm for range semigroup operator queries can be turned into an almost linear circuit (of size $O(\alpha(n) \cdot n)$ where $\alpha(n)$ is inverse Ackermann)

In particular, I don't even know how to construct a linear size circuit for a special case where each row of $A$ contains exactly two zeros. While the case of exactly one zero in each row is easy. (Each output function can be computed by an OR of a prefix $[1..k-1]$ and a suffix $[k+1..n]$, which can be precomputed by $2n$ OR-gates.)