Probablistic Methods in Computer Science

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

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.