# Complexity of planted root of a system of quadratic homogeneous polynomials?

Given homogeneous degree $$2$$ randomly chosen polynomials $$f_1,\dots,f_{m}$$ in $$\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$$ each with only monomials $$x_iy_j$$ with condition that the system $$f_1=\dots=f_{m}=0$$ has an unique common root in $$\mathbb Z^{2n}\backslash\{{(0,\dots,0)}\}$$ upto sign and exchange of $$x$$ and $$y$$ variables we can extract the root with elimination theory in $$2^{O(n)}poly(\max\log\|f_i\|_\infty)$$ time if $$m=2n$$ holds. Assume we have $$m=poly(n)$$ random equations (note only any $$2n$$ of them can be algebrically independent and they will be so with high propbaility).

1. Is there an approach that can give $$O(poly(n)poly(\max\log\|f_i\|_\infty))$$ time?

2. What conditions are on the polynomials are needed to extract the unique root in $$O(poly(n))poly(\max\log\|f_i\|_\infty)$$ time in case roots 1. does not have a general algorithm?

Is this approachable using Sum-of-squares? Note $$f_i^2$$ are all non-negative and have same integer roots.

• Interesting question. I'm curious as to the motivation? – Joshua Grochow Mar 18 '19 at 21:43
• @JoshuaGrochow The motivation is circuitous and I can communicate privately if interested. – T.... Mar 18 '19 at 22:02
• Sure, I'd be curious to hear. – Joshua Grochow Mar 18 '19 at 22:51
• @JoshuaGrochow Ok I will send you email. However do you think this can be solved? – T.... Mar 18 '19 at 23:26
• @JoshuaGrochow I have completed documentation of this. May I send information on this approach? – T.... Jun 5 '19 at 11:04