Source author record

Chih-Hung Liu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry Discrete Mathematics Machine Learning math.CO

Catalog footprint

Research overview

5works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Given $n$ elements, an integer $k$ and a parameter $\varepsilon$ , we study to select an element with rank in $(k-n\varepsilon,k+n\varepsilon]$ using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant error probability, and multiple comparisons between the same pair of elements are independent. In this fault model, the fundamental problems of finding the minimum, selecting the $k$ -th smallest element and sorting have been shown to require $Θ\big(n \log \frac{1}{Q}\big)$ , $Θ\big(n\log \frac{\min\{k,n-k\}}{Q}\big)$ and $Θ\big(n\log \frac{n}{Q}\big)$ comparisons, respectively, to achieve success probability $1-Q$ . Recently, Leucci and Liu proved that the approximate minimum selection problem ( $k=0$ ) requires expected $Θ(\varepsilon^{-1}\log \frac{1}{Q})$ comparisons. We develop a randomized algorithm that performs expected $O(\frac{k}{n}\varepsilon^{-2} \log \frac{1}{Q})$ comparisons to achieve success probability at least $1-Q$ . We also prove that any randomized algorithm with success probability at least $1-Q$ performs expected $Ω(\frac{k}{n}\varepsilon^{-2}\log \frac{1}{Q})$ comparisons. Our results indicate a clear distinction between approximating the minimum and approximating the $k$ -th smallest element, which holds even for the high probability guarantee, e.g., if $k=\frac{n}{2}$ and $Q=\frac{1}{n}$ , $Θ(\varepsilon^{-1}\log n)$ versus $Θ(\varepsilon^{-2}\log n)$ . Moreover, if $\varepsilon=n^{-α}$ for $α\in (0,\frac{1}{2})$ , the asymptotic difference is almost quadratic, i.e., $\tildeΘ(n^α)$ versus $\tildeΘ(n^{2α})$ .

preprint2022arXiv

Fast algorithm for overcomplete order-3 tensor decomposition

We develop the first fast spectral algorithm to decompose a random third-order tensor over $\mathbb{R}^d$ of rank up to $O(d^{3/2}/\text{polylog}(d))$ . Our algorithm only involves simple linear algebra operations and can recover all components in time $O(d^{6.05})$ under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most $O(d^{4/3}/\text{polylog}(d))$ . Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm.

preprint2020arXiv

Approximate Minimum Selection with Unreliable Comparisons in Optimal Expected Time

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 $k$ elements in a linearly-ordered collection of $n$ elements by only performing \emph{unreliable} pairwise comparisons: whenever two elements are compared, there is a constant probability that the wrong answer is returned. We design a randomized algorithm that solves this problem with probability $1-q \in [ \frac{1}{2}, 1)$ and for the whole range of values of $k$ using $O( \frac{n}{k} \log \frac{1}{q} )$ expected time. Then, we prove that the expected running time of any algorithm that succeeds w.h.p. must be $Ω(\frac{n}{k}\log \frac{1}{q})$ , thus implying that our algorithm is asymptotically optimal, in expectation. These results are quite surprising in the sense that for $k$ between $Ω(\log \frac{1}{q})$ and $c \cdot n$ , for any constant $c<1$ , the expected running time must still be $Ω(\frac{n}{k}\log \frac{1}{q})$ even in absence of comparison faults. Informally speaking, we show how to deal with comparison errors without any substantial complexity penalty w.r.t.\ the fault-free case. Moreover, we prove that as soon as $k = O( \frac{n}{\log\log \frac{1}{q}})$ , it is possible to achieve the optimal \emph{worst-case} running time of $Θ(\frac{n}{k}\log \frac{1}{q})$ .

preprint2020arXiv

Simple Topological Drawings of $k$ -Planar Graphs

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 restrictions simple drawings do not universally exist. For instance, \emph{ $k$ -planar graphs} are those graphs that can be drawn so that every edge has at most $k$ crossings (i.e., they admit a \emph{ $k$ -plane drawing}). It is known that for $k\le 3$ , every $k$ -planar graph admits a $k$ -plane simple drawing. But for $k\ge 4$ , there exist $k$ -planar graphs that do not admit a $k$ -plane simple drawing. Answering a question by Schaefer, we show that there exists a function $f : \mathbb{N}\rightarrow\mathbb{N}$ such that every $k$ -planar graph admits an $f(k)$ -plane simple drawing, for all $k\in\mathbb{N}$ . Note that the function $f$ depends on $k$ only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every $4$ -planar graph admits an $8$ -plane simple drawing.

preprint2012arXiv

Higher Order City Voronoi Diagrams

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 of axis-parallel line segments. For the structural complexity of kth-order city Voronoi diagrams of n point sites, we show an upper bound of O(k(n - k) + kc) and a lower bound of Ω(n + kc), where c is the complexity of the transportation network. This is quite different from the bound O(k(n - k)) in the Euclidean metric. For the special case where k = n - 1 the complexity in the Euclidean metric is O(n), while that in the city metric is Θ(nc). Furthermore, we develop an O(k^2(n + c) log n)-time iterative algorithm to compute the kth-order city Voronoi diagram and an O(nc log^2(n + c) log n)-time divide-and-conquer algorithm to compute the farthest-site city Voronoi diagram.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Chih-Hung Liu

Research overview

Is this your work?

5 publications

Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Fast algorithm for overcomplete order-3 tensor decomposition

Approximate Minimum Selection with Unreliable Comparisons in Optimal Expected Time

Simple Topological Drawings of $k$ -Planar Graphs

Higher Order City Voronoi Diagrams

See the researcher in context

Building this map preview

Chih-Hung Liu

Research overview

Is this your work?

5 publications

Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Fast algorithm for overcomplete order-3 tensor decomposition

Approximate Minimum Selection with Unreliable Comparisons in Optimal Expected Time

Simple Topological Drawings of kkk-Planar Graphs

Higher Order City Voronoi Diagrams

See the researcher in context

Building this map preview

Simple Topological Drawings of $k$ -Planar Graphs