Lower Bounds for Approximating Graph Parameters via Communication Complexity
share
We present a new framework for proving query complexity lower bounds for graph problems via reductions from communication complexity. We illustrate our technique by giving new proofs of tight lower bounds for several graph problems: estimating the number of edges in a graph, sampling edges from an almost-uniform distribution, estimating the number of k-cliques in a graph, and estimating the moments of the degree distribution of a graph.
READ FULL TEXT