Komplexität der ODER-Schaltung eines dichten linearen Operators

Betrachten Sie das folgende einfache monotone Schaltungsmodell: Jedes Gatter ist nur ein binäres ODER. Was ist die Komplexität einer Funktion wobei eine boolesche Matrix mit 0 ist? Kann es mit ODER-Schaltungen linearer Größe berechnet werden?$f(x)=Ax$$A$$n \times n$$O(n)$

Genauer gesagt ist $f$ eine Funktion von $n$ bis $n$ Bits. Die $i$ te Ausgabe von ist (dh ein ODER der durch die te Reihe von gegebenen Teilmenge von Eingabebits ).$f$$\bigvee_{j=1}^{n}(A_{ij} \land x_j)$$i$$A$

Beachten Sie, dass 0 die Zeilen von in Bereiche aufteilt (Teilmengen, die aus aufeinanderfolgenden Elementen von ). Dies ermöglicht es, bekannte Bereichsabfragedatenstrukturen zu verwenden. Beispielsweise kann eine Datenstruktur mit geringer Dichte in eine ODER-Schaltung der Größe . Yaos Algorithmus für Bereichs-Semigruppenoperator-Abfragen kann in eine nahezu lineare Schaltung (mit der Größe wobei invers ist, umgewandelt werden. Ackermann)$O(n)$$A$$O(n)$$[n]$$O(n\log n)$$O(\alpha(n) \cdot n)$$\alpha(n)$

Insbesondere weiß ich nicht einmal, wie man eine Schaltung mit linearer Größe für einen speziellen Fall konstruiert, bei dem jede Zeile von $A$ genau zwei Nullen enthält. Dabei ist der Fall von genau einer Null in jeder Zeile einfach. (Jede Ausgangsfunktion kann durch ein ODER eines Präfixes $[1..k-1]$ und eines Suffixes $[k+1..n]$ berechnet werden, das durch $2n$ ODER-Gatter vorberechnet werden kann .)

Dies ist eine teilweise (bejahende) Antwort in dem Fall, dass wir in jeder Zeile oder in jeder Spalte eine Obergrenze für die Anzahl der Nullen haben.

Ein Rechteck ist eine boolesche Matrix, die aus einer all-1-Submatrix besteht und an anderer Stelle Nullen aufweist. Ein OR-Rang r k ( A ) einer Booleschen Matrix ist die kleinste Anzahl r von Rechtecken, so dass A als (komponentenweises) OR dieser Rechtecke geschrieben werden kann. Das heißt, jeder 1-Eintrag von A ist ein 1-Eintrag in mindestens einem der Rechtecke, und jeder 0-Eintrag von A ist ein 0-Eintrag in allen Rechtecken. Beachten Sie, dass log r k ( A ) genau die nicht deterministische Kommunikationskomplexität der Matrix $rk(A)$$r$$A$$A$$A$$\log rk(A)$$A$(wo Alice Zeilen und Bob Spalten bekommt). Als OP geschrieben, jede Boolesche m × n Matrix A = ( a i , j ) definiert eine Abbildung Y = A x , wobei y i = ⋁ n j = 1 a i , j x j für i = 1 , ... , m . Das heißt, wir nehmen ein Matrix-Vektor-Produkt über das Boolesche Semiren. $m\times n$$A=(a_{i,j})$$y=Ax$$y_i=\bigvee_{j=1}^na_{i,j}x_j$$i=1,\ldots,m$

Das folgende Lemma stammt von Pudlák und Rödl; Siehe Proposition 10.1 in diesem Artikel oder Lemma 2.5 in diesem Buch für eine direkte Konstruktion.

Lemma 1: Für jede boolesche n × n- Matrix A kann die Abbildung y = A x durch eine unbegrenzte Fanin-ODER-Schaltung der Tiefe 3 unter Verwendung von höchstens O ( r k ( A ) ⋅ n / log n ) -Drähten berechnet werden . $n\times n$$A$$y=Ax$$O(rk(A)\cdot n/\log n)$

Wir haben auch die folgende Obergrenze für den OR-Rang von dichten Matrizen. Das Argument ist eine einfache Variation des von Alon in diesem Artikel verwendeten .

