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.