Research Topics in Parallel Computing and Complexity Theory Research will be conducted in the areas of parallel computing and computational complexity. Specific topics include: o development of general methodologies for design and analysis of algorithms for parallel networks; development of techniques for efficient simulations between networks with different architectures; o investigation of the computational power of parallel networks in comparison to sequential models and other models of parallel computation; o mapping algorithms onto fixed-size parallel architectures and experimental validation; o development of techniques for showing problems to be in NC (the class of problems solvable by boolean circuits of polynomial size and polylogarithmic depth); o investigation of properties (e.g., closure properties) of NC; o topics in complexity theory: space-time trade-offs, hierarchies of computation, nondeterminism versus determinism, parallel versus sequential, (un) decidability of decision problems.
