# What is the computational complexity of solving a highly underdetermined system?

Let $$F$$ be a finite field with $$q$$ elements. Consider an underdetermined system of linear equations with $$m$$ equations and $$n$$ variables where $$n\gg m$$. What is the complexity of solving such a highly underdetermined system?

Can someone point me in the right direction? Are there any research articles on this?

Thank you.

• Do you want the complexity of a practically feasible algorithm, or the best theoretical bound? That is, do you consider the matrix product to have complexity $O(n^3)$ or $O(n^{\omega})$ with $\omega \leq 2.37$? Mar 7, 2021 at 8:50
• @FedericoPoloni Thanks for the response. I want the complexity of a practically feasible algorithm. Mar 7, 2021 at 8:53
• I am not an expert, but this looks like a good starting point to check: hal.archives-ouvertes.fr/hal-00688254/document . Algorithm 4.2 should address that problem, if I read correctly. Mar 8, 2021 at 12:02
• @FedericoPoloni This is regarding the first comment. The formula $\mathcal{O}(n^3)$ gives the complexity for system of $m$ equations and $n$ variables?? Are you sure there is no involvement for $m$. Thanks for reading. Mar 9, 2021 at 6:08
• No, that was just an example of another algorithm (multiplying square $n\times n$ matrices) that has two different "complexities" depending on the context in which we are asking this question. Mar 9, 2021 at 7:07