Workshop I: Probabilistic Techniques and Applications

October 5 - 9, 2009


One of the exciting phenomena in mathematics in recent years has been the wide-spread and surprisingly effective use of probabilistic methods in diverse areas. The probabilistic approach has been strikingly successful in Combinatorics, Graph Theory, Combinatorial Number Theory, Optimization and Theoretical Computer Science. This workshop will focus on several main research directions of Probabilistic Combinatorics, including the application of probability to solve combinatorial problems, the study of random combinatorial objects and the investigation of randomized algorithms.

Specific topics to be discussed will include: the application of probabilistic arguments to Ramsey and Turan-type problems and to graph colorings, the semi-random method, tools like the Local lemma, large deviation and correlation inequalities, the classical ErdH{o}s-Renyi random graphs model and its variations, the investigation of various graph processes and hitting times, random regular graphs, models based on preferential attachment and real world networks, random subgraphs of given graphs and applications to various percolation models, the study of the random k-SAT problem and other random instances of computationally hard problem, applications of randomness to Computer Science, in particular to the design of efficient algorithms, derandomization and pseudo-randomness.

Organizing Committee

Alan Frieze (Carnegie-Mellon University, Mathematical Sciences)
Nathan (Nati) Linial (Hebrew University, Computer Science)
Angelika Steger (ETH Zürich)
Benjamin Sudakov (University of California, Los Angeles (UCLA))
Prasad Tetali (Georgia Institute of Technology)