Confirmed keynote speakers:
Abstracts of the invited presentations:
|
Phase transitions have long been studied in statistical mechanics. Indeed, physicists have developed ingenious, albeit non-rigorous, techniques for the study of phase transitions. In recent years it has emerged that phase transitions also play a key role in computer science. In this talk I am going to give an overview of this exciting area, and explain how ideas from statistical mechanics shed light on the mystery of computational complexity. In addition, I am going to survey the recent progress in turning the statistical mechanics work into a rigorous theory.
Slides in PDF format. |
|
In recent years there has been increasing interest in the asymptotic
analysis of (several classes of) planar maps and planar graphs.
This was initiated by bijective methods (e.g. the Shaeffer bijection),
generating function methods (e.g. Gimenez and Noy's result on the asymptotics
of number of planar graphs) and the search for probabilistic limiting
objects (e.g. the Brownian map by Le Gall). In particular in the discussion of
several planar graph classes (like series-parallel graphs or labelled planar graphs)
a dichotomy between a "critical" and "subcritical" behaviour between
2-connected and connected graphs was observed. Informally a graph class is
subcritical when all 2-connected components are small (i.e., at most of log n - size)
and one observes a "treelike structure". Conversely a graph class is critical
when the largest 2-connected component is comparable to the size of the
whole graph.
The purpose of this talk is to discuss the asymptotic behaviour of several (extremal) parameters of subcritical and critical graph classes, in particular the diameter and the maximum degree. For subcritical graph classes the diameter is (usually) of oder n^(1/2) whereas we can expect the order n^(1/4) in the critial case. On the other hand the maximum degree is (usually) of order log n in both cases. However, critical graph classes are notoriously more difficult to handle than subcritical ones. This talk is mainly based on joint work with Omer Gimenez, Marc Noy, Konstantinos Panagiotou, and Angelika Steger. Slides in PDF format. |
|
We give a unified treatment of the limit, as the size tends to infinity, of random simply generated trees, including both the well-known result in the standard case of critical Galton-Watson trees and similar but less well-known results in the other cases (i.e., when no equivalent critical Galton-Watson tree exists). There is a well-defined limit in the form of an infinite random tree in all cases; for critical Galton-Watson trees this tree is locally finite but for the other cases the random limit has exactly one node of infinite degree.
The random infinite limit tree can in all cases be constructed by a modified Galton-Watson process. In the standard case of a critical Galton-Watson tree, the limit tree has an infinite "spine", where the offspring distribution is size-biased. In the other cases, the spine has finite length and ends with a vertex with infinite degree. A node of infinite degree in the limit corresponds to the existence of one node with very high degree in the finite random trees; in physics terminology, this is a type of condensation. In simple cases, there is one node with a degree that is roughly a constant times the number of nodes, while all other degrees are much smaller; however, more complicated behaviour is also possible. The proofs use a well-known connection to a random allocation model that we call balls-in-boxes, and we prove corresponding results for this model. Slides in PDF format. |
| To deal with NP-hard reconstruction problems, one natural possibility consists in assuming that the input data is a noisy version of some unknown ground truth. We present two such examples: correlation clustering, and transitive tournaments. In correlation clustering, the goal is to partition data given pairwise similarity and dissimilarity information, and sometimes semi-definite programming can, with high probability, reconstruct the optimal (maximum likelihood) underlying clustering. The proof uses semi-definite programming duality and the properties of eigenvalues of random matrices. The transitive tournament problem asks to reverse the fewest edge orientations to make an input tournament transitive. In the noisy setting it is possible to reconstruct the underlying ordering with high probability using simp dynamic programming. We conclude with related open questions. |
|
We study several natural problems in which an unknown distribution over an unknown population of vectors needs to be recovered from partial or noisy samples. Such problems naturally arise in a variety of contexts in learning, clustering, statistics, data mining and database privacy, where loss and error may be introduced by nature, inaccurate measurements, or on purpose. We give fairly efficient algorithms to recover the data under fairly general assumptions, when loss and noise are close to the information theoretic limit (namely, nearly completely obliterate the original data).
Underlying our algorithms is a new structure we call a partial identification (PID) graph. While standard IDs are subsets of features (vector coordinates) that uniquely identify an individual in a population, partial IDs allow ambiguity (and "imposters"), and thus can be shorter. PID graphs capture this imposter-structure. PID graphs yield strategies for dimension reductions of recovery problems, and the re-assembly of this local pieces of statistical information to a global one. The quality of our recovery algorithms critically depends on three parameters of PID graphs: width, depth and cost. The combinatorial heart of this work is showing that every set of vectors posses a PID graph in which all three parameters are small (we also prove some limitations on their trade-offs). We further give an efficient algorithm to find such near-optimal PID graphs for any set of vectors. This is joint work with Amir Yehudayoff. Slides in PDF format. |