Abstract: In this paper we describe a parallel programming paradigm called problem space promotion (PSP), a technique that increases parallelism by reducing communication and synchronization. We present four algorithms that exploit PSP and evaluate their communication characteristics relative to non-PSP solutions. Our analysis is aided by the use of parallel algorithm notation that is concise, yet accurately reflects parallelism and communication costs. Our analysis illustrates circumstances under which the use of PSP is beneficial and detrimental to performance, and experiments on the Cray T3E attest to the validity of the analysis. We find that PSP can significantly improve the performance and scaling behavior of certain computations, even when compared to existing high quality parallel algorithms.