We obtain restriction estimates of ε -removal type for the set of k-th powers of integers, and for discrete d-dimensional surfaces of the form { ( n 1 , ⋯ , n d , n 1 k + ⋯ + n d k ) : | n 1 | , ⋯ , | n d | ⩽ N } , which we term 'k-paraboloids'. For these surfaces, we obtain a satisfying range of exponents for large values of d, k. We also obtain estimates of ε -removal type in the full supercritical range for k-th powers and for k-paraboloids of dimension d < k ( k - 2 ) . We rely on a variety of techniques in discrete harmonic analysis originating in Bourgain's works on the restriction theory of the squares and the discrete parabola.