Alek Westover

collaborators

8 papers

cs.DS2026

Lower Bounds for Linear Hashing via Arithmetic Kakeya

Ainesh Bakshi, Alex Conway, Hanna Komlós +2

Affine modular linear hashing is one of the simplest classical hash families. For a prime $p > u$ , the hash function is obtained by choosing $s, t$ uniformly from $Z_{p}$ and…

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…