This award supports on-going research efforts on interactive computational models which incorporate both randomness and nondeterminism in novel ways. A fundamental goal of the work is to address what is probably the major open problem in computer science: how randomness and nondeterminism help in computation. Representative problems in this area are stochastic games, automata theory and random walks on graphs. Stochastic games model a large class of problems in optimization called decision problems under uncertainty. Finite state automata are studied with both nondeterministic and random states in order to understand the difference between such models and their deterministic counterparts. New questions about random walks have been formulated on graphs that are partly controlled by an adversary; in our scenario edges of the graph are colored and the adversary can control the walk by specifying which color edge is followed at a given step. Further this award supports ongoing research regarding the need for a more realistic theory of parallel computation. The design and implementation of algorithms on parallel machines is combined with analysis of these algorithms on realistic models. Two algorithmic paradigms will be restudied: dynamic programming and branch and bound. Emphasis will be on applications of dynamic programming to problems in DNA sequence analysis and of branch and bound algorithms to problems in combinatorial optimization. Also a new look is taken at what it means for a problem to be ``inherently sequential''.
