Efficient Algorithm Design Using Randomness Parsimoniously

点击翻译按钮获取中文摘要

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.