Source author record

Bryce Sandlund

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.GR Symbolic Computation

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Selectable Heaps and Optimal Lazy Search Trees

We show the $O(\log n)$ time extract minimum function of efficient priority queues can be generalized to the extraction of the $k$ smallest elements in $O(k \log(n/k))$ time (we define $\log(x)$ as $\max(\log_2(x), 1)$ .), which we prove optimal for comparison-based priority queues with $o(\log n)$ time insertion. We show heap-ordered tree selection (Kaplan et al., SOSA '19) can be applied on the heap-ordered trees of the classic Fibonacci heap and Brodal queue, in $O(k \log(n/k))$ amortized and worst-case time, respectively. We additionally show the deletion of $k$ elements or selection without extraction can be performed on both heaps, also in $O(k \log(n/k))$ time. Surprisingly, all operations are possible with no modifications to the original Fibonacci heap and Brodal queue data structures. We then apply the result to lazy search trees (Sandlund & Wild, FOCS '20), creating a new interval data structure based on selectable heaps. This gives optimal $O(B+n)$ time lazy search tree performance, lowering insertion complexity into a gap $Δ_i$ from $O(\log(n/|Δ_i|) + \log \log n)$ to $O(\log(n/|Δ_i|))$ time. An $O(1)$ time merge operation is also made possible when used as a priority queue, among other situations. If Brodal queues are used, all runtimes of the lazy search tree can be made worst-case.

preprint2020arXiv

A Simple Algorithm for Minimum Cuts in Near-Linear Time

We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that $2$ -respects (cuts two edges of) a spanning tree $T$ of a graph $G$ . This procedure can be used in place of the complicated subroutine given in Karger's near-linear time minimum cut algorithm (J. ACM, 2000). We give a self-contained version of Karger's algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an $m$ -edge, $n$ -vertex graph in $O(m \log^3 n)$ time with high probability, matching the complexity of Karger's approach.

preprint2020arXiv

Faster Dynamic Range Mode

In the dynamic range mode problem, we are given a sequence $a$ of length bounded by $N$ and asked to support element insertion, deletion, and queries for the most frequent element of a contiguous subsequence of $a$ . In this work, we devise a deterministic data structure that handles each operation in worst-case $\tilde{O}(N^{0.655994})$ time, thus breaking the $O(N^{2/3})$ per-operation time barrier for this problem. The data structure is achieved by combining the ideas in Williams and Xu (SODA 2020) for batch range mode with a novel data structure variant of the Min-Plus product.

preprint2020arXiv

Space-Efficient Data Structures for Lattices

A lattice is a partially-ordered set in which every pair of elements has a unique meet (greatest lower bound) and join (least upper bound). We present new data structures for lattices that are simple, efficient, and nearly optimal in terms of space complexity. Our first data structure can answer partial order queries in constant time and find the meet or join of two elements in $O(n^{3/4})$ time, where $n$ is the number of elements in the lattice. It occupies $O(n^{3/2}\log n)$ bits of space, which is only a $Θ(\log n)$ factor from the $Θ(n^{3/2})$ -bit lower bound for storing lattices. The preprocessing time is $O(n^2)$ . This structure admits a simple space-time tradeoff so that, for any $c \in [\frac{1}{2}, 1]$ , the data structure supports meet and join queries in $O(n^{1-c/2})$ time, occupies $O(n^{1+c}\log n)$ bits of space, and can be constructed in $O(n^2 + n^{1+3c/2})$ time. Our second data structure uses $O(n^{3/2}\log n)$ bits of space and supports meet and join in $O(d \frac{\log n}{\log d})$ time, where $d$ is the maximum degree of any element in the transitive reduction graph of the lattice. This structure is much faster for lattices with low-degree elements. This paper also identifies an error in a long-standing solution to the problem of representing lattices. We discuss the issue with this previous work.

preprint2016arXiv

Baby-Step Giant-Step Algorithms for the Symmetric Group

We study discrete logarithms in the setting of group actions. Suppose that $G$ is a group that acts on a set $S$ . When $r,s \in S$ , a solution $g \in G$ to $r^g = s$ can be thought of as a kind of logarithm. In this paper, we study the case where $G = S_n$ , and develop analogs to the Shanks baby-step / giant-step procedure for ordinary discrete logarithms. Specifically, we compute two sets $A, B \subseteq S_n$ such that every permutation of $S_n$ can be written as a product $ab$ of elements $a \in A$ and $b \in B$ . Our deterministic procedure is optimal up to constant factors, in the sense that $A$ and $B$ can be computed in optimal asymptotic complexity, and $|A|$ and $|B|$ are a small constant from $\sqrt{n!}$ in size. We also analyze randomized "collision" algorithms for the same problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Bryce Sandlund

Research overview

Is this your work?

5 publications

Selectable Heaps and Optimal Lazy Search Trees

A Simple Algorithm for Minimum Cuts in Near-Linear Time

Faster Dynamic Range Mode

Space-Efficient Data Structures for Lattices

Baby-Step Giant-Step Algorithms for the Symmetric Group

See the researcher in context

Building this map preview