Communication complexity
See Information and coding theory ref.
Komogrov complexity
Of a computational object: Resourses required to specify it. Eg: If P is a program which outputs a string x, then P is a description of x. The length of the description is just the length of P as a character string.
Smoothed complexity
\tbc