Algebraic Complexity

The BSS and related models of real computation has a distinctive algebraic flavour -- and so does its corresponding theory of computation. In particular, the classical field of (non-effective) algebra provides for a rich variety of concepts and tools which have spurred quantitative complexity results and established (quasi) optimality for many algorithms -- which discrete complexity is still far from. Morgenstern's volume bound for instance proves that the Fast Fourier Transform's running time can (in the model with bounded coefficients) not be improved asymptotically. On the other hand, Strassen's Fast Matrix Multiplication has shown cubic-time Gaussian Elimination to be suboptimal; and initiated the scintillating theory of tensor rank.

It is the merit of Blum, Shub, and Smale (1989) to have transferred structural complexity theory from the discrete to the real (and complex) setting by proving Hilbert's Nullstellensatz complete for $\mathcal{NP}_{\mathbb{C}}$. Present research locates many classical theorems in algebraic geometry as complete for (BSS-counterparts to discrete) complexity classes.

Selected References: Bürgisser, Clausen, Shokrollahi: Algebraic Complexity Theory, Springer (1997)