Zoom link: https://harvard.zoom.us/j/779283357?pwd=MitXVm1pYUlJVzZqT3lwV2pCT1ZUQT09

Title: Holographic Algorithms
Speaker: Leslie Valiant
Affiliation: Harvard University
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 to be computationally intractable. We shall survey these ideas and their applications in computational complexity.