Lower Bounds for Approximating Graph Parameters via Communication Complexity

Understand

In a celebrated work, Blais, Brody, and Matulef developed a technique for proving property testing lower bounds via reductions from communication complexity.

• Their work focused on testing properties of functions, and yielded new lower bounds as well as simplified analyses of known lower bounds.
• Here, we take a further step in generalizing the methodology of Blais et al.
• to analyze the query complexity of graph parameter estimation problems.