In subsec:aloceBob we present the Alice-Bob lower bound framework developed in [1]} that we use to obtain quadratic and near-quadratic lower bounds for \(G^2\) -MVC and \(G^2\) -MDS (Section ). Then, in Sections REF  and REF  we use the framework to prove near-quadratic lower bounds for \(G^2\) -MWVC and \(G^2\) -MVC. In sec:VC-apx-limitations we show limitations of the framework and in sec:VChardness we show our conditional lower bound for \(G^2\) -MVC.
