Research on Randomized Algorithms, Complexity Theory, and Quantum Computers

在过去的十年里，随机化和概率技术在理论计算机科学中发挥了至关重要的作用。这项研究涉及四个领域：(1)分析马尔可夫链的混合率，为近似计数问题设计有效的随机化算法--包括估计矩阵的恒等式的经典问题，(2)最近发现的概率可检验证明系统的进一步应用，以证明某些近似问题在计算上是困难的，特别是近似图的展开的问题，以及近似计数问题，(3)用于识别概率假设的Occam剃刀的推广的公式，以及(4)基于量子物理的计算设备的计算能力的研究。

Randomization and probabilistic techniques have played a vital role in theoretical computer science over the last decade. This research addresses four areas; (1) the analysis of mixing rates of Markov chains to design efficient randomized algorithms for approximate counting problems -- including the classical problem of estimating the permanent of a matrix, (2) further applications of recently discovered probabilistically checkable proof systems to prove that certain approximation problems are computationally hard, in particular, the problem of approximating the expansion of a graph, as well as approximate counting problems, (3) the formulation of a generalization of Occam's razor for the identification of probabilistic hypotheses, and (4) the study of the computational power of computing devices based on quantum physics.