1
$\begingroup$

I am trying to understand which operations are computable by an $\texttt{NC}^1$ circuit. However, I am struggling to understand whether there is such a circuit for multiplying a matrix with a vector or if the circuit will necessarily be in $\texttt{NC}^2$.

$\endgroup$
1
  • $\begingroup$ Doesn't it have an arithmetic circuit of constant depth? That would imply it's in $\texttt{NC}^1$, I believe. $\endgroup$ Jul 1, 2023 at 3:38

1 Answer 1

0
$\begingroup$

Say you have $A\in \mathbb{F}_p^{m\times n}$, and $s\in\mathbb{F}_p^n$. We want to compute $As\in\mathbb{F}_p^m$. Note that

  1. We can split this into $m$ computations of $\langle A_i, s\rangle$, where $A_i$ are the rows of $A$, i.e. it is $m$ $n$-dimensional inner products
  2. Each inner product can be computed in $\log_2(n)$ depth using $O(n)$ processors, essentially via putting each summand in $\langle A_i, s\rangle = \sum_{j = 1}^n A_{ij}s_j$ on the leaf of a full binary tree, and having each internal node sum the results of its two children. The root will then contain $\langle A_i, s\rangle$.

In total, with $O(mn)$ processors, we should be able to determine it in depth $O(\log n)$, provided the underlying arithmetic in $\mathbb{F}_p$ can be done in constant depth, which seems like a reasonable assumption. This would put it in $\mathsf{NC}^1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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