We describe a new method for creating spin-dependent long-range interactions between atomic ultra-cold neutral bosons-specifically Rb-87-in an optical lattice. In this proposal, the bosonic system is immersed in a spin-polarized degenerate Fermi gas (almost perfectly non-interacting), here Li-6. We first show that the bosons acquire a long-range interaction analogous to Ruderman-Kittel-Kasuya-Yosida interaction in solids. The resulting fermion-mediated Bose-Bose interaction, which can depend on the bosons spin state, is tunable using inter-species Feshbach resonance. When the bosons are subject to a suitable optical lattice, 3-body loss processes are greatly suppressed. We conclude by showing that these interactions can lead to a supersolid phase for single-spin Bose system, and also to a fully tunable transverse field Ising model for a two-component Bose system.