The proposed work is on a number of fundamental problems in several areas of algorithm design and analysis. Work in three areas is planned. o Work on both limited and unlimited randomness is to be continued on two fronts, new algorithms and better tools for analyzing them. The analytic tools include better bounds for tail events, and extensions of operator theory to analyze performance in more difficult cases. o For suitably restricted classes, it should be feasible to automate the generation of algorithms problems for teaching, and to formulate very high level languages that admit natural solutions and support automated verification and refutation. Research for this section is aimed at exploring the fundamentals necessary to build a fledgling system to support the learning of algorithmic concepts. o While a rich variety of models for distributed processing have been devised, and many algorithms have been analyzed within these theoretical frameworks, some large scale machines are being built that run on different principles. This work is aimed at understanding such computation, which might be called semi-synchronous.
