Gödel's Lost Letter

This interesting article submitted here on HN is one I have often recommended to other readers, so I'm glad to see it on HN's main page. It's particularly interesting to read the comments here, mostly largely agreeing with Tao, as I am currently at Epsilon Camp,

http://epsiloncamp.org/

the most advanced mathematics summer program for YOUNG learners in North America, and the parents of the campers here are all pondering the issue of their children's mathematical development. Plainly, at any given age, some young people are more advanced in their mathematical development than many of their age mates, but it is still to be seen how steadily and consistently the mathematical development of the most advanced young learners can be developed if optimal practices are applied to their education.

Based on this published writing by Tao and various writings by other mathematicians, the Epsilon Camp program provides FAQ pages for parents,

http://epsiloncamp.org/FAQ.php

who in many cases are not themselves mathematicians, to serve as food for thought as precocious young mathematics learners are growing up. One of the issues for many of the parents from various parts of the United States is simply finding a flexible local school. Another issue, which the meetings of the parents at the camp has helped to handle, is sustaining friendship relationships among those most advanced young mathematics-learners as they disperse around the country at the end of the summer program. On the whole,…

This is something that I've struggled with myself so I can only give you advice as I've learned it from my perspective.

Math is a big field so you have to understand what parts you're really interested in and how you want information to be presented so that you'll learn it. For example, I'm interested in computation aspects of mathematics (information theory, computation group theory, abstract algebra, analysis, etc.) and I always prefer a "computer programmers" intuition in how to learn these subjects. That is, understanding how to 'program it', whatever that means for the different subjects I'm interested in.

Here is a small list of intuition I've learned about finding good resources:

* Books, and sometimes textbooks, are still a valuable resource. It's still the case that having a book on a subject that has curated content is better than the random Wikipedia articles or blog posts on the subject. Use Wikipedia, obviously, and look at blog posts, but I search for books in the subject area, especially if it's a field I'm not familiar with.

* When looking for books, prefer books that have "elementary" in the title, as in "elementary introduction". The more "advanced" books are talking about the bounds of research in the area, often fussing over esoteric issues whereas the "elementary" books give the foundation of knowledge in that area.

* Ideally for me, books would have "fundamental algorithms" somewhere in the title, as these books usually are exactly what I need to…

> This is like measuring the computational complexity of a mathematical proof - it has no complexity, it's delcarative.

There are few things that are absolute in this universe, but computational complexity is one of them. There is plenty of complexity involved. Have your heard of proof complexity? How do you know that a proof is a proof and how is a proof created? It's pretty much the core of P vs. NP question (and first discussed by Stephen Cook, the same guy who formally framed P vs. NP): https://en.wikipedia.org/wiki/Proof_complexity

Actually, the first one who asked the question of P vs. NP was Kurt Gödel (https://rjlipton.wordpress.com/the-gdel-letter/), and as a mathematician, he was very much interested in the complexity (although he didn't use that word) of proofs. He said that if P = NP (not in those words):

> If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n2), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine.

>Quantum Computers have been proved to be more powerful than classical. wrong.

I take issue with that claim.

Take for example, the Deutsch-Jozsa problem.
Given some function f, on n bits to one bit, such that f is either {zero on all the possible inputs, or one on all inputs}, or f is zero on half the inputs and one on the other half.
To tell which of those cases it is, it requires 2^(n-1) + 1 tests of f. You have to test it on half the inputs, plus one.

With the added power of a quantum computer, we can solve it with only one call to f.

Boom, there is exponential speedup with quantum computing. This is similar to what lies behind Shor's algorithm for factoring.

Check it out, wikipedia has diagrams that I can't put in here.

http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm

EDIT:
It seems he addresses this exact problem here
http://rjlipton.wordpress.com/2011/10/26/quantum-chocolate-boxes/

I apologize, I was a bit hasty to call him out, he does know what he is talking about.

this is great article for someone to undertand how cryptography and AES works - but as all great explanations - it fails to explain some key concepts that take it from 0 - to "got it!" for me (hacker with absolutely no idea of how cryptography works other than simple caesar ciphers and stuff from childhood books) - this actually reminds me of the article in rjlipton's blog that also made it up HN a couple of weeks ago (http://rjlipton.wordpress.com/2011/08/05/give-me-a-lever/) about the lever in any mathematical explanation. I'm going to use that a little leniently here and go so far as to say - the algorithm makes sense - but for someone who doesn't get cryptography - its the "key" that's the lever. I get the diffusion and confusion and most of the rest - that math is not the hardest bit. But how the key actually comes into being - and how the Standard ensures that only the 2 people in the conversation have the key - is what would really crack the entire thing for me.

Some related links:

An introduction to the area from before this new breakthrough -- https://www.ams.org/journals/notices/201910/rnoti-p1618.pdf

Gil Kalai on the mathematical implications -- https://gilkalai.wordpress.com/2020/01/17/amazing-zhengfeng-ji-anand-natarajan-thomas-vidick-john-wright-and-henry-yuen-proved-that-mip-re-and-thus-disproved-connes-1976-embedding-conjecture-and-provided-a-negative-answer-to-tsirelso/

Lance Fortnow -- https://blog.computationalcomplexity.org/2020/01/quantum-provers-to-infinity-and-beyond.html

KW Regen -- https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-time-quantum-provable/

Boaz Barak -- https://windowsontheory.org/2020/01/14/mipre-connes-embedding-conjecture-disproved/

Scott Aaronson -- https://www.scottaaronson.com/blog/?p=4512