Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry

One is allowed to pre-process this matrix as appropriate.

Given another positive integer entried $B$ of size $n\times b$ with $\ell'$ bits per entry, what is the complexity of multiplication $AB$?

Note we already have $(\max(a,n,b))^{2+\theta}polylog(\ell\ell')$ time and space algorithms where $2+\theta=\omega$ and $\omega$ is exponent of matrix multiplication.

  1. The query here is whether we can do take $\theta=0$ or at least have flexibility to take any $\theta>0$ by anything cleverer?

  2. Can we attain $\theta=0$ or at least have flexibility to take any $\theta>0$ with number of operations independent of $\ell$ and $\ell'$ in the $RAM$ model?


Your Answer

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

Browse other questions tagged or ask your own question.