2021.12.10 16:34:42 (1469329735167913987) from Daniel J. Bernstein, replying to "Sam Jaques (@sejaques)" (1469271990989213698):
Sent email early Nov with a simpler question; didn't hear back. Mail filtering? Senior author (who used to work for NSA) getting approval to reply? Busy with new paper version? Eventually tweeted that question (https://twitter.com/hashbreaker/status/1459198701826547713). Decided to tweet the nesting question too.
2021.11.12 17:37:35 (1459198701826547713) from Daniel J. Bernstein:
Skeptical about Corollary 7 of https://arxiv.org/abs/2110.13352. Doesn't Theorem 6 need to assume that gamma is bounded away from 1, which in turn needs N to have a higher exponent? Might still beat other approaches but needs more careful analysis of the run time, heuristic accuracy, etc.
2021.12.10 11:31:06 (1469253334418997256) from Daniel J. Bernstein:
Looking a bit more at https://arxiv.org/abs/2110.13352, and now skeptical about Theorem 6 (never mind the application to Corollary 7). The last proof step says 2^t amplifications each costing sqrt(N), but aren't half of these nested amplifications? How are further sqrt(N) factors avoided?
2021.12.10 12:45:15 (1469271990989213698) from "Sam Jaques (@sejaques)":
I had the same thought: "build_superposition" is acting as the diffusion operator of the amplitude amplification, and thus must be repeated in each subsequent A.A. (so total cost is at least O(sqrt(N)^t), more when counting the tree) Have you asked the authors for clarification?