The complexity of MinRank
arXiv:1905.02682v35 citations
Originality Synthesis-oriented
AI Analysis
This work addresses a theoretical problem in computational algebra and cryptography, but it is incremental as it builds on prior research.
The authors tackled the complexity of the generalized MinRank Problem, providing a concise and rigorous proof that recovers and extends previous results for under-defined and well-defined cases.
In this note, we leverage some of our results from arXiv:1706.06319 to produce a concise and rigorous proof for the complexity of the generalized MinRank Problem in the under-defined and well-defined case. Our main theorem recovers and extends previous results by Faugère, Safey El Din, Spaenlehauer (arXiv:1112.4411).