Randomized experiments on a network often involve interference between connected units; i.e., a situation in which an individual's treatment can affect the response of another individual. Current approaches to deal with interference, in theory and in practice, often make restrictive assumptions on its structure---for instance, assuming that interference is local---even when using otherwise nonparametric inference strategies. This reliance on explicit restrictions on the interference mechanism suggests a shared intuition that inference is impossible without any assumptions on the interference structure. In this paper, we begin by formalizing this intuition in the context of a classical nonparametric approach to inference, referred to as design-based inference of causal effects. Next, we show how, always in the context of design-based inference, even parametric structural assumptions that allow the existence of unbiased estimators, cannot guarantee a decreasing variance even in the large sample limit. Our results suggest that much of the intuition from the no-interference case do not easily transfer to the interference setting.