Thanks! I'll have to remember to add a link from this post to the paper once it's out. For your construction in part 1, would it not have worked equally well to take $P(x) = \prod_{k\le N^{1/3}} (1-kx)$?

On further thought, I think I can get a modest improvement to my complexity lower bound already from this. fedja, would you like to be added as a coauthor of a quantum algorithms paper, with me doing almost all the work, or would you prefer just a prominent acknowledgment? Shoot me an email at [email protected] if you'd like to discuss.

I'd like to add a note to a paper to the effect, "while it's not automatic, it seems likely that the degree lower bound from this MO post could be used to improve this complexity lower bound from $\Omega(N^{1/4})$ to $\Omega(N^{1/3})$, closer to the upper bound of $O(\sqrt{N})$." If I do so, should I acknowledge you as "fedja" or should I use a full name? Thanks!

This is awesome!! I also had the idea of multiplying a Chebyshev polynomial on $[0,N^{-1/3}]$ by a polynomial of degree ~$N^{1/3}$ that would simply zero out the remaining points, but I didn't see why doing so would preserve boundedness.