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 -

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.

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 -

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