Property Testing for Independent Sets Suppose we're given a graph $G$ and parameters $k,\epsilon$. Are there ranges of values for $k$ (or is it doable for all $k$) for which it is possible to test whether $G$ is $\epsilon$-far from having an independent set of size at least $k$ in time $O(n + \text{poly}(1/\epsilon))$ ? 

If we use the usual notion of $\epsilon$-far (i.e at most $\epsilon n^2$ edges would need to be changed in order to obtain such a set), then the problem is trivial for $k = O(n\sqrt{\epsilon})$.  So


It seems that if $k$ is larger, some sampling ideas should work to solve the problem. Is that true ? 
Are there other notions of $\epsilon$-far (i.e maybe $\epsilon |E|$ edges instead) under which there are nontrivial results ? 


I'm basically looking for references at this point.
This problem has indeed been studied.  Goldreich, Goldwasser and Ron studied it in their seminal paper which kicked off graph property testing, and then, Feige, Langberg, and Schechtman also have results on it in their FOCS '02 paper "Graphs with tiny vector chromatic numbers and huge chromatic numbers".

Specifically, [FLS '02] show that one can distinguish between graphs with an independent set of size $\rho n$ from graphs $\epsilon$-far from being so (meaning, at least $\epsilon n^2$ edges need to be removed to create such an independent set) by choosing a random subgraph induced by $s = \tilde{O}(\rho^4/\epsilon^3)$ random vertices in the graph and checking whether the random subgraph has an independent set of size $\rho s$ or not.   ([GGR '98] showed a weaker bound on $s$ of $\tilde{O}(\rho/\epsilon^4)$.)  [FLS '02] also show a lower bound on $s$ of $\Omega(\rho^3/\epsilon^2)$.