  In numerical linear algebra, a well-established practice is to choose a norm
that exploits the structure of the problem at hand in order to optimize
accuracy or computational complexity. In numerical polynomial algebra, a single
norm (attributed to Weyl) dominates the literature. This article initiates the
use of $L_p$ norms for numerical algebraic geometry, with an emphasis on
$L_{\infty}$. This classical idea yields strong improvements in the analysis of
the number of steps performed by numerous iterative algorithms. In particular,
we exhibit three algorithms where, despite the complexity of computing
$L_{\infty}$-norm, the use of $L_p$-norms substantially reduces computational
complexity: a subdivision-based algorithm in real algebraic geometry for
computing the homology of semialgebraic sets, a well-known meshing algorithm in
computational geometry, and the computation of zeros of systems of complex
quadratic polynomials (a particular case of Smale's 17th problem).
