Ars Mathematica

Sanjeev Arora is writing a new book on computational complexity, and he’s posting the draft chapters online. Since the standard textbook on the subject, Papadimitriou’s Computational Complexity, is from 1993, a more-recent take on the subject is much appreciated.

I’m a total amateur in the subject, but my impression looking at the notes is that the big difference between 1993 and now is that in 1993 researchers were already beginning to suspect that the best idea in years for settling P versus NP (circuit complexity) wasn’t going to work, and now they’re pretty sure it won’t work.

In the introduction, Arora provides a more succinct summary of the post-1993 work than I possibly could:

The list of surprising and fundamental results proved in the 1990s alone could fill a book: these include new probabilistic definitions of classical complexity classes ( IP = PSPACE and the PCP Theorems) and their implications for the field of approximation algorithms; Shor’s algorithm to factor integers using a quantum computer; an understanding of why current approaches to the famous P versus NP will not be successful; a theory of derandomization and pseudorandomness based upon computational hardness; and beautiful constructions of pseudorandom objects such as extractors and expanders.

We’ve previously linked to some expository material on expanders.

Via Scott Aaronson.

On his blog, Sigfpe has proposed SIGFPE’s Law, that unlike the exponential growth of ordinary computers, the number of qubits in a quantum computer will only grow linearly. So when the mafia hacks into your bank account a la Sneakers because of their quantum public-encryption-cracking supercomputer, blame Sigfpe for getting it so terribly wrong. Also, blame him for the lack of flying cars.

(One subtlety to keep in mind — which Sigfpe alludes to — a 2-qubit computer is not the same thing as 2 1-qubit computers. The the states of each qubits must allow quantum superposition with each other to really count.)

This post on Scott Aaronson’s weblog is every internet discussion thread in microcosm (except for ours, which are shockingly polite by internet standards). Scott thought he was explaining the notion of non-constructive proof to a dense but argumentative student. If you read the comment thread, though, you’ll discover that the “student” thought Scott was some sort of nut who imagined he’d invented a computer more powerful than a Turing machine.

The Enigma machine was a mechanical encoding/decoding device used by the German military in WWII and which the British were able to successfully crack on occasion. It is now possible to purchase a Do-it-yourself Enigma machine and even a paper-version of one.

Epistemic modal logic was invented by Finnish philosopher Jaako Hintikka to represent knowledge and belief (in a book published in 1962), and is now used by computer scientists to model and design systems of autonomous software agents. It uses modal operators to indicate which propositions are known to which agents.

A common modal system for beliefs is C. I. Lewis‘ system S5, which (among other axioms) assumes that agents know what it is they know (positive introspection) and know what it is that they don’t know (negative introspection). (In other words, if an agent does not know whether or not some proposition is true, then the agent knows that he does not know whether or not that proposition is true). These are quite strong assumptions, and have been criticized as being unrealistic. Two computer scientists, Joseph Halpern and Leandro Chaves Rego, have now identified negative introspection as the axiom which makes the satisfiability problem for S5 NP-complete.

As an aside, discussion of positive and negative introspection by epistemic logicians meant that they fully understood Donald Rumsfeld’s statements about known unknowns vs. unknown unknowns.

Scott Aaronson and Greg Kuperberg have put together a website, the Complexity Zoo, that describes 443 (!) computational complexity classes.

Finding those math theorems or conjectures just too hard to prove? Then, you need to attend this workshop.

One important thread in computer science is the study of extensions of the lambda calculus. The lambda calculus is a model of computation that uses rewrite rules based on a simple notion of a function. The rho calculus extends the lambda calculus to allow more general rewrite rules based on pattern matching. For a survey, see the paper Matching Power or the web site The Rho-Calculus Home Page.

Via Lambda the Ultimate.

Jeffrey Lagarias has been maintaining a summary of work on the Collatz problem, which is arguably the easiest open problem in mathematics: The 3x+1 problem: An annotated bibliography. It’s disturbing that such a simple problem is unsolved.

If anyone’s interested in contributing to Wikipedia, here’s an opportunity. To fix some errant links, I’ve just created a stub page on corecursion. Unfortunately, I know almost nothing about the topic, so if you do, now’s your chance to show off.