  We study implications of theories with sub-millimeter extra dimensions and
$M_f \sim (1 - 10) $ TeV scale quantum gravity for neutrino physics. In these
theories, the left-handed neutrinos as well as other standard model (SM)
particles, are localized on a brane embedded in the bulk of large extra space.
Mixing of neutrinos with (SM) singlet fermions propagating in the bulk is
naturally suppressed by the volume factor $M_f/M_P \sim 3\cdot 10^{-16} -
3\cdot 10^{-15}$, where $M_P$ is the Planck mass. Properties of the neutrino
oscillations and the resonance conversion to the bulk fermions are considered.
We show that the resonance conversion of the electron neutrinos to the light
bulk fermions can solve the solar neutrino problem. The signature of the
solution is the peculiar distortion of the solar neutrino spectrum. The
solution implies that the radius of at least one extra dimension should be in
the range 0.06 - 0.1 mm {\it irrespective} of total number of extra dimensions.
The corresponding modification of the Newtonian law is within the range of
sensitivity of proposed sub-millimeter experiments, thus providing a verifiable
link between neutrino physics and the gravity measurements.
