We develop a new technique for constructing small-cut graphs that allow us to prove near-linear lower bounds for computing distances, and near-quadratic lower bounds for optimization problems in the CONGEST model. In this talk I will present the technique, and show a near-linear lower bound for computing a (3/2-\epsilon)-approximation for the diameter, and a near-quadratic lower bound for computing minimum vertex cover or maximum independent set.
Based on joint works with Amir Abboud, Keren Censor-Hillel, and Ami Paz.