Before revision:  edges, where \epsilon = \Theta   1 / t^2  . Our main result is that any O( \text{poly (n))-time algorithm must send at least \tilde\Omega  n ^{1+ 1 / 2t }   bits in the CONGEST model under the KT1 assumption , where each node has knowledge of its neighbors' IDs initially . Previously, only a trivial lower bound of \tilde \Omega(n) bits was known for this problem ; in fact, our result is the first nontrivial lower bound on the communication complexity of a sparse subgraph problem under the KT1 assumption .
After revision:  edges, where \epsilon = \Theta  1 / t^2 . Our main result is that any O( \text{poly (n))-time algorithm must send at least \tilde\Omega  n ^{1+ 1 / 2t }  bits in the CONGEST model under the KT1 assumption , where each node has knowledge of its neighbors' IDs initially . Previously, only a trivial lower bound of \tilde \Omega(n) bits was known for this problem .