Skip to main content.
Advanced search >
<< Back to previous page Print

<< Monday, September 08, 2014 >>

Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare

Simons Institute Open Lecture: Geometry, Invariants, and the Elusive Search for Complexity Lower Bounds

Lecture | September 8 | 4 p.m. | Sutardja Dai Hall, Banatao Auditorium

Peter Bürgisser

Simons Institute for the Theory of Computing

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., 510.664.9856