10 citations · 20 across the 13 of their papers we have counts for
21 papers
Scalable Auction Algorithms for Bipartite Maximum Matching Problems
Quanquan C. Liu, Yiduo Ke, Samir Khuller
In this paper, we give new auction algorithms for maximum weighted bipartite matching (MWM) and maximum cardinality bipartite -matching (MCbM). Our algorithms run in $O\left(\lo…
The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations
Quanquan C. Liu, Vaidehi Srinivas
We formulate the predicted-updates dynamic model, one of the first beyond-worst-case models for dynamic algorithms, which generalizes a large set of well-studied dynamic models inc…
Triangle Counting with Local Edge Differential Privacy
Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova +1
Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study tri…
An Algorithmic Approach to Address Course Enrollment Challenges
Arpita Biswas, Yiduo Ke, Samir Khuller +1
Massive surges of enrollments in courses have led to a crisis in several computer science departments - not only is the demand for certain courses extremely high from majors, but t…
A Note on Improved Results for One Round Distributed Clique Listing
Quanquan C. Liu
In this note, we investigate listing cliques of arbitrary sizes in bandwidth-limited, dynamic networks. The problem of detecting and listing triangles and cliques was originally st…
Differential Privacy from Locally Adjustable Graph Algorithms: -Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova +3
Differentially private algorithms allow large-scale data analytics while preserving user privacy. Designing such algorithms for graph data is gaining importance with the growth of…
Active Learning for Contextual Search with Binary Feedbacks
Xi Chen, Quanquan Liu, Yining Wang
In this paper, we study the learning problem in contextual search, which is motivated by applications such as first-price auction, personalized medicine experiments, and feature-ba…
The Power of Random Symmetry-Breaking in Nakamoto Consensus
Lili Su, Quanquan C. Liu, Neha Narula
Nakamoto consensus underlies the security of many of the world's largest cryptocurrencies, such as Bitcoin and Ethereum. Common lore is that Nakamoto consensus only achieves consis…
Scheduling with Communication Delay in Near-Linear Time
Quanquan C. Liu, Manish Purohit, Zoya Svitkina +2
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-…
Parallel Batch-Dynamic Algorithms for -Core Decomposition and Related Graph Problems
Quanquan C. Liu, Jessica Shi, Shangdi Yu +2
Maintaining a -core decomposition quickly in a dynamic graph has important applications in network analysis. The main challenge for designing efficient exact algorithms is that…
Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry-Breaking Problems
Shiri Antaki, Quanquan C. Liu, Shay Solomon
The field of dynamic graph algorithms aims at achieving a thorough understanding of real-world networks whose topology evolves with time. Traditionally, the focus has been on the c…
A Lower Bound for Byzantine Agreement and Consensus for Adaptive Adversaries using VDFs
Thaddeus Dryja, Quanquan C. Liu, Neha Narula
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 binar…
Parallel Batch-Dynamic -Clique Counting
Laxman Dhulipala, Quanquan C. Liu, Julian Shun +1
In this paper, we study new batch-dynamic algorithms for the -clique counting problem, which are dynamic algorithms where the updates are batches of edge insertions and deletion…
Tatamibari is NP-complete
Aviv Adler, Jeffrey Bosboom, Erik D. Demaine +3
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition…
Massively Parallel Algorithms for Small Subgraph Counting
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu +2
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 p…
Fully Dynamic -Coloring in Constant Update Time
Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni +2
The problem of (vertex) -coloring a graph of maximum degree has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic…
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster +5
We develop a new framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a sce…
Static-Memory-Hard Functions and Nonlinear Space-Time Tradeoffs via Pebbling
Thaddeus Dryja, Quanquan C. Liu, Sunoo Park
Pebble games were originally formulated to study time-space tradeoffs in computation, modeled by games played on directed acyclic graphs (DAGs). Close connections between pebbling…
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu +2
This paper initiates the study of I/O algorithms (minimizing cache misses) from the perspective of fine-grained complexity (conditional polynomial lower bounds). Specifically, we a…
Upward Partitioned Book Embeddings
Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg +1
We analyze a directed variation of the book embedding problem when the page partition is prespecified and the nodes on the spine must be in topological order (upward book embedding…
Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs
Erik D. Demaine, Quanquan C. Liu
Pebble games are single-player games on DAGs involving placing and moving pebbles on nodes of the graph according to a certain set of rules. The goal is to pebble a set of target n…