6 citations · 10 across the 7 of their papers we have counts for
12 papers
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…
Optimal Planar Nearest Neighbors Queries for Additively Weighted Euclidean Distances and Convex Metrics
Chih-Hung Liu
Given a set of point sites in the plane, the nearest neighbors problem is to build a data structure that, for a query point and a query integer , reports the …
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…
Fast algorithm for overcomplete order-3 tensor decomposition
Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu +2
We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to . Our algorithm only involves…
Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser +3
We develop machinery to design efficiently computable and consistent estimators, achieving estimation error approaching zero as the number of observations grows, when facing an obl…
Simple Topological Drawings of -Planar Graphs
Michael Hoffmann, Chih-Hung Liu, Meghana M. Reddy +1
Every finite graph admits a \emph{simple (topological) drawing}, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other re…
Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
Chih-Hung Liu
We study the k nearest neighbors problem in the plane for general, convex, pairwise disjoint sites of constant description complexity such as line segments, disks, and quadrilatera…
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…
A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram in a Simple Polygon
Chih-Hung Liu
The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell s…
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…
Higher Order City Voronoi Diagrams
Andreas Gemsa, D. T. Lee, Chih-Hung Liu +1
We investigate higher-order Voronoi diagrams in the city metric. This metric is induced by quickest paths in the L1 metric in the presence of an accelerating transportation network…