This is the video of the BMS Friday lecture by Peter Bürgisser (TU Berlin) entitled "Geometry, invariants, and the elusive search for complexity lower bounds". The talk was given on April 24, 2015 at the BMS Loft at Urania.
Since the 1970s, it has been known that algebraic geometry provides concepts and methods for proving that the evaluation of certain polynomials is algorithmically difficult. However, the range of these methods so far has been limited, and its successful application to algebraic versions of NP–complete problems has remained elusive.
The flagship question, introduced by Leslie Valiant in 1979, is the “permanent versus determinant problem“. It is simple to state, but despite considerable efforts, completely open. A recent suggestion, named “geometric complexity theory“, is to attack this and similar problems by representation theory of groups (symmetries) and geometric invariant theory. The approach reveals fascinating and unexpected connections with other areas of mathematics. A remarkable recent insight is an intimate connection of effective questions of classical invariant theory (as studied in the 19th century), and the presumed hardness of the permanent.
For more information about BMS Fridays, visit our website at: math-berlin.de/academics/bms-fridays.