Please note: These two PhD seminars will be given online.
Bryce Sandlund, PhD candidate
David R. Cheriton School of Computer Science
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.
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) logn) bits of space, which is only a Θ(logn) 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 ∈ [1/2,1], the data structure supports meet and join queries in O(n^(1−c/2)) time, occupiesO(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 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.
200 University Avenue West
Waterloo, ON N2L 3G1