Complexidade do circuito OR de um operador linear denso

14

Considere o seguinte modelo de circuito simples monótono: cada porta é apenas um OR binário. Qual é a complexidade de uma função f ( x ) = A x emf(x)=Ax que AA é uma matriz booleana n × nn×n com O ( n )O(n) 0's? Pode ser calculado por circuitos OR de tamanho linear?

Mais formalmente, ff é uma função de nn para nn bits. A ii -ésima saída de ff é n j = 1 ( A i j x j )nj=1(Aijxj)(isto é, um OR do subconjunto de bits de entrada dadas pelaiilinha de -ésimoUmA).

Observe que O ( n )O(n) 0's dividem as linhas de AA em intervalos de O ( n )O(n) (subconjuntos que consistem em elementos consecutivos de [ n ][n] ). Isso torna possível empregar estruturas de dados de consulta de intervalo conhecidas. Por exemplo, uma estrutura de dados de tabela esparsa pode ser transformada em um circuito OR do tamanho O ( n log n )O(nlogn) . O algoritmo de Yao para consultas de operadores de semigrupos de alcance pode ser transformado em um circuito quase linear (do tamanho O ( α ( n ) n )O(α(n)n) ondeα ( n )α(n) é inverso de Ackermann)

Em particular, nem sei como construir um circuito de tamanho linear para um caso especial em que cada linha de AA contém exatamente dois zeros. Embora o caso de exatamente um zero em cada linha seja fácil. (Cada função de saída pode ser calculada por um OR de um prefixo [ 1 .. k - 1 ][1..k1] e um sufixo [ k + 1 .. n ][k+1..n] , que pode ser pré-computado por 2 n2n OR-gates.)

Alexander S. Kulikov
fonte
3
Um limite superior é conhecido: é no máximo rk (A) vezes n dividido pelo log n, em que rk (A) é o ranking OR de uma matriz booleana A (= número mínimo de sub-trechos 1 cujo OR coincide com A ) Veja o Lema 2.5 neste livro . Então, qual o tamanho (no máximo) da classificação booleana de uma matriz nxn com O (n) zeros pode ser?
Stasys
@Stasys Obrigado, Stasys! Já para a matriz com diagonal zero, o OR-rank é linear, certo?
Alexander S. Kulikov
2
A classificação OR da sua matriz (diagonal zero e 1s em outro lugar) é no máximo 2 \ log n: rotule linhas / colunas por cadeias binárias de comprimento \ log n e considere retângulos {(r, c): r (i) = a, c (i) = 1-a} para a = 0,1. Observe também que o lema 2.5 é um limite superior . Um limite inferior em termos de classificação OR é dado em Thm. 3.20 Além disso, o log da classificação OR é exatamente a complexidade da comunicação não determinística das matrizes.
Stasys
@Stasys oh, sim, certo!
Alexander S. Kulikov

Respostas:

7

Esta é uma resposta parcial (afirmativa) no caso em que temos um limite superior no número de zeros em todas as linhas ou colunas.

Um retângulo é uma matriz booleana que consiste em uma submatriz all-1 e possui zeros em outro lugar. Um OR-rank r k ( A ) de uma matriz booleana é o menor número r de retângulos, de modo que A possa ser escrito como um OR (componente a componente) desses retângulos. Ou seja, cada entrada de A é uma entrada em pelo menos um dos retângulos e cada entrada de A é entrada de 0 em todos os retângulos. Observe que log r k ( A ) é exatamente a complexidade de comunicação não determinística da matriz Ark(A)rAAAlogrk(A)A (onde Alice obtém linhas e colunas Bob). Como OP escreveu, toda matriz × n m × n A = (m×n b a i , j ) define um mapeamento y = A x , onde y i = n j = 1 a i , j x j para i = 1 , , m . Ou seja, tomamos um produto de vetor de matriz sobre o semiamento booleano. A=(ai,j)y=Axyi=nj=1ai,jxji=1,,m

O seguinte lema é devido a Pudlák e Rödl; veja a Proposição 10.1 neste artigo ou o Lema 2.5 deste livro para uma construção direta.

Lema 1: Para cada matriz booleana n × n A , o mapeamento y = A x pode ser calculado por um circuito OR de profundidade ilimitada de ventilador 3, usando no máximo fios O ( r k ( A ) n / log n ) . n×nAy=AxO(rk(A)n/logn)

Também temos o seguinte limite superior no ranking OR de matrizes densas. O argumento é uma variação simples da usada por Alon neste artigo .

Lema 2: Se todas as colunas ou linhas de uma matriz booleana A contiver no máximo d zeros, então r k ( A ) = O ( d ln | A | ) , em que | Um | é o número de 1 s emAdrk(A)=O(dln|A|)|A|1 um . A

Prova: Construa uma submatriz aleatória all- 1 R escolhendo cada linha independentemente com a mesma probabilidade p = 1 / ( d + 1 ) . Seja eu o subconjunto aleatório obtido de linhas. Então deixe- R = I × J , onde J é o conjunto de todas as colunas de A que não têm zeros nas linhas em que eu . 1Rp=1/(d+1)IR=I×JJAI

A 11-entry (i,j)(i,j) of AA is covered by RR if ii was chosen in II and none of (at most dd) rows with a 00 in the jj-th column was chosen in II. Hence, the entry (i,j)(i,j) is covered with probability at least p(1p)dpepdp2dp/ep(1p)dpepdp2dp/e. If we apply this procedure rr times to get rr rectangles, then the probability that (i,j)(i,j) is covered by none of these rectangles does not exceed (1p/e)rerp/e(1p/e)rerp/e. By the union bound, the probability that some 11-entry of AA remains uncovered is at most |A|erp/e|A|erp/e, which is smaller than 11 for r=O(dln|A|)r=O(dln|A|).

Corollary: If every column or every row of a boolean matrix AA contains at most dd zeros, then the mapping y=Axy=Ax can be computed by an unbounded fanin OR-circuit of depth-3 using O(dn)O(dn) wires.

I guess that a similar upper bound as in Lemma 2 should also hold when dd is the average number of 11s in a column (or in a row). It would be interesting to show this.


Remark: (added 04.01.2018) An analogue rk(A)=O(d2logn)rk(A)=O(d2logn) of Lemma 2 also holds when dd is the maximum average number of zeros in a submatrix of AA, where the average number of zeros in an r×sr×s matrix is the total number of zeros divided by s+rs+r. This follows from Theorem 2 in N. Eaton and V. Rödl;, Graphs of small dimension, Combinatorica 16(1) (1996) 59-85. A slightly worse upper bound rk(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 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.

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

Proof: Consider the bipartite n×n graph G with (i,j) being an edge iff ai,j=0. Then the maximum average degree of G is at most d. By Lemma 3, we can write G=G1G2, where the maximum degree of the vertices on the left part of G1, and the maximum degree of the vertices on the right part of G2 is d. Let A1 and A2 be the complements of the adjacency matrices of G1 and G2. Hence, A=A1A2 is a componentwise AND of these matrices. The maximum number of zeros in every row of A1 and in every column of A2 is at most d. Since rk(A)rk(A1)rk(A2), Lemma 2 yields 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) 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=n, and put an identity m×m matrix in, say left upper corner of A, and fill the remaining entries by ones. Then d(A)m2/2n<1 but rk(A)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.

Stasys
fonte
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]; 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×(LR)) 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)an+C(n/2) implying C(n)=O(n).

Now, generalize it to the case of at most d zeros in every row. Let Cd(n) be the complexity of an n×(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(12d) 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×L, T×R, and 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
fonte
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