The microblog: 2021.12.10 16:34:42

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 ( Decided to tweet the nesting question too.


2021.11.12 17:37:35 (1459198701826547713) from Daniel J. Bernstein:

Skeptical about Corollary 7 of 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, 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?