People always post interesting links in the comments to Scott Aaronson’s weblog. For example, the other day Paul Beame posted two links that explain the connections between random walks on graphs and electrical networks. One is a complete book on the subject by Doyle and Snell. The other is an article by Chandra, Raghavan, Ruzzo, Smolensky, and Tiwari that further develops the theory.
David Corfield highlights two articles by Samson Abramsky: one on Temperley-Lieb algebras and the other on concurrency.
The concurrency article, What are the fundamental structures of concurrency? We still don’t know!, discusses the profusion of formalisms for representing concurrency. Abramsky passes on the following anecdote:
The mathematician André Weil apparently compared finding the right definitions in algebraic number theory — which was like carving adamantine rock—to making definitions in the theory of uniform spaces (which he founded), which was like sculpting with snow.
Jim Gray, the 1998 Turing Award winner, has gone missing on a sailing trip off the coast of California to scatter his mother’s ashes.
His book on the inner workings of databases, Transaction Processing: Concepts and Techniques, is very good.
Update. Cosmic Variance has more about Gray. He was a major contributor to the Sloan Digital Sky Survey.
I’ve been insanely busy lately, which means I have a gigantic backlog of stuff that I meant to link to, but didn’t.
Scott Aaronson has a knack for taking certain interesting but not obviously revolutionary inspiring concepts in complexity theory and in good Russian-formalist fashion, making them strange. Here are some examples:
This is probably well-known to everyone in physics, but less well-known to pure mathematicians. For a open-source high quality implementation of linear algebra computations such as finding eigenvalues, the standard is LAPACK (distributed by Netlib, a numerical source code repository). It is so standard, in fact, that tuned versions exist for individual architectures, and LAPACK performance is frequently used to benchmark processors.
Lambda the Ultimate links to a cool little paper, An Incremental Approach to Compiler Construction. It’s literally a short tutorial on how to write a compiler. It concentrates on the least-complicated but most-intimidating phase: machine code generation.
November Notices of the AMS are out. The entire issue is devoted to Alan Turing.
Interestingly, known public-key cryptosystems all seem to depend on the difficulty of the hidden subgroup problem. Suppose you have a group that can observe, and a subgroup that you cannot observe. Instead, you have a function that is constant along cosets of the group and different for different subgroups. The hidden subgroup problem is to compute a generating set for the subgroup just by evaluating the function. The problem generalizes integer factorization, the graph isomorphism problem and the problem of finding the shortest vector in a lattice. An efficient algorithm would apparently crack all known public-key cryptosystems.
Chris Lamont has a survey paper on the hidden subgroup problem in quantum computing, one that does not assume any background in quantum mechanics. Dave Bacon has some thoughts on an alternate approach.
I was under the impression that the uncracked public-key cryptosystems were all based on number theory, which made them vulnerable to variants of Shor’s algorithm. Yesterday I learned via Dave Bacon that there are cryptosystems based on the hardness of finding the shortest vector on a lattice. Here is a survey paper on the subject by Oded Regev. There is also the McEliece cryptosystem, which is based on coding theory.
We here at Ars Mathematica set back the course of complexity theory by several hours, and Scott Aaronson thanks us for it.