New Methods for the Analysis of Randomized Algorithms

随机性是设计有效算法的一个非常强大的资源。随机算法的分析需要获得可证明的保证，关于他们的正确性和效率引入了重大的挑战，和许多基本问题的随机性的一般权力，在有效的计算仍然是开放的问题在复杂性理论。该研究旨在通过开发和利用新的算法，数学和信息理论方法来设计和分析随机算法，以克服这些重要的挑战。这些方法将导致新的高效算法的多个基本的计算任务，新的方法来确定随机算法的局限性，以及新的见解之间的相互作用的随机性和计算。这项研究将提供一个重要的一步，在实现高层次的长期目标，建立一个完整的，统一的，和健全的理论基础的随机算法。

Randomness is a remarkably powerful resource in the design of efficient algorithms. The analysis of randomized algorithms required to obtain provable guarantees regarding their correctness and efficiency introduces significant challenges, and many basic questions about the general power of randomness in efficient computation remain open problems in complexity theory. The proposed research aims to overcome these important challenges by developing and exploiting new algorithmic, mathematical, and information-theoretic methods for the design and analysis of randomized algorithms. These methods will lead to new efficient algorithms for multiple fundamental computational tasks, to new methods for determining the limitations of randomized algorithms, and to new insights on the interplay between randomness and computation. This research will provide an important step in reaching the high-level long-term goal of establishing a complete, unified, and sound theoretical foundation for randomized algorithms.