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.

  • $\begingroup$ 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$? $\endgroup$ Mar 7, 2021 at 8:50
  • $\begingroup$ @FedericoPoloni Thanks for the response. I want the complexity of a practically feasible algorithm. $\endgroup$ Mar 7, 2021 at 8:53
  • $\begingroup$ 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. $\endgroup$ Mar 8, 2021 at 12:02
  • $\begingroup$ @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. $\endgroup$ Mar 9, 2021 at 6:08
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 9, 2021 at 7:07


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.