25 citations · 54 across the 7 of their papers we have counts for
4 papers · 1 filter
Longest Increasing Subsequence under Persistent Comparison Errors
Barbara Geissmann
We study the problem of computing a longest increasing subsequence in a sequence of distinct elements in the presence of persistent comparison errors. In this model, every…
Parallel Minimum Cuts in Near-linear Work and Low Depth
Barbara Geissmann, Lukas Gianinazzi
We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum cut in a graph, while previous parallel algorithms with poly-logarithmic depth re…
Optimal Sorting with Persistent Comparison Errors
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We consider the problem of sorting elements in the case of \emph{persistent} comparison errors. In this model (Braverman and Mossel, SODA'08), each comparison between two eleme…
Sorting by Swaps with Noisy Comparisons
Tomáš Gavenčiak, Barbara Geissmann, Johannes Lengler
We study sorting of permutations by random swaps if each comparison gives the wrong result with some fixed probability . We use this process as prototype for the behaviour o…