Suppose we have a matrix $$T\in\Bbb K^{n^k\times m}$$ and a target vector $v\in\Bbb F_q^m$ where $m<n^k$ and $1<k$ holds.

We need to find $k$ vectors $u_1,\dots,u_k\in\Bbb K^n$ such that $$v=uT$$ holds where $u=(u_1\otimes\dots\otimes u_k)$ is true.

Is there an $O((n^k\log B)^c)$ algorithm for this where $$\Bbb K=\Bbb F_q\implies B=q\mbox{ and }\Bbb K=\Bbb Z\implies B=\max(\max|T_{ij}|,\max|v_j|)?$$

The algorithm should output the vectors if they exist or $0$ otherwise.


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.