7
$\begingroup$

It is known that most computational problems related to linear algebra can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals or a finite field, we can compute the rank of $A$, $\det(A)$ or $A^{-1}$, etc. in parallel time $O(\log^2(n))$.

The complexity of these linear-algebra problems remains the same (i.e. in $NC^2$) even if the rank of $A$ is say $n^{\epsilon}$ for some small constant $\epsilon>0$ (just by padding zeros) but what happens to the complexity of these problems when $A$ has very small rank, i.e. $r = rank(A) \leq \log(n)$?

Clearly, if $A$ is ${\it given}$ to us as a full-rank matrix of dimension $n \times r$ then the complexity drops: Consider for example the problem of determining whether $A x = b$ for inputs $A,b$ over $\mathbf{F}_2$ for some vector $x$.

One can simply enumerate over all possible column subsets of $A$, and compute $x$ in constant parallel time ($ACC^0[2]$). However, the problem is that we do not posses such a succinct description from the input. Naively, trying to brute-force enumerate over all possible column combinations of size $\log(n)$ results in time ${n\choose \log(n)}$ which is quasi-polynomial.

$\endgroup$
  • $\begingroup$ I don't understand your question. What is your input and how do you compute $x$ in constant parallel time? What is succinct about the description? $\endgroup$ – Nikhil May 11 '17 at 8:41
  • 1
    $\begingroup$ In the example above, the input is an $n\times n$ matrix $A$, and a length $n$ vector $b$. To determine whether there is such $x$ you compute in parallel all partial sums of columns of $A$, and for each one - you check if it is equal to b. Using unbounded fan-in parity gates each summation can be carried out in constant depth. $\endgroup$ – Lior Eldar May 11 '17 at 12:48
4
$\begingroup$

I think the following procedure computes a basis of the column span of an $n \times n$-matrix of rank at most $\log n$ in $\mathrm{AC}_1$.

If you have a matrix of size $n \times 2 \log n$, you can find a basis of its column span in $\mathrm{AC}_0$ by running over all subsets in parallel and checking in parallel whether a nontrivial linear combination vanishes (say over $\mathbb{F}_2$). From all sets of maximal rank you select the lexicographically smallest.

Now given an $n \times n$-matrix of rank at most $\log n$, we can find a basis of its column span in $\mathrm{AC}_1$ as follows: Divide the columns into two halfves, compute a basis recursively. From these two bases we can compute a common basis using the algorithm from above.

$\endgroup$
  • $\begingroup$ Great! Though I guess that finding the lexicographically first element is already in ACC1[2] and not ACC0[2], right? – Lior Eldar 1 hour ago $\endgroup$ – Lior Eldar May 11 '17 at 15:49
  • $\begingroup$ I don't think so. To check whether you are the first basis, you just have to check whether there is no basis to the left of you. This is just an OR. $\endgroup$ – Markus Bläser May 15 '17 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.