Geometry, computational complexity and algebraic number fields

Geometry Topology Seminar
Monday, November 23, 2009 - 14:00
1 hour (actually 50 minutes)
Skiles 269
Mathematical Institute of Academy of Sciences of the Czech Republic
In 1979 Valiant gave algebraic analogs to algorithmic complexity problem such as $P \not = NP$. His central conjecture concerns the determinantal complexity of the permanents. In my lecture I shall propose geometric and algebraic methods to attack this problem and other lower bound problems based on the elusive functions approach by Raz. In particular I shall give new algorithms to get lower bounds for determinantal complexity of polynomials over $Q$, $R$ and $C$.