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.
Category Archives: Computer science
Setting Back the Course of Complexity Theory
We here at Ars Mathematica set back the course of complexity theory by several hours, and Scott Aaronson thanks us for it.
Topological semantics of computer programs
The latest issue of the e-journal, Electronic Notes in Theoretical Computer Science, has a nice summary article by Michael Huth on his work using topology for computer program semantics (vol. 161, pp. 3–23, 2006).
Logic and computer science
Logician Solomon Feferman, who did his PhD under Alfred Tarski, has just written a short article on Tarski’s influence on computer science. It seems that this influence was wider than just that between cylindrical algebras and relational database theory.
Grete Hermann
This thread about famous women mathematicians on Cocktail Party Physics, reminded me of an interesting figure in history that I came across while doing researching for a Wikipedia article: Grete Hermann. (The Wikipedia article is a skeleton that I created; it could use a lot of work.)
Hermann was a student of Emmy Noether. Noether was one of the iconic figures of twentieth-century mathematics, a key figure in the century’s trend toward abstraction. A typical example is her proof of the Lasker-Noether theorem. The theorem, that every ideal has a primary decomposition, was originally proven for polynomial rings by Emanuel Lasker, using a difficult computational argument. Noether identified the key abstract condition behind the result — the ascending chain condition on ideals — and used it to give a shorter proof of a much more general theorem. Rings that satisfy the ascending chain condition on ideals are now known as Noetherian rings in her honor.
While Hermann was Noether’s student, her thesis was a throwback to the nineteenth century’s computational approach. Hermann showed that Lasker’s approach could be turned into an effective procedure for computing primary decompositions. Hermann did this before the invention of the computer, or even before the notion of an effective procedure had been formalized. (As her definition, Hermann used the existence of an explicit upper bound on time complexity, and gave such a bound for primary decomposition, and other questions in commutative ring theory.)
Hermann went on to work in philosophy and the foundations of physics. John Von Neumann had proposed a proof that a hidden variable theory of quantum mechanics could not exist. (A hidden variable theory is one that explains the random behavior of quantum mechanical systems in terms of unobserved deterministic variables.) Hermann discovered and published the flaw in Von Neumann’s proof back in 1935, a result that has no impact until it was rediscovered by John Bell some thirty years later.
(The thread on Cocktail Party Physics is instructive for just how unfamous mathematicians really are. For physicists, Karl Weierstrauss is an obscure historical figure. For mathematicians of course, Weierstrauss is five times as famous as Madonna and Britney Spears combined. It was interesting to learn that Sofia Kovalevskaya is not particularly well-known among physicists, even though part of her research was in classical mechanics.)
Bacon on Quantum Computing
This post by Dave Bacon on his weblog, makes quantum computing sound like a modest extension of classical computing, which works by speeding up computation of Fourier transforms on Z/2Z: quantum computers can be built up out of two different gates, the Toffoli gate (which is universal for classical computation), and the Hadamard gate, which implements the Fourier transform on Z/2Z. The full discrete Fourier transform can be built out of this special case.
Dave links to a short proof of the universality of this family of gates by Dorit Aharonov.
Laws of Form and Bigraphs
Alerted by a post of sigfpe, I learnt about George Spencer-Brown’s 1972 book Laws of Form. Reading Louis Kauffman’s account of the theory, I was struck by the similarity to Robin Milner‘s theory of bigraphs (see here for papers). From a talk I heard him give a few years ago, I believe that Milner’s theory was originally intended as a rigorous category-theoretic account of hyperlinks in computer networks. Has anyone explored the connections between these two mathematical theories?
Data visualization software
Statisticians among us may be interested in Gapminder, free data visualization software from Sweden developed originally to assist in communicating information about global development. The software makes use of web animation tools such as Flash.
The physicists and the wagon
Scott Aaronson has posted an extremely funny parable on his weblog about physicists and impossibility proofs.
Wanted: game theorists
The University of Liverpool (UK) has a vacancy for a post-doc researcher and for a PhD student, both in automated mechanism design. The expertise we are looking for includes game theory, mechanism design and auction theory, mathematical economics, and computational versions of same. These posts are part of a major UK research project on market-based control of complex computational systems.