cevi

My favorite would have to be (Modular) SNUSP[1]. The combination of two-dimensional control flow with one-character recursion is completely irresistible to me. If it just had support for pointers, my life would be complete.

[1] https://esolangs.org/wiki/SNUSP

"The achievement of the Polish-Chinese-Canadian team of researchers is of fundamental importance, but it is so profound that it may translate into new quantum technologies."

Pure hyperbole. This result is philosophically interesting, and is useful in the sense that it might get some diehard anti-complex-numbers physicists to finally admit they were wrong (well, we can dream). But if it somehow leads to any new technology then I will eat my hat.

I expected to see just one or two, but this really does have quite a few good ones!

One of my favorite little-known algorithmic facts is that a sparse system of n linear equations in n unknowns over a finite field can be solved in time O(mn) if the corresponding matrix has m nonzero entries[1]. I'm surprised at how hard it is to extend this to the reals - it seems like dealing with the precision issues is much tougher than I imagined.

[1] http://www.enseignement.polytechnique.fr/profs/informatique/...

Reminds me very strongly of the opening lines of https://qntm.org/destroy

The best reference for learning quantum computing that I know is Watrous's notes: https://cs.uwaterloo.ca/~watrous/LectureNotes/CPSC519.Winter...

I am far from being an expert on descriptive complexity, and have only skimmed the paper. One spot jumped out at me as a potential error: on page 21, the sentence

"Next we exploit that a choice in state S will be insignificant iff all update sets in Delta_r(S) are isomorphic, so..."

seems suspicious to me. One direction is likely obvious (that an isomorphism between choices proves the insignificance of the choice), but the other direction seems likely to be untrue (if I am interpreting correctly).

This approach has been explored. It has only been helpful for showing that certain types of (short-ish) cycles can't occur [1]. Showing that the sequence can't get larger and larger forever (without repeating) with this approach has been a non-starter.

[1] See https://en.wikipedia.org/wiki/Collatz_conjecture#Cycle_lengt... for a few references. The most recent appears to be the paper "Theoretical and computational bounds for m-cycles of the 3n + 1 problem" by Simons and de Weger.

I took the class these notes were based on at Caltech with Peter Schröder - it was one of the most interesting courses I ever took. Glad to see these notes show up on HN.

Here's a reading recommendation list I put together over the years: http://math.mit.edu/~notzeb/rec.html

Two caveats: first, it is obviously biased to the sort of math I find enjoyable, and second, many of the suggestions require the reader to have that elusive quality called "mathematical maturity". (I have no idea how one goes about gaining mathematical maturity, despite having gone through this process myself.)

The obvious conspiracy theory: instead of arresting him, the chinese government quietly offered him a job.

The main problem I see with this is that it seems to implicitly assume the Extended Church-Turing Thesis, which is widely suspected to be false (assuming that quantum computers can be built, and that BQP is not equal to BPP).

How would a superintelligence living inside a cellular automaton (like the game of life) ever hope to estimate the probability of intelligent life arising in a world where chemistry is governed by quantum physics? How could we ever hope to understand the values of a typical superintelligence built in an alternate universe filled with Popescu-Rohrlich boxes (https://en.wikipedia.org/wiki/Quantum_nonlocality#Superquant...), let alone engage in acausal trade with it?

LeVeque's book "Fundamentals of Number Theory" is decent - it covers the basics (sometimes goes a bit beyond the basics), does some elementary ring theory, has exercises, and has a little bit of historical trivia.

Andrews has a book titled just "Number Theory" which is very combinatorial (gives a combinatorial proof of Fermat's little theorem) - the second half of the book is about partitions and their generating functions.

Borevich and Shafarevich have a book also titled just "Number Theory" which is an introductory text on algebraic number theory, ideal class groups, etc., and by the end it uses these techniques to explain how Kummer proved Fermat's Last Theorem for exponents below 100.

Baker's "A concise introduction to the Theory of Numbers" is exactly what it says on the tin. It has five to ten exercises per chapter, and each chapter is a fairly short introduction to a different branch of number theory, giving examples of the fundamental techniques or ideas or results in that area.

The main step seems to be Lemma 2. The fact that the reductions are logspace is never actually used in the argument - so if this proof worked, it would also apply to arbitrary reductions, and the same argument would show that NP is not contained in, say, EXP.

The fact that there are no inequalities anywhere throughout the paper is the real tip-off that this is not a serious attempt.

I always wondered what the bizarre hype about the d.school at Stanford was about.

Find better quantum error correcting codes, and quantum computers will show up that much faster.

Why not donate them to a library?

Personally, I'm looking forward to the day when Automated Theorem Provers can compete with top high school students on math competitions. My guess is that the way to go is to combine resolution theorem proving with intuitive pattern matching (via deep learning), similar to the way AlphaGo combined monte carlo tree search with deep learning.

More nominations:

Hashlife (golly)

SAT-solvers (minisat, glucose, lingeling, ...)

Convex optimization (CVXOPT, ...)

Aside from the silly claim that log(0) = 1, this has a fundamental flaw: if the attacker knows a sufficiently long chunk of the plaintext (standard headers, for instance), then it's nearly trivial to deduce the key (using gaussian elimination) and from there to get all the rest of the plaintext. Even without known plaintext, they can use statistical regularities of the English language to reverse engineer the key with high probability.

Modern cryptography assumes the attacker has gigabytes worth of known plaintext-ciphertext pairs (even chosen plaintext) to play with, and tries to make it hard for them to recover the key regardless. This assumption basically forces you to think about computational complexity.

If you're going to open source it, you may as well put it in a big repository such as http://www.personalgenomes.org/

Pros: mad scientists can make use of your genome. Cons: your health insurance provider might make use of your genome.

Maybe this explains the time I found a $20 bill in a rather obscure library book.