Holographic Algorithms

MATHEMATICAL PICTURE LANGUAGE

View Calendar
November 16, 2021 9:30 am - 10:30 am
via Zoom Video Conferencing
Speaker:

Leslie Valiant - Harvard University


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.


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