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

<ol>
<li><p>Is there an approach that can give <span class="math-container">$O(poly(n)poly(\max\log\|f_i\|_\infty))$</span> time?</p></li>
<li><p>What conditions are on the polynomials are needed to extract the unique root in <span class="math-container">$O(poly(n))poly(\max\log\|f_i\|_\infty)$</span> time in case roots 1. does not have a general algorithm?</p></li>
</ol>

<p>Is this approachable using Sum-of-squares? Note <span class="math-container">$f_i^2$</span> are all non-negative and have same integer roots. </p>

CC BY-SA 4.0
2019-03-18T21:43:43.650Z
Interesting question. I'm curious as to the motivation?
Joshua Grochow
CC BY-SA 4.0
2019-03-18T22:02:19.630Z
@JoshuaGrochow The motivation is circuitous and I can communicate privately if interested.
Turbo
CC BY-SA 4.0
2019-03-18T22:51:59.077Z
Sure, I'd be curious to hear.
Joshua Grochow
CC BY-SA 4.0
2019-03-18T23:26:04.573Z
@JoshuaGrochow Ok I will send you email. However do you think this can be solved?
Turbo
CC BY-SA 4.0
2019-06-05T11:04:54.657Z
@JoshuaGrochow I have completed documentation of this. May I send information on this approach?
Turbo
CC BY-SA 4.0
2019-06-05T13:09:54.493Z
Sure, go ahead.
Joshua Grochow
CC BY-SA 4.0
2019-06-05T14:26:10.920Z
@JoshuaGrochow sent.
Turbo
<cc.complexity-theory><nt.number-theory><polynomials><algebraic-complexity><sum-of-squares>
Complexity of planted root of a system of quadratic homogeneous polynomials?
Turbo
# Complexity of planted root of a system of quadratic homogeneous polynomials?

(Asked by: username_0 on 2019-03-18)

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.

**Tags:** cc.complexity-theory, nt.number-theory, polynomials, algebraic-complexity, sum-of-squares
> **Comments:**
> **username_1**: Interesting question. I'm curious as to the motivation?  
> **username_0**: @JoshuaGrochow The motivation is circuitous and I can communicate privately if interested.  
> **username_1**: Sure, I'd be curious to hear.  
> **username_0**: @JoshuaGrochow Ok I will send you email. However do you think this can be solved?  
> **username_0**: @JoshuaGrochow I have completed documentation of this. May I send information on this approach?  
> **username_1**: Sure, go ahead.  
> **username_0**: @JoshuaGrochow sent.  

---

## 0 answers

