Probabilistic Methods in Computer Science

点击翻译按钮获取中文摘要

Probabilistic methods in Computer Science range from design of algorithms to analysis of typical behavior of algorithms to proving lower bounds in complexity theory. This research will concentrate on a number of specific problems where application of the probabilistic method seems promising. The questions include graph algorithms (finding approximation algorithms for the coloring problem and the independent set size problem), parallel sorting (in the so-called PRAM model), as well as algebraic questions (diameter of Cayley graphs), problems in circuit complexity (non-linear lower bounds), and complexity of on-line algorithms. Based on past experience, the asymptotic combinatorial tools are expected to be applicable more broadly, beyond the problems stated.