Probabilistic Methods in Computer Science

计算机科学中的概率方法从设计 算法分析算法的典型行为， 证明复杂性理论中的下界。 这项研究将 集中讨论一些具体问题， 概率方法似乎很有前途。 的问题 包括图形算法（找到用于 着色问题和独立集大小问题）， 并行排序（在所谓的PRAM模型中），以及 代数问题（凯莱图的直径），问题 电路复杂度（非线性下限）和复杂度 在线算法。 根据以往的经验， 渐近组合工具预计是适用的 更广泛地说，超越了所述的问题。

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.