  Renormalized homotopy continuation on toric varieties is introduced as a tool
for solving sparse systems of polynomial equations, or sparse systems of
exponential sums. The cost of continuation depends on a renormalized condition
length, defined as a line integral of the condition number along all the lifted
renormalized paths.
  The theory developed in this paper leads to a continuation algorithm tracking
all the solutions between two generic systems with the same structure. The
algorithm is randomized, in the sense that it follows a random path between the
two systems. The probability of success is one. In order to produce an expected
cost bound, several invariants depending solely of the supports of the
equations are introduced. For instance, the mixed area is a quermassintegral
that generalizes surface area in the same way that mixed volume generalizes
ordinary volume. The facet gap measures for each 1-cone in the fan and for each
support polytope, how close is the supporting hyperplane to the nearest vertex.
Once the supports are fixed, the expected cost depends on the input
coefficients solely through two invariants: the renormalized toric condition
number and the imbalance of the absolute values of the coefficients. This leads
to a non-uniform polynomial complexity bound for polynomial solving in terms of
those two invariants.
