The major applications of probabilistic techniques in Discrete Mathematics include the development of powerful methods to deal with Graph Coloring Problems and with Ramsey type questions, the recent asymptotic resolution of $R(3,k)$ being one particularly notable success. Another active area has been the combination of spectral Graph Theory and probabilistic methods in the study of expanders. These are graphs with strong pseudo-random properties that have numerous applications in the design of efficient communication and sorting networks, in the construction of powerful error correcting codes and in the development of efficient derandomization procedures. Probabilistic techniques also played a major role in the most exciting development in Theoretical Computer Science over the last decade; the result that any NP statement has a (short) proof that can be checked probabilistically with extreme efficiently, and its relevance to the hardness of approximation of many interesting problems in Combinatorial Optimization.
One subtheme will be the new uses of probability. The Lovasz Local Lemma, Janson's Inequality, martingale techniques, Talagrand's inequality, branching processes, stochastic differential equations, entropy and other techniques have all been brought to bear with the object of proving the existence of an appropriate combinatorial object. No longer do linearity of expectation and the Chernoff bounds suffice!
One of the main reasons for the fast recent development of modern Combinatorics is its tight connection to Theoretical Computer Science, which has been a source of numerous fascinating combinatorial problems over the last two decades. Probabilistic techniques have been very powerful in tackling these problems. The study of Random Algorithms is closely aligned to the Probabilistic Method. These techniques are also applied in the development of Isoperimetric Inequalities and the study of rapidly mixing Markov Chains which are useful in the design of efficient ways to estimate quantities which are hard to compute and arise in Combinatorics and in Statistical Physics.
The workshop will bring together renowned researchers in Combinatorics, Probability and Computer Science with younger mathematicians working in these areas. There would be about 15-20 lectures presenting progress, trends, directions and open problems, together with ample time for discussions between the participants, enabling them to communicate recent results and discuss recent problems. We believe that the interaction between the participants from various disciplines will be very helpful in the propagation of recent tools and the generation of new ideas.
Next: Call for Participation
Workshop Index
DIMACS Homepage