## Archive for June, 2006

### Time to do Scott’s research again

Tuesday, June 27th, 2006

Given vectors v1,…,vm in Rn, is it NP-hard to find a unit vector w that maximizes the (absolute value of the) product of inner products, |(v1·w)···(vm·w)|? What about in Cn? Are these problems hard to approximate on a logarithmic scale?

American.

### Confessions of a Hebrew Philistine

Thursday, June 15th, 2006

I took a lot of flak for expressing wrong musical opinions last week. Since I so enjoy the role of human flamebait, I’ve decided to have another go at clarifying my views about Art in general. See, until a few years ago, I was intimidated by art and music snobs, by the sort of person who recently deposited the following on Lance Fortnow’s blog:

man, the ignorance displayed here is taken to new levels. your ph.d. in computer science qualifies you as nothing musically, dumbass. ever heard of dynamic range? go look it up.

A bit uncivil, perhaps, but doesn’t this anonymous fount of musical wisdom have a point? After all, spouting off about quantum computers, entanglement, or Gödel’s Theorem without studying them first would certainly qualify you as a dumbass. So if I don’t think the same about music, then aren’t I a big fat hypocrite?

Ah, but consider the following. If — as the snob would be first to affirm — the purpose of art is not to assert or argue anything as a research paper would, but simply to produce an emotional response in the viewer or listener, then what does it even mean to be unqualified to voice that response? Presumably one person’s emotional response is as valid as another’s. Indeed, the difficulty with the snob is that he wants it both ways. “What made Picasso the greatest artist of the twentieth century is ineffable, indescribable — and I’m the one who knows enough to describe it to you.” “This opera is astounding because it induces a visceral, gut response in the audience — and if you don’t have that response, your gut must be mistaken.” The point is that, once you’ve declared something to be nonscientific, emotional, subjective, you have to allow that someone else’s subjective reaction might differ from yours.

So on this day, let us celebrate our freedom from the tyranny of pretending to like stuff we don’t. I’ll start the honesty ball rolling by dividing the world’s artistic output into three categories, then giving examples of each (not representative, just the first things that popped into my head).

Art that’s stirred my soul

The Simpsons
Futurama
South Park
Shakespeare (comedies especially)
Tom Sawyer and Huck Finn
The Mind-Body Problem by Rebecca Goldstein
Everything by Pixar

Art that maybe hasn’t moved me, but that I can nevertheless agree is quite impressive, based not on what other people say but on my own experience of it

The Sistine Chapel (indeed, pretty much everything in Rome)
Them big paintings in the Louvre
Them big Buddhist temples in Kyoto
Beethoven
Mozart
The Beatles
Jazz improv
Jimi Hendrix
Early Woody Allen

Art in neither of the two above categories

Late Woody Allen
Everything in the MoMA
Picasso
Van Gogh
Weird indie films where nothing happens
Anything by David Lynch or M. Night Shyamalan
Rap (except MC Hawking)
“Experimental” music

PS. There’s really no need to flame me if you have different tastes, since I won’t take it as a moral failing on your part. (Except with regard to M. Night Shyamalan.)

### Schrödinger’s cat is hunting masked chickens

Monday, June 12th, 2006

A commenter on my last post — who, since he or she chose not to provide a name, I’ll take the liberty of calling Dr. Doofus McRoofus — offers the following prediction about quantum computing:

[U]nless quantum computing can deliver something practical within the next five to ten years it will be as popular then as, say, PRAMs are today.

Four reactions:

1. String theory has been immensely popular for over 20 years, among a much larger community, with zero prospects for delivering anything practical (or even any contact with experiment, which — ahem — some of us have had for a decade). Reasoning by analogy, if quantum computing became popular around 1995, that should at least put us in the upper range of McRoofus’s “five to ten years.”
2. For better or worse, the funding outlook for quantum computing is much less depressing right now than for classical theoretical computer science. Many of us have been making the case to DARPA and NSF that classical complexity should continue to be funded in part because of its relevance for quantum computing.
3. The right analogy is not between quantum computing and PRAM’s; it’s between quantum computing and parallel computing. Specific architectures, like linear optics and PRAM’s, have gone in and out of fashion. Modes of computation, like nondeterminism, randomness, parallelism, and quantumness, have instead just gotten agglomerated onto the giant rolling snowball of complexity. As long as the snowball itself continues to tumble down the hill (shoot — bad metaphor?), I don’t see any reason for this to change.
4. I’m no good at predicting social trends, so perhaps time will prove me wrong and Dr. McRoofus right. But speaking for myself, I’d go insane if I had to pick research topics based on popularity. I became interested in quantum computing because of a simple trilemma: either (i) the Extended Church-Turing Thesis is false, (ii) quantum mechanics is false, or (iii) factoring is in classical polynomial time. As I put it in my dissertation, all three possibilities seem like wild, crackpot speculations, but at least one of them is true! The question of which will remain until it’s answered.

### Anonymous reviewing: the QWERTY of science

Saturday, June 10th, 2006

The journal Nature has started a three-month trial of a new peer review system. Here’s how it works: while a paper is sent out for traditional review, the authors can also choose to make it open for comments on the web. Any such comments are public and signed, and the authors can respond to them in public. Then, when making their acceptance decision, the editors take into account both the anonymous reviews and the public online discussion.

Personally, I think this is a phenomenal idea, and I hope it spreads to computer science sooner rather than later. I’ve always been struck by the contradiction between scientists’ centuries-old mistrust of secrecy — their conviction that “only mushrooms grow in the dark” — and their horror at signing their names to their opinions of each other’s work. Are we a bunch of intellectual wusses?

Inspired by Nature’s experiment, I’m going to try an experiment of my own. Rather than develop my views any further (which I don’t feel like doing), I’m just going to stop right here and open the field to comments. Go!

### Called in for another cohenoscopy

Thursday, June 8th, 2006

how does Leonard Cohen (the Montreal-born singer-songwriter, a.k.a. my latest hero) fit in “the Cohen balance of the universe”?

I’d heard of him, but I knew nothing about him until Ronald’s question prompted several hours of websurfing. (Thanks a million, Ronald!) As a result of this diligent research — as well as almost three full minutes of listening to mp3’s — I can now offer the world the following

COHEN SCORECARD

Starting credit: 1 point.

Seems like a nice guy: +3 points.

Singing voice several notches below me with a sore throat: -2 points.

Songs that I can’t imagine listening to for pleasure: -1 point.

Then again, I don’t listen to music: 1 point back.

In his seventies, continues to attract babes like flypaper: +4 points.

Is nevertheless profoundly melancholic: -4 points.

Verdict: Inconclusive.