Waring's problem (previously asked about <a href="http://mathoverflow.net/questions/437/sums-of-cubes-and-more">here</a>) asks, for each integer $k \ge 2$, what is the smallest integer $g(k)$ such that any positive integer can be written as a sum of $g(k)$ kth powers.  We have $g(2) = 4$, $g(3) = 9$, etc.  A (harder) variant asks what the smallest integer $G(k)$ is such that all <i>sufficiently large</i> integers can be written as a sum of $G(k)$ kth powers.  

I have two related questions:

1. What is known if we relax the condition ``any positive integer'' and only require a <i>positive-density subset</i>?  More precisely, we look for the smallest $g'(k)$ for which there is some $S \subset \mathbb{Z}_{>0}$ of positive density such that any $x \in S$ can be written as $g'(k)$ $k$th powers.  Then we have $g'(2) = 3$, while $G(2) = 4$; and $g'(3) = 4$, while it is only known that $4 \le G(3) \le 7$.  Is anything known about $g'(k)$ for k = 4,5, or larger?

2. For fixed k, is there an efficient algorithm that, given n, writes n as a sum of $g(k)$ kth powers?  What about decomposing n into the minimal number of kth powers for that n?   (Here `efficient' means polynomial in log(n).)  

Edit: Wikipedia says that ``In the absence of congruence restrictions, a density argument suggests that G(k) should equal k + 1.''  So perhaps this is the answer to (1)?