5 papers · 1 filter
Combinatorial Boolean Matrix Multiplication in Time
Piaoyang Cui, Yiming Liu, David P. Woodruff
For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abbo…
A Nearly Optimal Min-Cut Algorithm for Dynamic Streams
Yang P. Liu, Hoai-An Nguyen, Vihan Shah +1
We give an -space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic fact…
Streaming Complexity Separations for Dense and Sparse Graphs
Yang P. Liu, Hoai-An Nguyen, Noah G. Singer +1
We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dens…
Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
Alina Ene, Alessandro Epasto, Vahab Mirrokni +4
In the maximum coverage problem we are given subsets from a universe , and the goal is to output subsets such that their union covers the largest possible number of di…
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions
Justin Y. Chen, Piotr Indyk, David P. Woodruff
We revisit the problem of estimating the profile (also known as the rarity) in the data stream model. Given a sequence of elements from a universe of size , its profile is a…