Alek Westover

activity

20202026

collaborators

Showing 2024Show all

6 papers · 1 filter

cs.DS2024

Listing 6-Cycles in Sparse Graphs

Virginia Vassilevska Williams, Alek Westover

This work considers the problem of output-sensitive listing of occurrences of $2 k$ -cycles for fixed constant $k \geq 2$ in an undirected host graph with $m$ edges and $t$ $2 k$ -cycle…

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.DS2024

When to Give Up on a Parallel Implementation

Nathan S. Sheffield, Alek Westover

In the Serial Parallel Decision Problem (SPDP), introduced by Kuszmaul and Westover [SPAA'24], an algorithm receives a series of tasks online, and must choose for each between a se…

cs.CC2024

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree

Brian Liu, Nathan S. Sheffield, Alek Westover

We study the following generalization of the Hamiltonian cycle problem: Given integers $a, b$ and graph $G$ , does there exist a closed walk in $G$ that visits every vertex at least…

cs.DS2024

A Nearly Quadratic Improvement for Memory Reallocation

Martin Farach-Colton, William Kuszmaul, Nathan Sheffield +1

In the Memory Reallocation Problem a set of items of various sizes must be dynamically assigned to non-overlapping contiguous chunks of memory. It is guaranteed that the sum of the…

cs.DS2024

Scheduling Jobs with Work-Inefficient Parallel Solutions

William Kuszmaul, Alek Westover

This paper introduces the \emph{serial-parallel decision problem}. Consider an online scheduler that receives a series of tasks, where each task has both a parallel and a serial im…