Lemma 2: Wenn jede Spalte oder jede Zeile einer Booleschen Matrix A höchstens d Nullen enthält, dann ist r k ( A ) = O ( d ln | A | ) , wobei | A | ist die Anzahl von 1 s in A . $A$$d$$rk(A)=O(d\ln|A|)$$|A|$$1$$A$

Beweis: Konstruieren Sie eine zufällige all- 1- Submatrix R, indem Sie jede Zeile einzeln mit der gleichen Wahrscheinlichkeit p = 1 / ( d + 1 ) auswählen . Sei ich die erhaltene zufällige Teilmenge von Zeilen. Dann sei R = I × J , wobei J die Menge aller Spalten von A ist , die keine Nullen in den Zeilen in I haben . $1$$R$$p=1/(d+1)$$I$$R=I\times J$$J$$A$$I$

Ein 1- Eintrag ( i , j ) von A wird von R abgedeckt, wenn i in I gewählt wurde und keine der (höchstens d ) Zeilen mit einer 0 in der j- ten Spalte in I gewählt wurde . Daher wird der Eintrag ( i , j ) wird mit einer Wahrscheinlichkeit von mindestens abgedeckt p ( 1 - p ) d ≥ p e - p d - p 2 d$1$$(i,j)$$A$$R$$i$$I$$d$$0$$j$$I$$(i,j)$p / e . Wenn wir diese Prozedur r- malanwenden, um r Rechtecke zu erhalten,überschreitetdie Wahrscheinlichkeit, dass ( i , j ) von keinem dieser Rechtecke abgedeckt wird, nicht ( 1 - p / e ) r ≤ e - r p / e . Nach der Vereinigungsgrenzebeträgtdie Wahrscheinlichkeit, dass ein 1 -Eintrag von A aufgedeckt bleibt, höchstens | A | ⋅ e - r p /$p(1-p)^{d}\geq pe^{-pd-p^2d}\geq p/e$$r$$r$$(i,j)$$(1-p/e)^r\leq e^{-rp/e}$$1$$A$$|A|\cdot e^{-rp/e}$, der für r = O kleiner als 1 ist ( d ln | A | ) . $1$$r=O(d\ln|A|)$$\Box$

Folgerung: Wenn jede Spalte oder jede Zeile einer Booleschen Matrix A höchstens d Nullen enthält, kann die Abbildung y = A x durch eine unbegrenzte Fan-in-ODER-Schaltung der Tiefe 3 unter Verwendung von O ( d n ) -Drähten berechnet werden . $A$$d$$y=Ax$$O(dn)$

Ich vermute, dass eine ähnliche obere Schranke wie in Lemma 2 auch gelten sollte, wenn d die durchschnittliche Anzahl von 1 s in einer Spalte (oder in einer Reihe) ist. Es wäre interessant, dies zu zeigen.$d$$1$

Bemerkung: (hinzugefügt am 04.01.2018) Ein Analogon r k ( A ) = O ( d 2 log n ) von Lemma 2 gilt auch, wenn d die maximale durchschnittliche Anzahl von Nullen in einer Untermatrix von A ist , wobei die durchschnittliche Anzahl von Nullen in Eine r × s- Matrix ist die Gesamtzahl der Nullen geteilt durch s + r . Dies folgt aus Satz 2 in N. Eaton und V. Rödl ;, Graphs of small dimension, Combinatorica 16 (1) (1996) 59-85 . Eine etwas schlechtere Obergrenze$rk(A)=O(d^2\log n)$$d$$A$$r\times s$$s+r$$rk(A)=O(d^2\ln^2 n)$ can be derived directly from Lemma 2 as follows.

Lemma 3: Let $d\geq 1$. If every spanning subgraph of a bipartite graph $G$ has average degree $\leq d$, then $G$ can be written as a union $G=G_1\cup G_2$, where the maximum left degree of $G_1$ and the maximum right degree of $G_2$ are $\leq d$.

