It is generally believed that superconductivity only weakly affects the indirect exchange between magnetic impurities. If the distance r between impurities is smaller than the superconducting coherence length (r less than or similar to xi), this exchange is thought to be dominated by Ruderman-Kittel-Kasuya-Yosida (RKKY) interactions, identical to the those in a normal metallic host. This perception is based on a perturbative treatment of the exchange interaction. Here, we provide a nonperturbative analysis and demonstrate that the presence of Yu-Shiba-Rusinov bound states induces a strong 1/r(2) antiferromagnetic interaction that can dominate over conventional RKKY even at distances significantly smaller than the coherence length (r << xi). Experimental signatures, implications, and applications are discussed.