Shtetl-Optimized

So, I finally had it both with Blogger, which was constantly down, and with my web hosting service, which was constantly down and inserting hidden Cialis ads into my homepage. (Yes, really.) So I ditched them both!

This morning Shtetl-Optimized finally departed the old country, and boarded a crowded ship bound for a strange new world: the world of Bluehost and WordPress. So welcome to a brand-new blog, which will feature the same name as the old one, the same topics, and the same terrible jokes. I hope you like it.

(Also this morning, I discovered a little hole-in-the-wall in Waterloo that sells hot, fresh bagels barely distinguishable from what you could get in New York. Yes, this is shaping up to be a very good day.)

(Oh, yes: Happy belated Thanksgiving to my American friends. I decided to stay in Waterloo over Thanksgiving to teach my course — is this is a sign that I’m actually becoming Canadian?)

Follow

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.)

Follow

From sayat-travel.kz:

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.

Follow

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.

Follow

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 7^th, while the Republican voting day is Wednesday November 8^th.

(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.)

Follow

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 i^th boy and the j^th 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 N⁵ 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.

Follow

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 n⁵ steps to break, you would’ve discovered an algorithm for breaking it in 2^{n^1/5} steps. If you proved that RSA took 2^{n^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 19^th-century physics; now it’s time to venture out into the early 20^th 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/Λ ~ 10¹²² bits.

Best,
Scott

Follow

Yesterday’s Times ran an essay by Steve Lohr, based on speeches about the future of computing given by my former teachers Richard Karp and Jon Kleinberg. Though most of the essay is welcome and unobjectionable, let’s look at the first two paragraphs:

Computer science is not only a comparatively young field, but also one that has had to prove it is really science. Skeptics in academia would often say that after Alan Turing described the concept of the “universal machine” in the late 1930’s — the idea that a computer in theory could be made to do the work of any kind of calculating machine, including the human brain — all that remained to be done was mere engineering.

The more generous perspective today is that decades of stunningly rapid advances in processing speed, storage and networking, along with the development of increasingly clever software, have brought computing into science, business and culture in ways that were barely imagined years ago. The quantitative changes delivered through smart engineering opened the door to qualitative changes.

So, here are the two options on offer from the paper of record: either

1. computer science was finished off by Alan Turing, or
2. “stunningly rapid advances in processing speed, storage and networking” have reopened it just recently.

Even among the commenters on this post by Chad Orzel — which Dave Bacon forwarded to me with the subject line “bait” — awareness of any third possibility seems depressingly rare. Judging from the evidence, it’s not that people have engaged the mysteries of P versus NP, randomness and determinism, one-way functions and interactive proofs, and found them insufficiently deep. Rather, as bizarre as it sounds, it’s that people don’t know these mysteries exist — just as they wouldn’t know about black holes or the Big Bang if no one told them. If you want to understand why our subject — which by any objective standard, has contributed at least as much over the last 30 years as (say) particle physics or cosmology to humankind’s basic picture of the universe — receives a whopping $5 million a year from the NSF (with even that in constant danger), look no further.

Follow