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 concentrates on a number of specific problems where application of the probabilistic method seems promising. The work includes: (1) graph algorithms (finding approximation algorithms for the coloring problem and the independent set size problem); (2) parallel sorting (in the so-called PRAM model); (3) algebraic questions (diameter of Cayley graphs); (4) problems in circuit complexity (non-linear lower bounds); and (5) complexity of on-line algorithms. Based on past experience, the asymptotic combinatorial tools are expected to be applicable more broadly.
