Monday, May 26, 2014
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
The phase transition in random graphs refers to a phenomenon that there is a drastic change of the size and structure of the largest component, caused by altering a critical edge density. In the Erdős and Rényi graph process, which begins with an empty graph on n vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches n/2 and a giant component emerges. In this talk we will discuss key results and techniques to study the size of giant components in various random graphs.
Colloquium - 16:00
Abstract:
The famous P vs NP problem is a conjecture about the inherent difficulties of certain computational problems. Based on work of Valiant from 1979, Mulmuley and Sohoni in 2001 proposed to view the P vs NP and related problems as specific orbit closure problems and to attack them by methods from geometric invariant and representation theory. They coined the term geometric complexity theory for their approach. It turns out that geometric complexity theory can also be used to study the complexity of computational tasks in linear algebra, most notably matrix multiplication. This insight is based on combining geometric complexity theory with a line of research on bilinear maps and tensor rank started by Strassen in 1969. This talk aims to be an introduction to some key ideas of geometric complexity theory on a basic level.