Matching Size and Matrix Rank Estimation in Data Streams

How well a sub-linear space algorithm can estimate the size of a largest matching in a graph or the rank of a given matrix, if the input is revealed in a streaming fashion? In this talk, we consider this question from both upper bound and lower bound ends and establish new results on the tradeoff between the space requirement and desired accuracy of streaming algorithms for these tasks.

We show that while the problem of matching size estimation is provably easier than the problem of finding an approximate matching (i.e., finding the actual edges of the matching), the space complexity of the two problems starts to converge together as the accuracy desired in the computation approaches near-optimality. A well-known connection between matching size estimation and computing rank of Tutte matrices allows us to further carry our lower bound results to the matrix rank estimation problem, and we show that an almost quadratic space is necessary to obtain a near-optimal approximation of matrix rank in data streams.

Based on a joint work with Sanjeev Khanna and Yang Li (in SODA’17, invited to HALG’17).