Two-Prover-One-Round Game (2P1R) and the hardness of approximating
connectivity problems. Based on the recent development on 2P1R by Chan
(STOC 2013), we improve hardness of connectivity problems that are in
the form k^delta, for some small constant delta>0, to hardness of the
form k^c for some explicit constant c, where k is a connectivity
parameter. Moreover, we prove hardness in terms of the number of
demand pairs for the target problems. This improves upon the known
hardness results of the rooted k-connectivity, vertex-connectivity
survivable network design and vertex-connectivity k-route-cut
problems.