Shtetl-Optimized

Given vectors v₁,…,v_m in Rⁿ, is it NP-hard to find a unit vector w that maximizes the (absolute value of the) product of inner products, |(v₁·w)···(v_m·w)|? What about in Cⁿ? Are these problems hard to approximate on a logarithmic scale?

$20 for answers to all three. I should get better at doing these things myself.

Follow

According to ancient complexity lore, at a saddle point high in the mountains of Oberwolfach lies buried a single flask of a mystical elixir known as Websbane, or the Hammer of Firefox. Some say that the productivity-enhancing potion was brewed from the sweat of Erdös and the toenail clippings of Euler; others that it was mixed, condensed, and extracted for the Prophesied One centuries hence who will derandomize BPP. Yet all agree on the tonic’s awesome efficacy: it is said that one drop would furnish lifelong protection against Slate and Salon; a teaspoonful would lift Wikipedia’s stranglehold on the soul. He who once imbibed would neither reread Onion articles from dusk till dawn, nor follow hyperlinks till scarcely a blue word remained amidst the purple, nor while away a Thursday googling a Montreal-born singer-songwriter mentioned in an email of de Wolf. Papers would get finished – books written – reimbursement forms turned in – blog entries posted without delay.

Today’s topic is what we can do until the Websbane is unearthed from its resting-ground. I offer four suggestions below; any additions are welcome.

• Use the embryo strategy. Whenever you’re procrastinating on something, someone is bound to tell you “divvy it up into smaller chunks, then tackle ’em one at a time.” I’ve found that to be terrible advice. When I’m starting a project, I have no idea how to divvy it up. I might commit myself to writing chapters on A, B, and C, only to realize later that A and C are trivial and that everything worth saying pertains to B. Or I might start the introduction, then freeze for days because I can’t decide what belongs in the introduction and what belongs in the “meat” until I’ve already written them.What I’ve found to be more effective is what I’ll call the “embryo strategy.” Here you simplify your project so dramatically that you can finish the entire thing (more or less) in one afternoon. For example, if before your goal was to write a ten-page popular article about quantum computing, now your goal is to write two paragraphs. Then, once you’ve finished something, you progressively add layers to it. This seems to be the approach taken by most successful software projects, not to mention by Nature herself. The advantages are twofold: firstly, everything is built around one initial idea. This changes what the end product looks like, but I think for the better. And secondly — here’s the real beauty — at no point are you ever working on something that will take “unimaginably long,” compared to the amount of time you’ve already spent. (Give or take a small additive constant.)

• Exploit the “quantum Zeno effect.” One to keep a quantum state from drifting uncontrollably is just to measure it over and over in some fixed basis. Roughly speaking, the mere fact that you’re looking means that the state “can’t try anything funny.” Similarly, I’ve taken to having my girlfriend spend the night with me when I need to finish a paper. What ensues is a long, romantic evening, wherein I sit at my computer and do my work, and Kelly sits at her computer and does her work. Interestingly, her mere presence often has the effect of projecting me onto a non-procrastinating subspace. (Kelly reports a similar effect on her as well.)

• Don’t eat. When you’re trying to prove theorems about quantum complexity classes, hunger is your friend and linguini-induced sleepiness your enemy. As obvious as that sounds, it took me almost a decade fully to understand its importance. These days I usually eat only one meal per day — my “brinner” — and don’t even try to work till three or four hours after it. (Does anyone know the physiological reason why humans seem unable to multitask between brains and stomachs?)

• Find yourself a “boss.” When I was at Berkeley, Umesh was my boss. That doesn’t mean he told me what to work on (he didn’t); it means that I got a warm fuzzy feeling from eliciting his opinion of what I had worked on. Since graduating, to stay productive I’ve had to seek out a succession of new “bosses” — from Avi Wigderson at IAS, to collaborators like Greg Kuperberg and Daniel Gottesman. Indeed, if you get a long, technical email from me, it’s not necessarily for your benefit. Mathematicians might be machines for turning coffee into theorems, but the fuel I run on is feedback.

Follow these rules, and you might someday become as disciplined and productive as I am.

Follow

And how is not this the most reprehensible ignorance, to think that one knows what one does not know? But I, O Athenians! in this, perhaps, differ from most men; and if I should say that I am in any thing wiser than another, it would be in this, that not having a competent knowledge of the things in Hades, I also think that I have not such knowledge.

