Sparsity is a powerful structural resource in optimization and statistics. We develop frameworks for leveraging sparsity in sampling problems over the Hamming slice
Xkd:={x∈{±1}d:∣{i:xi=1}∣=k}, in high-dimensional regimes where
k≪d (i.e., where
Xkd is \emph{highly magnetized}). We use our frameworks to design improved samplers for canonical problems in the study of \emph{Ising models} and \emph{Bayesian sparse linear regression}. Our first main result considers the \emph{Sherrington--Kirkpatrick} (SK) model restricted to fixed-magnetization slices
Xkd. We give a polynomial-time sampler for fixed-magnetization SK models at any inverse temperature
β>0, under arbitrary external fields, provided that
k≤cβd for an appropriate constant
cβ. By combining this result with an annealing strategy for estimating normalizing constants, we obtain polynomial-time samplers for the SK model at arbitrarily low temperatures under a sufficiently strong external field of strength
h. In the large-
β limit, our framework permits sampling at field strengths within constant factors of the \emph{Almeida--Thouless line} delineating the replica-symmetric and replica-symmetry-breaking regions ([dAT78]), improving polynomially over the field strength
h(β) required by the recent work of [BAR26]. Our second main result concerns the measurement complexity of polynomial-time Bayesian sparse linear regression. Recent work by [KSTZ25] shows how to sample from the canonical \emph{Gaussian spike-and-slab posterior} with expected sparsity
k, at any signal-to-noise ratio, given
n≳k3log3d Gaussian measurements. We improve this requirement to
n≳k3/2log2d+klog3d, using a common sparsity-aware framework underlying both our results.