UC Irvine

Theoretical analysis of algorithms relies on idealized models of computers. This inevitably creates a gap between what is efficient in theory and in practice, motivating fine-grained models which better emulate real-world constraints. This thesis makes new developments in two such models. First, we consider the noisy primitives model. Here, each comparison, such as ''is a < b?'', independently returns the wrong answer with probability p < 1/2. This model has applications in quantum and distributed computing. We extend the model to various geometric problems with Boolean geometric primitive comparisons such as ''is point p above line L?''. We give optimal sequential and parallel algorithms that solve these geometric problems using new techniques in random walks and parallel divide-and-conquer. Second, we consider in-place models of computation, in which memory usage is restricted. We give the first sorting algorithm that is optimal in terms of the run-entropy of the input and only uses O(1) additional memory. We also define a new model of memory-efficient parallelism called Strict Synchronous Parallel In-Place and give efficient parallel algorithms that require no auxiliary shared memory. We introduce novel techniques to ensure that our algorithms in this model remain efficient and in-place at all processor counts.