2
$\begingroup$

I'm studying algorithms solving multivariate equations. I'm stuck in solving overdetermined set of quadratic equations. Concretely, with the number $n$ of variables, the number of equations is $m=\epsilon n^2$. If $\epsilon\geq 1/2$, it is known that trivial linearization solves the set of equations. However, in the case that $\epsilon<1/2$, the trivial linearization seems not working anymore.

But there are some papers suggesting that if $\epsilon$ is somewhat large ($1/16<\epsilon<1/2$) then the system of equations can be solved in $O(n^{2\omega})$-time where $2\leq\omega\leq3$ is linear algebra constant. Efficient algorithms for solving overdefined systems of multivariate polynomial equations claimed that the time complexity of XL algorithm is $O(n^{\omega\lceil\frac 1 {\sqrt{\epsilon}}\rceil})$. It implies that if $1/4\leq \epsilon<1/2$ then the time complexity is $O(n^{2\omega})$. But I cannot catch the case.

One more paper here. Complexity of Groebner basis computation for semi-regular overdetermined sequences over F_2 with solutions in F_2 claimed that the degree of regularity is asymptotically $\max(1/8\epsilon,2)$ which implies that if $1/16\leq \epsilon<1/2$ then the time complexity of F5 algorithm is $O(n^{2\omega})$.

For both cases, I don't know how the algorithms can get such time complexity (when maximal degree of XL or F5 computation is 2). Are those my missings or just asymptotics not for the cases?

$\endgroup$

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.