Timeline for Real polynomial bounded at inverse-integer points
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 7, 2018 at 19:10 | comment | added | fedja | @ScottAaronson It would. I just wanted to make it a bit flatter but in this particular case it is not really necessary, indeed. | |
| Jun 7, 2018 at 14:35 | comment | added | Scott Aaronson | 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)$? | |
| Jun 7, 2018 at 13:04 | comment | added | fedja | @ScottAaronson Mentioning MO is more than sufficient as far as I am concerned, but I'm glad my 2 cents helped :-) | |
| Jun 7, 2018 at 8:30 | comment | added | Scott Aaronson | 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. | |
| Jun 7, 2018 at 4:49 | comment | added | Scott Aaronson | 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! | |
| Jun 7, 2018 at 4:46 | comment | added | Scott Aaronson | 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. | |
| Jun 7, 2018 at 3:27 | vote | accept | Scott Aaronson | ||
| Jun 7, 2018 at 2:46 | comment | added | Christian Remling | I love your line "One thing that is written in every decent textbook ...," when, obviously, this is the first time this piece of wisdom has been shared in print. | |
| Jun 7, 2018 at 2:36 | history | edited | David E Speyer | CC BY-SA 4.0 |
fixed typo in equation after "You just write".
|
| S Jun 7, 2018 at 0:11 | history | edited | fedja | CC BY-SA 4.0 |
added 2187 characters in body
|
| Jun 6, 2018 at 23:14 | review | Suggested edits | |||
| S Jun 7, 2018 at 0:11 | |||||
| Jun 6, 2018 at 21:48 | history | edited | fedja | CC BY-SA 4.0 |
added 1857 characters in body
|
| Jun 6, 2018 at 19:05 | history | answered | fedja | CC BY-SA 4.0 |