Proof: Induction on the number $n$ of vertices. The base cases $n=1$ and $n=2$ are obvious. For the induction step, we will color the edges in blue and red so that the maximum degree in both blue and red subgraphs are $\leq d$. Take a vertex $u$ of degree $\leq d$; such a vertex must exists because also the average degree of the entire graph must be $\leq d$. If $u$ belongs to the left part, then color all edges incident to $u$ in blue, else color all these edges in red. If we remove the vertex $u$ then the average degree of the resulting graph $G$ is also at most $d$, and we can color the edges of this graph by the induction hypothesis. $\Box$

Lemma 4: Let $d\geq 1$. If the maximum average number of zeros in a boolean $n\times n$ matrix $A=(a_{i,j})$ is at most $d$, then $rk(A)=O(d^2\ln^2 n)$.

Proof: Consider the bipartite $n\times n$ graph $G$ with $(i,j)$ being an edge iff $a_{i,j}=0$. Then the maximum average degree of $G$ is at most $d$. By Lemma 3, we can write $G=G_1\cup G_2$, where the maximum degree of the vertices on the left part of $G_1$, and the maximum degree of the vertices on the right part of $G_2$ is $\leq d$. Let $A_1$ and $A_2$ be the complements of the adjacency matrices of $G_1$ and $G_2$. Hence, $A= A_1\land A_2$ is a componentwise AND of these matrices. The maximum number of zeros in every row of $A_1$ and in every column of $A_2$ is at most $d$. Since $rk(A)\leq rk(A_1)\cdot rk(A_2)$, Lemma 2 yields $rk(A)=O(d^2\ln^2 n)$. $\Box$

N.B. The following simple example (pointed by Igor Sergeev) shows that my "guess" at the end of the answer was totally wrong: if we take $d=d(A)$ to be the average number of zeros in the entire matrix $A$ (not the maximum of averages over all submatrices), then Lemma 2 can badly fail. Let $m=\sqrt{n}$, and put an identity $m\times m$ matrix in, say left upper corner of $A$, and fill the remaining entries by ones. Then $d(A)\leq m^2/2n < 1$ but $rk(A)\geq m$, which is exponentially larger than $\ln|A|$. Note, however, that the OR complexity of this matrix is very small, is $O(n)$. So, direct arguments (not via rank) can yield much better upper bounds on the OR complexity of dense matrices.

(I tried to post this as a comment to Stasys' answer above, but this text is too long for a comment, so posting it as an answer.) Ivan Mihajlin (@ivmihajlin) came up with the following construction. Similarly to Stasys' proof, it works for the case when the maximum (rather than average) number of 0’s in each row is bounded.

First, consider the case when every row contains exactly two zeros. Consider the following undirected graph: the set of vertices is $[n]$; two nodes $i$ and $j$ are joined by an edge, if there is a row having zeros in columns $i$ and $j$. The graph has $n$ edges and hence it contains a cut $(L,R)$ of size at least $n/2$. This cut splits the columns of the matrix into two parts ($L$ and $R$). Let now also split the rows into two parts: the top part $T$ contains all columns that have exactly one zero in both $L$ and $R$; the bottom part $B$ contains all the remaining rows. What is nice about the top part of the matrix ($T \times (L \cup R)$) is that it can be computed by $O(n)$ gates. For the bottom part, let’s cut all-1 columns out of it and make a recursive call. The corresponding recurrence relation is $C(n) \le an + C(n/2)$ implying $C(n)=O(n)$.

Now, generalize it to the case of at most $d$ zeros in every row. Let $C_d(n)$ be the complexity of an $n \times (\le dn)$ matrix with at most $d$ zeros per row (if there are more than $dn$ columns, then some of them are all-1). Partition the columns into two parts $L$ and $R$ such that at least $n(1-2^{-d})$ rows (call them $T$) satisfy the following property: if there are exactly $d$ zeroes in a row, then not all of them belong to the same part (denote the remaining rows by $B$). Then make three recursive calls: $T \times L$, $T \times R$, and $B \times (L \cup R)$. This gives a recurrence relation $C_d(n) \le an + 2\cdot C_{d-1}(n(1-2^{-d}))+C_d(2^{-d}n)$. This, in turn, implies that $C_d(n) \le f(d)\cdot n$. The function $f(d)$ is exponential, but still.