6 citations · 10 across the 7 of their papers we have counts for
5 papers · 1 filter
Near-Optimal Parallel -Matrix Scaling
Chih-Hung Liu, Aaron Sidford, Ta-Wei Tu
In this paper we consider the problem of computing a positive diagonal scaling of a symmetric -matrix so that all row and column sums are . We provide a poly-log…
Approximate Selection with Unreliable Comparisons in Optimal Expected Time
Shengyu Huang, Chih-Hung Liu, Daniel Rutschman
Given elements, an integer and a parameter , we study to select an element with rank in using unreliable comparisons where th…
Approximate Minimum Selection with Unreliable Comparisons in Optimal Expected Time
Stefano Leucci, Chih-Hung Liu
We consider the \emph{approximate minimum selection} problem in presence of \emph{independent random comparison faults}. This problem asks to select one of the smallest element…
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 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…