Alek Westover

activity

20202026

collaborators

11 papers

cs.AI2026

Distillation for Incrimination and Distillation for Capabilities

Sebastian Prasanna, Jacqueline Tay, Alek Westover

Powerful misaligned AI models might recognize alignment evaluations and strategically behave well on them, rendering direct audits uninformative. However, distilling such a model i…

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…

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…

cs.DS2023

On the Relationship Between Several Variants of the Linear Hashing Conjecture

Alek Westover

In Linear Hashing ( $LH$ ) with $β$ bins on a size $u$ universe $U = {0, 1, \dots, u - 1}$ , items ${x_{1}, x_{2}, \dots, x_{n}} \subset U$ are placed in bins by…

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…