Efficient Algorithm Design Using Randomness Parsimoniously

简约地利用随机性的高效算法设计

• 批准号: 9304722
• 负责人: Michael Luby
• 金额: $ 16.5万
• 依托单位: International Computer Science Institute
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-08-15 至 1997-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9304722&HistoricalAwards=false
• 关键词: Efficient; Algorithm; Design; Using; Randomness

The research is partitioned into four parts: (1) cryptography; (2) derandomization; (3) approximation algorithms; and (4) parallel and distributed algorithms. As described below, there are strong interconnections and themes that link the work in the different parts. The interaction between randomness and efficient computation is crucial in all parts. In cryptography, randomness is crucial for hiding information, and the interaction between randomness and computational power is the motivating force behind the definition of a pseudo-random generator. The derandomization part explores the development of general methods for converting efficient randomized algorithms into efficient deterministic algorithms, and thus the interplay between randomness and efficiency is central. The de-randomization part has strong connections with the parallel algorithms and approximation algorithms parts: some of the algorithms de-randomized are randomized parallel algorithms, and some are randomized approximation algorithms. Some of the work in the approximation algorithms part develops efficient randomized approximation algorithms. The work on the approximation algorithms is done jointly with the ESPRIT RAND working group.

研究内容分为四个部分：（1）密码学； (2)去随机化； (3)近似算法； (4)并行和分布式算法。 如下所述，不同部分的作品之间存在着紧密的相互联系和主题。 随机性和高效计算之间的相互作用在所有部分都至关重要。 在密码学中，随机性对于隐藏信息至关重要，随机性和计算能力之间的相互作用是伪随机生成器定义背后的推动力。 去随机化部分探索了将有效的随机算法转换为有效的确定性算法的通用方法的开发，因此随机性和效率之间的相互作用是核心。 去随机化部分与并行算法和逼近算法部分有很强的联系：去随机化的算法有些是随机并行算法，有些是随机逼近算法。 近似算法部分的一些工作开发了高效的随机近似算法。 近似算法的工作是与 ESPRIT RAND 工作组联合完成的。