Shtetl-Optimized’s Mistake of the Week series finally resumes today, with what’s arguably the #1 mistake of all time. This one’s been noted by everyone from Defense Secretary Donald Rumsfeld, to some toga-wearing ancient dude, to the authors of the paper Unskilled and Unaware of It: How Difficulties In Recognizing One’s Own Incompetence Lead to Inflated Self-Assessments.

Rather than give examples of this mistake — where would I start? where would I stop? how often have I made it myself? — I figured it’d be easier to give an example where someone didn’t make it. Today I received an email from a graduate student who had proved a quantum oracle separation, and wanted to know whether or not his result was too trivial to publish. I get fan mail, I get hate mail, I get crank mail, I get referee requests, but this is something I almost never see. After telling the student why his result was, indeed, too trivial to publish, I wrote:

There’s no shame in proving things that are already known, or that follow easily from what is. Everyone does it, the more so when they’re just starting out … The very fact that you cared enough to ask me if your result is trivial bodes well for your proving something nontrivial.

Follow

[Here’s a little fable that I wrote today, while listening to a talk “showing” that a fault-tolerant quantum computer would need at least 100 physical qubits for every logical qubit. Physicists are welcome to shoot back with counter-fables, as are closet computer scientists like His Holiness.]

Update: The Pontiff has accepted my challenge and posted a counter-fable to his blog. I’ve replied in his comments section with a counter-counter-fable.

One day a group of physicists ran excitedly into the computer science building. “Guess what?” they cried. “You know how you’re always trying to prove lower bounds, but you almost never succeed? Well, today we proved a lower bound!”

“What did you prove?” asked the computer scientists.

“We proved that to pull a wagon through a forest, you need at least five oxen. It’s physically impossible to do it with four oxen or less, regardless of what other resources you have.”

“How did you prove that?”

“Well, we looked up the strength of a typical ox, the weight of a typical wagon, the size of every forest in a 30-mile radius…”

“Yeah, but what if you had an ox the size of a Brontosaurus? Or what if the forest was only two feet across? Or what if the wagon weighed less than a fingernail?”

The physicists snickered. “These are clearly unphysical assumptions. As long as you stay within a realistic region of parameter space, our impossibility proof is airtight.”

“Ah, but how do you know there couldn’t be some completely different method of pulling wagons — maybe even a method that’s not ox-based at all?”

“Look, we physicists are interested in the real world, not complexity-theory la-la land. And at least in the real world, when people want to pull wagons, oxen are what they use.”

The physicists weren’t heard from again until almost a decade later, when they once again barged into the CS building. “Guess what?” they cried. “We just discovered a loophole in the famous Five-Ox Theorem — the one we published years ago in Nature!”

“What’s the loophole?”

“Elephants! If you had an elephant pulling the wagon, you wouldn’t need any oxen at all. With hindsight it’s almost obvious, but what a paradigm shift it took!”

The computer scientists stared blankly.

“You see,” said the physicists. “This is why we never trust so-called impossibility proofs.”

Follow

When you see me getting chased across the blogosphere by livid, paintbrush-wielding artistes, it can only mean one thing: that I’ve once again abandoned my “promise” to stick to the Serious Complexity Theory That I’m Actually Qualified To Discuss. So I’ll tell you what, whistling-pig-lovers: answer me the following; then come back for more.

Given a set of n-by-n real matrices, is there a nonzero linear combination of those matrices with rank 1? Equivalently, given a subspace S of a bipartite n-by-n Hilbert space, does S contain a separable state?

I’d like (1) a proof of NP-hardness for the exact version, and (2) more importantly, whether or not there’s a decent approximation algorithm. (For instance, an algorithm that finds a rank-1 matrix, with the sum of the squares of the entries equal to 1, whose L₂-distance from the subspace of interest is at most a small additive constant more than optimal.)

So get cracking! If you do find a decent approximation algorithm, you’ll have shown, among other things, that QMA(2) (QMA with two unentangled yes-provers) is in EXP. Incredibly, right now we don’t have any upper bound better than NEXP.

Oh, yes: while my brain is closed, and while I can barely turn theorems into coffee, I will offer $20 for a solution to (2).

American.

Follow

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
Arcadia by Tom Stoppard

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

Follow

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.

Follow

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!

Follow

Ronald de Wolf asks:

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.

Follow