Probablistic Methods in Computer Science

计算机科学中的概率方法包括从算法的设计到算法的典型行为分析，再到证明复杂性理论中的下界。本研究集中在一些应用概率方法似乎很有前途的具体问题上。工作包括：(1)图算法（寻找着色问题和独立集大小问题的近似算法）；(2)并行排序（即所谓的PRAM模型）；(3)代数问题（Cayley图的直径）；(4)电路复杂度问题（非线性下界）；⑤在线算法的复杂性。根据以往的经验，渐近组合工具有望得到更广泛的应用。

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.