fdupress
Joined 7 years ago
Joined 7 years ago
As the silliest example of this: the Calculus of Inductive Constructions (the core calculus implemented in Lean) has a published proof of its soundness (that you cannot derive False in it). That proof can (probably, thanks to Gödel) not be formalized in Lean or any formal system of axioms weaker than Lean.
If what you were trying to do was define what it means for something to be a correct proof, then you must equally admit that there can't be a correct proof of the fact that Lean can't prove False. And if you find that world a happy world to live in while we delegate all concerns about truth to Lean, then I have an infinite hierarchy of monotonically growing bridges to sell you.
Replacing thought and curation with repeated automation is tech debt, pushed down to fundamental knowledge and understanding.
If that "bait" caused you to stop reading despite the fact that you probably agree with the author's sentiment, it's not very good bait.
That's all I can think of, though.
I could not follow where the leaf_hash is used carefully enough to figure out exactly how dangerous this is in the broader context and taking future evolution into account. But it's clearly safe as it is used now because all expected inputs have the same length.
> Note: Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.