Titles and abstracts
Pierre Pansu- Hardness of approximation
Some combinatorial problems seem not to be algorithmically
solvable in polynomial time. MAX CUT is one of them. Even finding an
approximate solution is hard, but this depends on the approximation
factor: there is an algorithm which achieves a factor of 0.878... There
is now strong evidence that this number is the approximability
threshold: no algorithm could, in polynomial time, achieve a better
factor. As is almost always the case in theoretical computer science,
the proof, due to S. Khot, G. Kindler, E. Mossel and R. O'Donnell in
2005, is conditional, it assumes Khot's Unique Games Conjecture.
Itai Benjamini - On graph limits and random metric spaces
We will start with general comments on global and local graph limits.
Then we will discuss a couple of specific examples such as the uniform infinite planar quadrangulation,
random subdivisions and the hyperbolic stochastic infinite quadrangulation.
Nathan Linial - High-dimensional combinatorics
Geometry provides a very useful perspective on numerous basic
aspects of combinatorics. In this view it is not too surprising that a
notion of dimension comes into play. As it turns out, many of the most
fundamental objects of combinatorics are inherently one-dimensional.
This suggests that we look into higher-dimensional counterparts of these
objects. The most obvious place to start is with graphs which, viewed
geometrically, are one-dimensional simplicial complexes. I will discuss
some work on the extending the theory of random graphs to the realm of
random simplicial complexes. I will also discuss higher-dimensional
analogs of permutations. If time permits I will also enter briefly into
the local theory of graphs and of simplicial complexes.
Guoliang Yu - Embedding and higher index theory
I will discuss embeddability of groups, its connections to higher index theory of elliptic differential operators,
and applications to differential geometry and topology. I will make an effort for the lectures to be accessible to non-experts.
Back to the main page of the conference