Efficient Algorithm Design Using Randomness Parsimoniously

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

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.