Source author record

Quanquan C. 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 Distributed, Parallel, and Cluster Computing Computational Complexity Computational Geometry

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Massively Parallel Algorithms for Small Subgraph Counting

Over the last two decades, frameworks for distributed-memory parallel computation, such as MapReduce, Hadoop, Spark and Dryad, have gained significant popularity with the growing prevalence of large network datasets. The Massively Parallel Computation (MPC) model is the de-facto standard for studying graph algorithms in these frameworks theoretically. Subgraph counting is one such fundamental problem in analyzing massive graphs, with the main algorithmic challenges centering on designing methods which are both scalable and accurate. Given a graph $G=(V, E)$ with $n$ vertices, $m$ edges and $T$ triangles, our first result is an algorithm that outputs a $(1+\varepsilon)$ -approximation to $T$ , with asymptotically \emph{optimal round and total space complexity} provided any $S \geq \max{(\sqrt m, n^2/m)}$ space per machine and assuming $T=Ω(\sqrt{m/n})$ . Our result gives a quadratic improvement on the bound on $T$ over previous works. We also provide a simple extension of our result to counting \emph{any} subgraph of $k$ size for constant $k \geq 1$ . Our second result is an $O_{\varepsilon}(\log \log n)$ -round algorithm for exactly counting the number of triangles, whose total space usage is parametrized by the \emph{arboricity} $α$ of the input graph. We extend this result to exactly counting $k$ -cliques for any constant $k$ . Finally, we prove that a recent result of Bera, Pashanasangi and Seshadhri (ITCS 2020) for exactly counting all subgraphs of size at most $5$ can be implemented in the MPC model in total space.

preprint2022arXiv

Scheduling with Communication Delay in Near-Linear Time

We consider the problem of efficiently scheduling jobs with precedence constraints on a set of identical machines in the presence of a uniform communication delay. Such precedence-constrained jobs can be modeled as a directed acyclic graph, $G = (V, E)$ . In this setting, if two precedence-constrained jobs $u$ and $v$ , with $v$ dependent on $u$ ( $u \prec v$ ), are scheduled on different machines, then $v$ must start at least $ρ$ time units after $u$ completes. The scheduling objective is to minimize makespan, i.e. the total time from when the first job starts to when the last job finishes. The focus of this paper is to provide an efficient approximation algorithm with near-linear running time. We build on the algorithm of Lepere and Rapine [STACS 2002] for this problem to give an $O\left(\frac{\ln ρ}{\ln \ln ρ} \right)$ -approximation algorithm that runs in $\tilde{O}(|V| + |E|)$ time.

preprint2020arXiv

A Lower Bound for Byzantine Agreement and Consensus for Adaptive Adversaries using VDFs

Large scale cryptocurrencies require the participation of millions of participants and support economic activity of billions of dollars, which has led to new lines of work in binary Byzantine Agreement (BBA) and consensus. The new work aims to achieve communication-efficiency---given such a large $n$ , not everyone can speak during the protocol. Several protocols have achieved consensus with communication-efficiency, even under an adaptive adversary, but they require additional strong assumptions---proof-of-work, memory-erasure, etc. All of these protocols use multicast: every honest replica multicasts messages to all other replicas. Under this model, we provide a new communication-efficient consensus protocol using Verifiable Delay Functions (VDFs) that is secure against adaptive adversaries and does not require the same strong assumptions present in other protocols. A natural question is whether we can extend the synchronous protocols to the partially synchronous setting---in this work, we show that using multicast, we cannot. Furthermore, we cannot achieve always safe communication-efficient protocols (that maintain safety with probability 1) even in the synchronous setting against a static adversary when honest replicas only choose to multicast its messages. Considering these impossibility results, we describe a new communication-efficient BBA protocol in a modified partially synchronous network model which is secure against adaptive adversaries with high probability.

preprint2020arXiv

Tatamibari is NP-complete

In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an $m \times n$ grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing + are square, rectangles containing - are strictly longer horizontally than vertically, rectangles containing | are strictly longer vertically than horizontally, and no four rectangles share a corner. We prove this puzzle NP-complete, establishing a Nikoli gap of 16 years. Along the way, we introduce a gadget framework for proving hardness of similar puzzles involving area coverage, and show that it applies to an existing NP-hardness proof for Spiral Galaxies. We also present a mathematical puzzle font for Tatamibari.

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.