8 citations · 21 across the 23 of their papers we have counts for
27 papers
Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
Cheng Jiang, Yinchen Liu, Huacheng Yu
A fundamental question in streaming complexity is whether every space-efficient turnstile algorithm is implicitly a linear sketch. The landmark work of Li, Nguyen, and Woodruff [LN…
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions
Huacheng Yu, Wei Zhan
We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the…
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
Tianxiao Li, Jingxun Liang, Huacheng Yu +1
A dictionary data structure maintains a set of at most keys from the universe under key insertions and deletions, such that given a query , it returns if i…
Super-Logarithmic Lower Bounds for Dynamic Graph Problems
Kasper Green Larsen, Huacheng Yu
In this work, we prove a unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability quer…
Detecting TCP Packet Reordering in the Data Plane
Yufei Zheng, Huacheng Yu, Jennifer Rexford
Network administrators want to detect TCP-level packet reordering to diagnose performance problems and attacks. However, reordering is expensive to measure, because each packet mus…
On the amortized complexity of approximate counting
Ishaq Aden-Ali, Yanjun Han, Jelani Nelson +1
Naively storing a counter up to value would require bits of memory. Nelson and Yu [NY22], following work of [Morris78], showed that if the query answers need only b…
On Constructing Spanners from Random Gaussian Projections
Sepehr Assadi, Michael Kapralov, Huacheng Yu
Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applicati…
Strong XOR Lemma for Communication with Bounded Rounds
Huacheng Yu
In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function , the -fold X…
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
Lijie Chen, Gillat Kol, Dmitry Paramonov +3
For a directed graph with vertices and a start vertex , we wish to (approximately) sample an -step random walk over starting from with…
Optimal bounds for approximate counting
Jelani Nelson, Huacheng Yu
Storing a counter incremented times would naively consume bits of memory. In 1978 Morris described the very first streaming algorithm: the "Morris Counter". His alg…
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena +1
Consider the following gap cycle counting problem in the streaming model: The edges of a -regular -vertex graph are arriving one-by-one in a stream and we are promised th…
Tight Distributed Sketching Lower Bound for Connectivity
Huacheng Yu
In this paper, we study the distributed sketching complexity of connectivity. In distributed graph sketching, an -node graph is distributed to players such that each pla…
Succinct Filters for Sets of Unknown Sizes
Mingmou Liu, Yitong Yin, Huacheng Yu
The membership problem asks to maintain a set , supporting insertions and membership queries, i.e., testing if a given element is in the set. A data structure that c…
Lower Bound for Succinct Range Minimum Query
Mingmou Liu, Huacheng Yu
Given an integer array , the Range Minimum Query problem (RMQ) asks to preprocess into a data structure, supporting RMQ queries: given , return the index…
Faster Update Time for Turnstile Streaming Algorithms
Josh Alman, Huacheng Yu
In this paper, we present a new algorithm for maintaining linear sketches in turnstile streams with faster update time. As an application, we show that \texttt{Count} sket…
Nearly Optimal Static Las Vegas Succinct Dictionary
Huacheng Yu
Given a set of (distinct) keys from key space , each associated with a value from , the \emph{static dictionary} problem asks to preprocess these (key, value) pairs…
How to Store a Random Walk
Emanuele Viola, Omri Weinstein, Huacheng Yu
Motivated by storage applications, we study the following data structure problem: An encoder wishes to store a collection of jointly-distributed files $\overline{X}:=(X_1,X_2,\ldot…
Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
Huacheng Yu
Given an -bit array , the succinct rank data structure problem asks to construct a data structure using space bits for , supporting rank queries of form $\matht…
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
Jelani Nelson, Huacheng Yu
We show optimal lower bounds for spanning forest computation in two different models: * One wants a data structure for fully dynamic spanning forest in which updates can insert or…
Pruning based Distance Sketches with Provable Guarantees on Random Graphs
Hongyang Zhang, Huacheng Yu, Ashish Goel
Measuring the distances between vertices on graphs is one of the most fundamental components in network analysis. Since finding shortest paths requires traversing the graph, it is…
Fillable arrays with constant time operations and a single bit of redundancy
Jacob Teo Por Loong, Jelani Nelson, Huacheng Yu
In the fillable array problem one must maintain an array A[1..n] of -bit entries subject to random access reads and writes, and also a operation which sets ev…
Cell-Probe Lower Bounds from Online Communication Complexity
Josh Alman, Joshua R. Wang, Huacheng Yu
In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the player…
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in d…
DecreaseKeys are Expensive for External Memory Priority Queues
Kasper Eenberg, Kasper Green Larsen, Huacheng Yu
One of the biggest open problems in external memory data structures is the priority queue problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be s…