I have a system of $m$ homogeneous degree $2$ polynomial equations in $\mathbb Z[x_1,\dots,x_n]$ where $m=poly(n)$. Take $$f_1(x_1,\dots,x_n)=0$$ $$\dots$$ $$f_m(x_1,\dots,x_n)=0$$ to be the system.
Typically such a system has $\emptyset$ intersection. In my case by design there are common roots that have integer coordinates and only these integer coordinated roots are the common solution.
Since degree is $2$ we have rank $1$ solution which if sparse then is probably amenable to compressed sensing type approaches. In my case the rank $1$ solutions are non-sparse.
Does Putinar's/Stengle's Positivstellensatz + SOS proof systems help?
MAIN PROBLEM 1 Does both SOS proof system and resultant approach for $m=n$ (case 1.) give a complexity that scales as $2^{O(n)}poly(nL)$ where $L$ is number of bits to represent the polynomials?
To the system above include hyperplane conditions $H_1,\dots,H_r$ where $r=O(1)$.
MAIN PROBLEM 2 Resultants do not apply now. Does SOS proof system for $n\ll m=poly(n)$ (case 2.) give a complexity that scales as $2^{O(n)}poly(nL)$ where $L$ is number of bits to represent the polynomials?
