Lower Bounds for Graph Stream Algorithms Through the Boolean Hidden Matching Problem

Abstract

Space lower bounds for streaming algorithms are frequently proven through reductions from communication complexity problems. We study reductions from a specific communication problem, Boolean Hidden Matching (BHM), to various graph streaming algorithms. Variants of BHM have been shown to reduce to (and give the current best lower bounds for) triangle counting, maxcut approximation, and maximum matching approximation. Though the graph problems are seemingly dissimilar, the communication problems they reduce from are all based on BHM, and moreover all have lower bounds established through Fourier analysis. This thesis examines why such a communication problem is successful in capturing the hardness of these graph problems. We review the original proof of the lower bound for BHM and discuss the aspects which likely motivated using Fourier analysis. Next, we review three BHM variants and the graph problems they reduce to. From this, we identify characteristics of graph problems that suggest reduction from BHM to be a good candidate for capturing the hardness of the graph problem. Then, we consider the problem of counting connected components in regular bipartite graphs, and we establish a streaming lower bound through reducing from BHM. Finally, we adapt a variant of BHM for the same problem which we show gives a stronger bound for a specific subclass of streaming algorithms.