关键词：有效计算；概率分布；随机性；输入；输出；算法；查询复杂性
摘 要：This dissertation explores the multifaceted interplay between efficient computation and prob-ability distributions. We organize the aspects of this interplay according to whether the randomness occurs primarily at the level of the problem or the level of the algorithm, and orthogonally according to whether the output is random or the input is random.
目 录：