Research Programme ; Academic Year 2009

RESEARCH PROGRAMME IN

PROBABILISTIC TECHNIQUES IN COMPUTER SCIENCE

An i-MATH Intensive Research Programme

Probabilistic Techniques in Computer Science constitutes a well developed area of research that combines Theoretical Computer Science, Discrete Mathematics, Probability Theory and Combinatorics. Hundreds of papers on probabilistic techniques appear each year in journals and conference proceedings, both general and specialized in this area, contributing with fresh ideas and opening novel paths of research.

There are two basic lines of research in the area. In one of them, the goal is to obtain precise and mathematically rigorous probabilistic predictions about the performance of algorithms. For many important algorithms, the worst-case performance has little practical relevance as it is highly unlikely; on the contrary, an understanding of their behavior in typical situations is of great practical value, as well as scientifically appealing. Besides that, many useful algorithms and data structures using randomization have been developed in recent years, for which probabilistic analysis is just the right tool.

The other main line of research makes use of probabilistic techniques in the study of combinatorial objects relevant to CS. For a concrete example that has attracted much interest lately consider the study of thresholds for properties of combinatorial objects. Boolean formulas of a fixed clause length are a paradigmatic example. It has been observed by simulation experiments that if the clauses to variables ratio (density) of a random formula is below a constant number (~4.25$, for 3-CNF formulas) then the formula is asymptotically (as the number of the variables grows large) almost always satisfiable. If the density is larger than this threshold number, then the formula is asymptotically almost always non-satisfiable. Several researchers obtained rigorous mathematical proofs for lower and upper bounds of such thresholds and have studied the geometry of the solution space. This area is characterized by an interesting cross-fertilization of ideas between physics on one hand and probability theory, combinatorics and discrete mathematics on the other.

Although the above two lines of research (one concentrating mainly on the probabilistic analysis os algorithms and the other on the study of combinatorial objects from a probabilistic viewpoint) complement each other and contribute to the richness of the field, there was, for some time, a clear danger that the field evolved into separate branches with little or no mutual understanding.

One of the main objectives of this Research Programme is to bring into closer contact researchers from both communities and thus contribute to the further advancement of the field. The Programme thus adds to several recent similar initiatives to bridge the two approaches.