Seminar: Hilde Verbeek (CWI) and Bram Bekker (TU Delft), 2 PhD Talks

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Hilde Verbeek (CWI)

Title: Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast

Abstract:
Sparse suffix sorting is the problem of sorting $b=o(n)$ suffixes of a string of length $n$. Efficient sparse suffix sorting algorithms have existed for more than a decade. Despite the multitude of works and their justified claims for applications in text indexing, the existing algorithms have not been employed by practitioners. Arguably this is because there are no simple, direct, and efficient algorithms for sparse suffix array construction. We provide two new algorithms for constructing the sparse suffix and LCP arrays that are simultaneously simple, direct, small, and fast. In particular, our algorithms are: simple in the sense that they can be implemented using only basic data structures; direct in the sense that the output arrays are not a byproduct of constructing the sparse suffix tree or an LCE data structure; fast in the sense that they run in $O(n \log b)$ time, in the worst case, or in $O(n)$ time, when the total number of suffixes with an LCP value greater than $2^{\lfloor \log \frac{n}{b} \rfloor + 1} − 1$ is in $O(b / \log b)$, matching the time of the optimal yet much more complicated algorithms [Gawrychowski and Kociumaka, SODA 2017; Birenzwige et al., SODA 2020]; and small in the sense that they can be implemented using only $8b + o(b)$ machine words. Our algorithms are simplified, yet non-trivial, space-efficient adaptations of the Monte Carlo algorithm by I et al. for constructing the sparse suffix tree in $O(n \log b)$ time [STACS 2014]. We also provide proof-of-concept experiments to justify our claims on simplicity and efficiency.

Based on https://arxiv.org/abs/2310.09023.

Video:

Slides:
Slides

Speaker: Bram Bekker (TU Delft)

Title: SDP hierarchies for distance-avoiding sets on compact spaces

Abstract:
Witsenhausen's problem asks for the maximum fraction α_n of the n-dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. We extended well known optimization hierarchies based on the Lovász theta number, like the Lasserre hierarchy, to Witsenhausen's problem and similar problems. These hierarchies are shown to converge and are used to compute the best upper bounds known for αn in low dimensions.

Based on https://arxiv.org/abs/2304.05429.

Video:

Slides:
Slides