中央研究院統計科學研究所

學 術 演 講


講 題:The Power of Randomness in Computation

演講人:呂 及 人 教 授(本院資訊所副研究員)

時 間:2005年7月25日(星期一)上午10:30-12:00

地 點:中央研究院統計科學研究所二樓交誼廳

※茶會:上午10:10統計所二樓交誼廳


摘 要

  Randomness is a powerful resource in computation. As we will see, randomness can be used to save time, space, or communication, and provide new ways for doing mathematical proofs. However, randomized algorithms typically depend on the availability of a perfect random source, whose existence even in nature is debatable. We will see how to deal with this issue, using randomness extractors and pseudo-random generators.