Alek Westover

collaborators

3 papers

cs.CC2024

New Direct Sum Tests

Alek Westover, Edward Yu, Kai Zheng

A function $f : [n]^{d} \to F_{2}$ is a \defn{direct sum} if there are functions $L_{i} : [n] \to F_{2}$ such that $f (x) = \sum_{i} L_{i} (x_{i})$ . In this work we give multiple…

cs.DS2020

The Variable-Processor Cup Game

William Kuszmaul, Alek Westover

The problem of scheduling tasks on $p$ processors so that no task ever gets too far behind is often described as a game with cups and water. In the $p$ -processor cup game on $n$ cu…

cs.DS2020

In-Place Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory

William Kuszmaul, Alek Westover

We present an in-place algorithm for the partition problem that has linear work and polylogarithmic span. The algorithm uses only exclusive read/write shared variables, and can be…