This paper draws a connection between GNNs and the communication complexity theory, and derived some interesting results regarding the GNN size and its capability of solving certain classes of problems, on certain input data distributions. Given that this paper brings in communication complexity theory into the study of GNNs, which is mostly new to our reviewers, it is a quite demanding paper to thoroughly review, and the reviewer confidence is low because of the lack of context / time to check every claim. The AC carefully checked the proofs of all the major claims and believes that the paper is correct, and the techniques developed in this paper can potentially bring useful insights to the community and have broader impact. However the review process did show that the author should do a better job of making this paper more accessible to the machine learning community, by e.g. improving the clarity of various definitions that set up the theory (the definition of the communication protocol is particularly confusing, even though it is almost copied from [38]), and explaining the intuitive proof strategy of the main results.