Monday, November 20, 2006

The ugliest flame war of all time

Yes, after searching the web for 12 years, I've finally found it. This one, about two adorable twin girls who formed a white supremacist rock band called "Prussian Blue" (having been indoctrinated into Hitlerism by their mother), has 337 posts and has been going on for two years. It has racist and anti-Semitic bile that will outrage even the most seasoned connoisseurs of the genre -- and people who attempt to reason with those spewing it. It has side-skirmishes about pedophilia and the troubles in Northern Ireland. Forget about Godwin's Law. If you're under the illusion that World War II ended sixty years ago, read this thread.

(As you can see, what's kept me from posting Lecture 7 or anything else over the past week has been webilicious procrastination of the most severe form. I also spent five days reading about the history of South Africa and the historicity of the Book of Exodus. Good stuff! I should blog about it when I have the "time.")

Sunday, November 12, 2006

Handle with care

In today's quant-ph we find a report of a truly dramatic experiment -- one that detected entanglement between Baton Rouge, Louisiana and Givarlais, France. How, you ask: by fiber-optic cable? Satellite? Neither: by postal mail! The authors don't say if it was FedEx, UPS, or some other carrier that managed to ship half an EPR pair across the Atlantic without decohering it -- but whoever it was, that's who I'm using from now on.

(Note: On close reading, it appears that when the authors use the word "entanglement," they actually mean "classical correlation." However, this is a technical distinction that should only matter for experts.)

Public Relations 101

ALMATY, Kazakhstan – Sayat Tour, a leading Kazakh tour operator, announced today several new tours for Americans and others who are willing to travel to Kazakhstan and see for themselves what the real country, not the Borat's version, is really like.

The tours, called "Kazakhstan vs. Boratistan" and "Jagzhemash!!! See the Real Kazakhstan", include visits to the cosmopolitan Almaty and its beautiful surroundings, tours of ancient sites such as the Hodja Akhmed Yassaui Mausoleum in Turkestan, as well as plentiful opportunities to meet and interact with the real Kazakhs. In addition to sightseeing, tours also include visits to local colorful bazaars, artifact shops and high fashion boutiques, as well as trying kumyss, the deliciously tasting Kazakh traditional drink made from fermented horse milk.

Marianna Tolekenova, Sayat's Executive Director, said: "With the release of Borat: Cultural Learnings of America for Make Benefit Glorious Nation of Kazakhstan, we are hoping many Americans will want to engage in 'cultural learnings' of that unknown 'glorious nation' for their own 'make benefit.' That is why we are launching these new tours and hoping the Americans will come visit us."

Earlier in October 2006, a high ranking Kazakh official said the creator of Borat, British comedian Sasha Baron Cohen, would be welcome in Kazakhstan. First Deputy Foreign Minister Rakhat Aliyev said, "His trip could yield a lot of discoveries -- that women not only travel inside buses but also drive their own cars, that we make wine from grapes, that Jews can freely attend synagogues and so on."
Update (11/13): In response to a comment by Greg Kuperberg, I've now reached a halakhic ruling on the morality of Sacha Baron Cohen's antics. Go to the comments section if you want to read it.

Thursday, November 09, 2006


Monday, November 06, 2006

Beating swords into pitchforks

Here's a heartwarming story of religious reconciliation in Israel, one that puts the lie to those cynics who thought such ecumenism impossible. It seems that large portions of Jerusalem's Orthodox Jewish, Muslim, and Christian communities have finally set aside their differences, and joined together to support a common goal: threatening the marchers in a Gay Pride parade with death.

Sunday, November 05, 2006

This week, let's overthrow the Taliban

Let this man's face serve as a reminder to all my American friends, to haul your respective asses to your respective polling places with no excuses accepted. Keep in mind that this year the Democratic voting day is Tuesday November 7th, while the Republican voting day is Wednesday November 8th.

(Me? I couldn't find a precinct station in Waterloo for some strange reason, so I mailed an absentee ballot back to New Hope, PA.)

Friday, November 03, 2006

More tender nuggets

You asked for 'em, you got 'em. (Do you want fries with that?)
  1. Suppose a baby is given some random examples of grammatical and ungrammatical sentences, and based on that, it wants to infer the general rule for whether or not a given sentence is grammatical. If the baby can do this with reasonable accuracy and in a reasonable amount of time, for any "regular grammar" (the very simplest type of grammar studied by Noam Chomsky), then that baby can also break the RSA cryptosystem.

  2. Oded Regev recently invented a public-key cryptosystem with an interesting property: though it's purely classical, his system only known to be secure under the assumption that certain problems are hard for quantum computers. The upside is that, if these problems are hard for quantum computers, then Regev's system (unlike RSA) is also secure against attack by quantum computers!

  3. Suppose N boys and N girls join a dating service. We write down an N-by-N matrix, where the (i,j) entry equals 1 if the ith boy and the jth girl are willing to date each other, and 0 if they aren't. We want to know if it's possible to pair off every boy and girl with a willing partner. Here's a simple way to find out: first rescale every row of the matrix to sum to 1. Then rescale every column to sum to 1. Then rescale every row, then rescale every column, and so on N5 times. If at the end of this scaling process, every row and column sum is between 1-1/N and 1+1/N, then it's possible to pair off the boys and girls; otherwise it isn't.

  4. If two graphs are isomorphic, then a short and simple proof of that fact is just the isomorphism itself. But what if two graphs aren't isomorphic? Is there also a short proof of that -- one that doesn't require checking every possible way of matching up the vertices? Under a plausible assumption, we now know that there is such a proof, for any pair of non-isomorphic graphs whatsoever (even with the same eigenvalue spectrum, etc). What's the plausible assumption? It has nothing to do with graphs! Roughly, it's that a certain problem, which is known to take exponential time for any one algorithm, still takes exponential time for any infinite sequence of algorithms.

  5. Suppose we had a small "neural network" with only three or four layers of neurons between the input and output, where the only thing each neuron could do was to compute the sum of its input signals modulo 2. We can prove, not surprisingly, that such a neural net would be extremely limited in its power. Ditto if we replace the 2 by 3, 4, 5, 7, 8, 9, or 11. But if we replace the 2 by 6, 10, or 12, then we no longer know anything! For all we know, a three-layer neural network, composed entirely of "mod 6 neurons," could solve NP-complete problems in polynomial time.

Thursday, November 02, 2006

Logicians on safari

Sean Carroll, who many of you know from Cosmic Variance, asked the following question in response to my last entry:
I'm happy to admit that I don't know anything about "one-way functions and interactive proofs." So, in what sense has theoretical computer science contributed more in the last 30 years to our basic understanding of the universe than particle physics or cosmology? (Despite the fact that I'm a cosmologist, I don't doubt your statement -- I'd just like to be able to explain it in public.)
I posted my response as a comment, but it's probably better to make it an entry of its own. So:

Hi Sean,

Thanks for your question!

Of course I was joking when I mentioned "objective standards" for ranking scientific fields. Depending on which questions keep you up at night, different parts of "humankind's basic picture of the universe" will seem larger or smaller. (To say that, of course, is not to suggest any relativism about the picture itself.)

What I can do, though, is to tell you why -- by my own subjective standards -- the contributions of theoretical computer science over the last 30 years rival those of theoretical physics or any other field I know about. Of course, people will say I only think that because I'm a theoretical computer scientist, but that gets the causal arrow wrong: I became a theoretical computer scientist because, as a teenager, I thought it!

It's probably best to start with some examples.
  1. We now know that, if an alien with enormous computational powers came to Earth, it could prove to us whether White or Black has the winning strategy in chess. To be convinced of the proof, we would not have to trust the alien or its exotic technology, and we would not have to spend billions of years analyzing one move sequence after another. We'd simply have to engage in a short conversation with the alien about the sums of certain polynomials over finite fields.

  2. There's a finite (and not unimaginably-large) set of boxes, such that if we knew how to pack those boxes into the trunk of your car, then we'd also know a proof of the Riemann Hypothesis. Indeed, every formal proof of the Riemann Hypothesis with at most (say) a million symbols corresponds to some way of packing the boxes into your trunk, and vice versa. Furthermore, a list of the boxes and their dimensions can be feasibly written down.

  3. Supposing you do prove the Riemann Hypothesis, it's possible to convince someone of that fact, without revealing anything other than the fact that you proved it. It's also possible to write the proof down in such a way that someone else could verify it, with very high confidence, having only seen 10 or 20 bits of the proof.

  4. If every second or so your computer's memory were wiped completely clean, except for the input data; the clock; a static, unchanging program; and a counter that could only be set to 1, 2, 3, 4, or 5, it would still be possible (given enough time) to carry out an arbitrarily long computation -- just as if the memory weren't being wiped clean each second. This is almost certainly not true if the counter could only be set to 1, 2, 3, or 4. The reason 5 is special here is pretty much the same reason it's special in Galois' proof of the unsolvability of the quintic equation.

  5. It would be great to prove that RSA is unbreakable by classical computers. But every known technique for proving that would, if it worked, simultaneously give an algorithm for breaking RSA! For example, if you proved that RSA with an n-bit key took n5 steps to break, you would've discovered an algorithm for breaking it in 2n^1/5 steps. If you proved that RSA took 2n^1/3 steps to break, you would've discovered an algorithm for breaking it in n(log n)^2 steps. As you show the problem to be harder, you simultaneously show it to be easier.
Alright, let me stop before I get carried away. The examples I've listed (and hundreds more like them) are not exactly discoveries about physics, but they don't have the flavor of pure math either. And even if they have some practical implications for computing (which they do), they certainly don't have the flavor of nitty-gritty software engineering.

So what are they then? Maybe it's helpful to think of them as "quantitative epistemology": discoveries about the capacities of finite beings like ourselves to learn mathematical truths. On this view, the theoretical computer scientist is basically a mathematical logician on a safari to the physical world: someone who tries to understand the universe by asking what sorts of mathematical questions can and can't be answered within it. Not whether the universe is a computer, but what kind of computer it is! Naturally, this approach to understanding the world tends to appeal most to people for whom math (and especially discrete math) is reasonably clear, whereas physics is extremely mysterious.

In my opinion, one of the biggest challenges for our time is to integrate the enormous body of knowledge in theoretical computer science (or quantitative epistemology, or whatever you want to call it) with the rest of what we know about the universe. In the past, the logical safari mostly stayed comfortably within 19th-century physics; now it's time to venture out into the early 20th century. Indeed, that's exactly why I chose to work on quantum computing: not because I want to build quantum computers (though I wouldn't mind that), but because I want to know what a universe that allows quantum computers is like.

Incidentally, it's also why I try hard to keep up with your field. If I'm not mistaken, less than a decade ago cosmologists made an enormous discovery about the capacity of finite beings to learn mathematical truths: namely, that no computation carried out in the physical world can ever involve more than 1/Λ ~ 10122 bits.