Randomness and complexity

随机性和复杂性

• 批准号: 283327-2007
• 负责人: Srinivasan, Venkatesh
• 金额: $ 1.49万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=395652
• 关键词: Randomness; complexity

This research program studies the strengths and limitations of randomized algorithms in various computational settings. A randomized algorithm is an algorithm that has access to a source of random bits and uses it as an auxiliary input to guide its behaviour. During the last two decades, understanding the role of randomness in computation has been an fascinating area of research leading to several fundamental results.

这项研究计划研究各种计算环境中随机算法的优点和局限性。随机化算法是一种能够访问随机比特源并将其用作辅助输入以指导其行为的算法。在过去的二十年里，理解随机性在计算中的作用一直是一个迷人的研究领域，导致了几个基本的结果。