6 citations · 6 across the 2 of their papers we have counts for
6 papers
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…
Sorting with Recurrent Comparison Errors
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sort…
Counting small cuts in a graph
Barbara Geissmann, Rastislav Šrámek
We study the minimum cut problem in the presence of uncertainty and show how to apply a novel robust optimization approach, which aims to exploit the similarity in subsequent graph…