Before revision:  We present explicit results with structured random polynomials for problems with two or more dimensions. Additionally, we provide some estimates of the separation bound of a univariate polynomial in our current framework .
After revision:  On the other hand, we study the size of the subdivision tree for Descartes' solver and run-time of the solver by Jindal and Sagraloff (arXiv:1704.06979). In both cases, we provide a bound that is polynomial in the size of the input (size of the support plus logarithm of the degree) for not only on the average, but all higher moments .