Сложность OR-схемы плотного линейного оператора

Рассмотрим следующую простую модель монотонной схемы: каждый элемент - это просто двоичное ИЛИ. Какова сложность функции где - булева матрица с 0? Может ли он быть рассчитан по линейным размерам OR-цепей?$f(x)=Ax$$A$$n \times n$$O(n)$

Более формально, является функцией от до n битов. Я -ый выход ф вне \ bigvee_ {j = 1} ^ {N} (A_ {IJ} \ земельного x_j) (то есть, ИЛИ подмножеств входных бит , заданных я -й строкой А ).$f$$n$$n$$i$$f$$\bigvee_{j=1}^{n}(A_{ij} \land x_j)$$i$$A$

Обратите внимание, что 0 разбивает строки на диапазоны (подмножества, состоящие из последовательных элементов ). Это позволяет использовать известные структуры данных запроса диапазона. Например, структура данных разреженной таблицы может быть преобразована в схему OR размера . Алгоритм Яо для запросов операторов полугруппы диапазонов можно превратить в почти линейную схему (размером где - обратный Аккерманн)$O(n)$$A$$O(n)$$[n]$$O(n\log n)$$O(\alpha(n) \cdot n)$$\alpha(n)$

В частности, я даже не знаю, как построить схему линейного размера для особого случая, когда каждая строка содержит ровно два нуля. Хотя в случае ровно одного нуля в каждом ряду все просто. (Каждая функция вывода может быть вычислена с помощью ИЛИ префикса и суффикса , который может быть предварительно вычислен с помощью ИЛИ-вентилей.)A [ 1 .. k - 1 ] $A$$[1..k-1]$ k + 1 .. n ] 2 $[k+1..n]$$2n$

Это частичный (утвердительный) ответ в случае, когда у нас есть верхняя граница числа нулей в каждой строке или в каждом столбце.

Прямоугольник является булевой матрицей , состоящей из одного все-1 подматрицы и имеющие нули в других местах. OR-ранг r k ( A ) булевой матрицы - это наименьшее число r прямоугольников, так что A можно записать как (компонентно) OR этих прямоугольников. Таким образом, каждая 1-запись A является 1-позицией по меньшей мере в одном из прямоугольников, и каждая 0-запись A является 0-позицией во всех прямоугольниках. Обратите внимание, что log r k ( A ) является именно недетерминированной коммуникационной сложностью матрицы $rk(A)$$r$$A$$A$$A$$\log rk(A)$$A$(где Алиса получает строки и столбцы Боба). Как писал OP, каждая булева матрица m × n A = ( a i , j ) определяет отображение y = A x , где y i = ⋁ n j = 1 a i , j x j для i = 1 , … , m . То есть мы берем матрично-векторное произведение над логическим полукольцом. $m\times n$$A=(a_{i,j})$$y=Ax$$y_i=\bigvee_{j=1}^na_{i,j}x_j$$i=1,\ldots,m$

Следующая лемма принадлежит Пудлаку и Редлу; см. предложение 10.1 в этой статье или лемму 2.5 в этой книге для прямого построения.

Лемма 1: Для каждой булевой матрицы A n × n отображение y = A x может быть вычислено неограниченной веерной OR-схемой глубины-3 с использованием не более O ( r k ( A ) ⋅ n / log n ) проводов. $n\times n$$A$$y=Ax$$O(rk(A)\cdot n/\log n)$

У нас также есть следующая верхняя оценка OR-ранга плотных матриц. Аргумент - это простая вариация того, что использовал Алон в этой статье .

Лемма 2. Если каждый столбец или каждая строка булевой матрицы A содержит не более d нулей, то r k ( A ) = O ( d ln | A | ) , где | A | это число 1 с в A . $A$$d$$rk(A)=O(d\ln|A|)$$|A|$$1$$A$

Доказательство: Постройте случайную все- 1 подматрицу R , выбирая каждую строку независимо с одинаковой вероятностью p = 1 / ( d + 1 ) . Позвольте мне быть полученным случайным подмножеством строк. Тогда пусть R = I × J , где J представляет собой множество всех столбцов A , которые не имеют нулей в строках в I . $1$$R$$p=1/(d+1)$$I$$R=I\times J$$J$$A$$I$

1 -Посещение ( я , J ) из А покрывается R , если я не был выбран в I , и ни один из (не более г ) строк с 0 в J -й столбец был выбран в I . Следовательно, запись ( i , j ) покрыта с вероятностью не менее p ( 1 - p ) d ≥ p e - p d - p 2 d$1$$(i,j)$$A$$R$$i$$I$$d$$0$$j$$I$$(i,j)$п / э . Если мы применяем эту процедуру r раз для получения r прямоугольников, то вероятность того, что ( i , j ) не покрыт ни одним из этих прямоугольников, не превышает ( 1 - p / e ) r ≤ e - r p / e . В силу границы объединения вероятность того, что некоторый 1- вход A останется непокрытой, не превосходит | 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}$, который меньше 1 при r = O ( d ln | A | ) . $1$$r=O(d\ln|A|)$$\Box$

Следствие: если каждый столбец или каждая строка булевой матрицы A содержит не более d нулей, то отображение y = A x может быть вычислено неограниченной веерной OR-схемой глубины-3 с использованием O ( d n ) проводов. $A$$d$$y=Ax$$O(dn)$

Я предполагаю, что аналогичная верхняя граница, как в лемме 2, должна также выполняться, когда d является средним числом 1 с в столбце (или в строке). Было бы интересно показать это.$d$$1$

Замечание: (добавлено 04.01.2018) Аналог r k ( A ) = O ( d 2 log n ) леммы 2 также имеет место, когда d - максимальное среднее число нулей в подматрице A , где среднее число нулей в давал R × сек матрицей является общим числом нулей , разделенных на s + г . Это следует из теоремы 2 Н. Итона и В. Рёдля; «Графики малой размерности», Combinatorica 16 (1) (1996) 59-85 . Немного хуже верхняя граница$rk(A)=O(d^2\log n)$$d$$A$$r\times s$$s+r$r k ( A ) = O ( d 2 ln 2 n ) можно вывести непосредственно из леммы 2 следующим образом.$rk(A)=O(d^2\ln^2 n)$

Лемма 3: Пусть d ≥ 1 . Если каждый охватывающий подграф двудольного графа G имеет среднюю степень ≤ d , то G можно записать в виде объединения G = G 1 ∪ G 2 , где максимальная левая степень G 1 и максимальная правая степень G 2 составляют ≤ d , $d\geq 1$$G$$\leq d$$G$$G=G_1\cup G_2$$G_1$$G_2$$\leq d$

Доказательство: Индукция по числу n вершин. Базовые случаи n = 1 и n = 2 очевидны. Для шага индукции мы закрасим края синим и красным, чтобы максимальный градус как в синем, так и в красном подграфах был ≤ d . Возьмем вершину u степени ≤ d ; такая вершина должна существовать, потому что средняя степень всего графа должна быть ≤ d . Если u принадлежит левой части, то все ребра, наложенные на вас, закрашиваем синим, а все эти ребра - красным. Если мы удалим вершину $n$$n=1$$n=2$$\leq d$$u$$\leq d$$\leq d$$u$$u$$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.