Since the 1970s, it has been known that algebraic geometry provides concepts and methods for proving that the evaluation of certain polynomials is hard. However, the range of these methods so far has been limited, and its successful application to algebraic versions of NP-complete problems (e.g., computing the permanent) has remained elusive. The approach of attacking these problems using the representation theory of groups (symmetries) reveals fascinating and unexpected connections with other areas of mathematics. A remarkable recent insight is an intimate connection between effective questions of classical invariant theory (as studied in the 19th century) and the presumed hardness of the permanent.
This talk will survey these connections at a high level. No detailed knowledge of algebra or complexity theory will be assumed.
Light refreshments will be served before the lecture at 3:30 p.m.
All scheduled dates:
Upcoming
No Upcoming activities yet