In this paper we develop optimal algorithms in the binary-forking model for a variety of
fundamental problems, including sorting, semisorting, list ranking, tree contraction, range …

Memory latency and bandwidth are significant bottlenecks in designing in-memory indexes.
Processing-in-memory (PIM), an emerging hardware design approach, alleviates this …

The cover tree is the canonical data structure that efficiently maintains a dynamic set of
points on a metric space and supports nearest and k-nearest neighbor searches. For most …

In this article, we show that many sequential randomized incremental algorithms are in fact
parallel. We consider algorithms for several problems, including Delaunay triangulation …

Some recent papers showed that many sequential iterative algorithms can be directly
parallelized, by identifying the dependences between the input objects. This approach …

Hiding countermeasure is among the best-known secure implementation techniques
designed to counteract side-channel attacks. It uses a permutation algorithm to shuffle data …

Motivated by the significantly higher cost of writing than reading in emerging memory
technologies, we consider parallel algorithm design under such asymmetric read-write …

The randomized incremental convex hull algorithm is one of the most practical and important
geometric algorithms in the literature. Due to its simplicity, and the fact that many points or …

In this paper, we design parallel write-efficient geometric algorithms that perform
asymptotically fewer writes than standard algorithms for the same problem. This is motivated …

This paper studies parallel algorithms for the longest increasing subsequence (LIS)
problem. Let n be the input size and k be the LIS length of the input. Sequentially, LIS is a …