Lecture: Holographic Algorithms

Leslie G. Valiant

Abstract:

When are two mathematical functions the same? One might think that this can be generally answered immediately from their definitions. However, functions may have numerous dissimilar alternative definitions. Fortunately, sameness can be often demonstrated systematically by certain linear mappings internal to the function definitions. These mappings, called holographic transformations, offer a powerful tool for showing that a function class is equivalent to one known to be efficiently computable, or, alternatively, that it is equivalent to one known to be in a completeness class suspected of being computationally intractable. We shall survey these ideas and their applications in computational complexity.

---