8 citations · 21 across the 23 of their papers we have counts for
4 papers · 1 filter
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…