  The condition-based complexity analysis framework is one of the gems of
modern numerical algebraic geometry and theoretical computer science. Among the
challenges that it poses is to expand the currently limited range of random
polynomials that we can handle. Despite important recent progress, the
available tools cannot handle random sparse polynomials and Gaussian
polynomials, that is polynomials whose coefficients are i.i.d. Gaussian random
variables.
  We initiate a condition-based complexity framework based on the norm of the
cube that is a step in this direction. We present this framework for real
hypersurfaces and univariate polynomials. We demonstrate its capabilities in
two problems, under very mild probabilistic assumptions. On the one hand, we
show that the average run-time of the Plantinga-Vegter algorithm is polynomial
in the degree for random sparse (alas a restricted sparseness structure)
polynomials and random Gaussian polynomials. 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 the
logarithm of the degree) not only for the average but also for all higher
moments.
