Семинар лаборатории теоретической информатики: "Complexity of dense linear operators". Докладчик: В. Подольский

Abstract

Suppose we have a vector x of n Boolean variables and we want to compute a Boolean operator Ax with Boolean square matrix A. That is, for all rows of A we would like to compute an OR of variables of x that has ones in the corresponding coordinate of the row. We start with variables and in one step we are allowed to apply OR operation to two expressions computed on previous steps (we build a circuit consisting of OR gates).
If A is a sparse matrix (has O(n) ones), this can easily be done in O(n) operations. We show that the same is true for very dense matrices (O(n) zeros).
This result translates to computation of operators over arbitrary commutative semiring. We also show that that the same cannot be done for semirings with large enough amount of non-commutativity.