Komplexität der ODER-Schaltung eines dichten linearen Operators

14

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 ) = A x f(x)=AxA An × n n×nO ( n )O(n)

Genauer gesagt ist ff eine Funktion von nn bis nn Bits. Die i-i te Ausgabe von ist (dh ein ODER der durch die te Reihe von gegebenen Teilmenge von Eingabebits ).f fn j = 1 ( A i jx j ) nj=1(Aijxj)i iAA

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 ) O(n)A AO ( n ) O(n)[ n ] [n]O ( n log n )O(nlogn)O ( α ( n ) n ) O(α(n)n)α ( n )α(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 AA 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 ][1..k1] und eines Suffixes [ k + 1 .. n ][k+1..n] berechnet werden, das durch 2 n2n ODER-Gatter vorberechnet werden kann .)

Alexander S. Kulikov
quelle
3
Eine Obergrenze ist bekannt: Sie ist höchstens rk (A) mal n geteilt durch log n, wobei rk (A) der OR-Rang einer Booleschen Matrix A ist (= minimale Anzahl aller 1-Submatrizen, deren OR mit A übereinstimmt ). Siehe Lemma 2.5 in diesem Buch . Wie groß kann also (höchstens) der Boolesche Rang einer nxn-Matrix mit 0 (n) Nullen sein?
Stasys
@Stasys Danke, Stasys! Schon für die Matrix mit der Diagonale Null ist der OR-Rang linear, oder?
Alexander S. Kulikov
2
Der OR-Rang Ihrer Matrix (Null-Diagonale und 1s an anderer Stelle) ist höchstens 2 \ log n: Beschriften Sie Zeilen / Spalten mit binären Zeichenfolgen der Länge \ log n und berücksichtigen Sie Rechtecke {(r, c): r (i) = a, c (i) = 1-a} für a = 0,1. Beachten Sie auch, dass Lemma 2.5 eine Obergrenze ist . Eine Untergrenze in Bezug auf den OR-Rang wird in Thm angegeben. 3,20. Außerdem ist log of OR rank genau die nicht deterministische Kommunikationskomplexität von Matrizen.
Stasys
@Stasys oh ja, richtig!
Alexander S. Kulikov

Antworten:

7

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 A istrk(A)rAAAlogrk(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×nA=(ai,j)y=Axyi=nj=1ai,jxji=1,,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×nAy=AxO(rk(A)n/logn)

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 . Adrk(A)=O(dln|A|)|A|1A

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 . 1Rp=1/(d+1)IR=I×JJAI

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 ) dp e - p d - p 2 d1(i,j)ARiId0jI(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 ) re - r p / e . Nach der Vereinigungsgrenzebeträgtdie Wahrscheinlichkeit, dass ein 1 -Eintrag von A aufgedeckt bleibt, höchstens | A | e - r p / ep(1p)dpepdp2dp/err(i,j)(1p/e)rerp/e1A|A|erp/e, der für r = O kleiner als 1 ist ( d ln | A | ) . 1r=O(dln|A|)

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 . Ady=AxO(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.d1


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 Obergrenzerk(A)=O(d2logn)dAr×ss+rrk(A)=O(d2ln2n)rk(A)=O(d2ln2n) can be derived directly from Lemma 2 as follows.

Lemma 3: Let d1d1. If every spanning subgraph of a bipartite graph GG has average degree dd, then GG can be written as a union G=G1G2G=G1G2, where the maximum left degree of G1G1 and the maximum right degree of G2G2 are dd.

Proof: Induction on the number nn of vertices. The base cases n=1n=1 and n=2n=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 dd. Take a vertex uu of degree dd; such a vertex must exists because also the average degree of the entire graph must be dd. If uu belongs to the left part, then color all edges incident to uu in blue, else color all these edges in red. If we remove the vertex uu then the average degree of the resulting graph GG is also at most dd, and we can color the edges of this graph by the induction hypothesis.

Lemma 4: Let d1d1. If the maximum average number of zeros in a boolean n×nn×n matrix A=(ai,j)A=(ai,j) is at most dd, then rk(A)=O(d2ln2n)rk(A)=O(d2ln2n).

Proof: Consider the bipartite n×nn×n graph GG with (i,j)(i,j) being an edge iff ai,j=0ai,j=0. Then the maximum average degree of GG is at most dd. By Lemma 3, we can write G=G1G2G=G1G2, where the maximum degree of the vertices on the left part of G1G1, and the maximum degree of the vertices on the right part of G2G2 is dd. Let A1A1 and A2A2 be the complements of the adjacency matrices of G1G1 and G2G2. Hence, A=A1A2A=A1A2 is a componentwise AND of these matrices. The maximum number of zeros in every row of A1A1 and in every column of A2A2 is at most dd. Since rk(A)rk(A1)rk(A2)rk(A)rk(A1)rk(A2), Lemma 2 yields rk(A)=O(d2ln2n)rk(A)=O(d2ln2n).

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)d=d(A) to be the average number of zeros in the entire matrix AA (not the maximum of averages over all submatrices), then Lemma 2 can badly fail. Let m=nm=n, and put an identity m×mm×m matrix in, say left upper corner of AA, and fill the remaining entries by ones. Then d(A)m2/2n<1d(A)m2/2n<1 but rk(A)mrk(A)m, which is exponentially larger than ln|A|ln|A|. Note, however, that the OR complexity of this matrix is very small, is O(n)O(n). So, direct arguments (not via rank) can yield much better upper bounds on the OR complexity of dense matrices.

Stasys
quelle
Thanks a lot, Stasys! This is nice! In the meantime, Ivan Mihajlin came with another proof. I've posted it below.
Alexander S. Kulikov
2

(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][n]; two nodes ii and jj are joined by an edge, if there is a row having zeros in columns ii and jj. The graph has nn edges and hence it contains a cut (L,R)(L,R) of size at least n/2n/2. This cut splits the columns of the matrix into two parts (LL and RR). Let now also split the rows into two parts: the top part TT contains all columns that have exactly one zero in both LL and RR; the bottom part BB contains all the remaining rows. What is nice about the top part of the matrix (T×(LR)T×(LR)) is that it can be computed by O(n)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)an+C(n/2)C(n)an+C(n/2) implying C(n)=O(n)C(n)=O(n).

Now, generalize it to the case of at most dd zeros in every row. Let Cd(n)Cd(n) be the complexity of an n×(dn)n×(dn) matrix with at most dd zeros per row (if there are more than dndn columns, then some of them are all-1). Partition the columns into two parts LL and RR such that at least n(12d)n(12d) rows (call them TT) satisfy the following property: if there are exactly dd zeroes in a row, then not all of them belong to the same part (denote the remaining rows by BB). Then make three recursive calls: T×LT×L, T×RT×R, and B×(LR)B×(LR). This gives a recurrence relation Cd(n)an+2Cd1(n(12d))+Cd(2dn). This, in turn, implies that Cd(n)f(d)n. The function f(d) is exponential, but still.

Alexander S. Kulikov
quelle
A nice argument. But it seems to be tailor made for the case of d=2 zeros per row. What about d>2 zeros?
Stasys
@Stasys, it is doable if I'm not mistaken. I've updated the answer.
Alexander S. Kulikov