Shtetl-Optimized

If you hadn’t been reading the comments on my last post, you might not know that my old chum Mahmoud Ahmadinejad had launched his own blog on Sunday. Along with a rambling autobiography, this exciting new blog (which I’ve added to my linklog on the right) also includes a poll:

Do you think that the US and Israeli intention and goal by attacking Lebanon is pulling the trigger for another word [sic] war?

When I first visited, only 5% had voted “yes”, though it’s now up to 50%.

But wait, it gets better: if Mahmoud’s site identifies your IP address as coming from Israel, then it tries to install a virus on your computer by exploiting an Internet Explorer vulnerability. (Thanks to an anonymous commenter for bringing this to my attention.)

I suppose we should grateful that, at least for now, defending oneself against the modern-day Hitler is as simple as installing Firefox.

Follow

A commenter on a previous post writes:

A lot of great discoveries came from non-scientific losers. E=MCC. Airplanes. America. Someone discovered how to make an airplane by playing with a box. Physics is mostly theoretical. America, I guess, is the most scientific discovery. They applied the scientific method to determine its existence, but they used no control group, and no placebo. For that, America’s existence is not yet proven. There seem to be other ways of establishing truth than just the scientific method. Scientists are contemporary soothsayers. They should use every means possible of proving a fact.

Despite its insightfulness and coherence, the above argument raises some immediate questions:

1. What does it have to do with anything I said?
2. E=MCC?
3. What would mean to use a placebo or control group to test America’s existence? Would it mean sending a ship in a different direction, and checking that it didn’t also reach America? Would it mean verifying that America can’t be reached from Europe by foot — since if it could, then it wouldn’t be America, but rather part of Eurasia?
4. Has England’s existence been scientifically proven? What about France’s?
5. Where do so many people get the cockamamie idea that there’s such a thing as a “scientific method” — that science is not just really, really, really careful thinking? (I blame the school system.)

Follow

From these lecture notes by Harvey Friedman comes one of the best metamathematical anecdotes I’ve ever heard (and yes, I’ve heard my share). Apparently Friedman was attending a talk by the “ultra-finitist” Alexander Yessenin-Volpin, who challenged the “Platonic existence” not only of infinity, but even of large integers like 2¹⁰⁰. So Friedman raised the obvious “draw the line” objection: in the sequence 2¹,2²,…,2¹⁰⁰, which is the first integer that Yessenin-Volpin would say doesn’t exist?

Yessenin-Volpin asked Friedman to be more specific.

“Okay, then. Does 2¹ exist?”

Yessenin-Volpin quickly answered “yes.”

“What about 2²?”

After a noticeable delay: “yes.”

“2³?”

After a longer delay: “yes.”

It soon became clear that Yessenin-Volpin would answer “yes” to every question, but would take twice as long for each one as for the one before it.

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

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

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

Greetings from America’s fourth-best city, Seattle, where I’m attending the STOC’2006 conference. I arrived here yesterday from America’s third-best city, Boston, where I visited MIT for a week and gave a talk about The Learnability of Quantum States. (I’ll leave the best and second-best cities as exercises for the reader.)

Since tomorrow’s my birthday, I’ll consider myself free to blog about whatever I feel like today (as opposed to most days, when I blog about whatever the invisible space antelopes tell me to). So without further ado, here’s a question that bugged me for years: why do we need to urinate on a regular basis?

I mean, I understand solid waste perfectly well, and I also understand the need to get rid of urea and the other waste products in urine. But why constantly excrete water, something that humans and other animals regularly die from not having enough of? Why not store the water in the body until the next time it’s needed? From a Darwinian perspective, a regularly-vacating bladder would seem to make as little sense as a toothless vagina.

And yet, after minutes of diligent Wikipedia research, I’ve pieced together what I believe is a complete solution to this pee versus in-pee puzzle.

The short answer is that conserving water, rather than just pissing it away (so to speak), is exactly what our bodies try to do. But one needs to remember that, while feces comes directly from the digestive tract, urine is collected from waste products in the bloodstream. In particular, the kidneys contain permeable membranes whose job is to let wastes like urea through, while keeping the useful stuff (like red blood cells) out. However, as with any other filtration process, it’s difficult or impossible to keep all the water on one side of the barrier.

So what the body does instead is to let the water through, then slowly absorb it back into the bloodstream as needed. That’s why your urine is darker (more concentrated) if you’re dehydrated than if you aren’t. At some point, though, it presumably becomes infeasible to extract more water from the bladder without also letting the toxic wastes back into the bloodstream.

Now, I know what you’re thinking. You’re thinking, “why isn’t my urine always dark? In other words, why don’t I always absorb as much water as possible back into my bloodstream, whether I’m dehydrated or not? Why not save the water for a (non) rainy day?”

Aha, I’ve got an answer to that one too. Besides excreting wastes, another function of urine is to maintain a homeostatic balance between water and sodium in the blood. If there’s too much water (say, because you just drank six beers), your blood will be too thin, which can cause brain damage (completely apart from the other effects of the beer). Ideally, your body would store the excess water separately from the blood — and again, that’s exactly what it tries to do, but your bladder is only so big.

In summary, if you think through what my “in-pee” solution would actually entail, it turns out to be almost identical to the “pee” solution that Nature actually adopted. One might even say that pee = in-pee.

[Note for harping relatives: now do you understand why I didn’t go to medical school?]

Follow

Sorry for the long delay; I’m recovering from a cold. Thankfully, nothing like my Canadian-muskox-strength cold in October, but still enough to keep my brain out of service for most of the week. On the positive side, I now have a week’s worth of websurfing to share with you.

What’s as fast-paced as Tetris or Pac-Man, playable for free on the web, and willing to tell you whether you harbor hidden biases against blacks, gays, women, or Jews? Why, the Implicit Association Test, developed by psychologists Mahzarin Banaji, Tony Greenwald, and Brian Nosek. If you haven’t played it yet, do so now — it’s fun! Do you take longer to match African-American faces with words like “peace,” “love,” and “wonderful” and Caucasian faces with words like “bad,” “awful,” and “horrible” than vice versa? Yes, if you’re like 88% of white Americans and — interestingly — 48% of black Americans. (Philip Tetlock, quoted in this Washington Post article, comments that “we’ve come a long way from Selma, Alabama, if we have to calibrate prejudice in milliseconds.”) While I’m ashamed to be part of that 88% statistic, I’m also relieved that, even at an involuntary, subconsious level, I apparently harbor no bias at all against Asian-Americans or gays.

While browsing Wikipedia (Earth’s largest procrastination resource), I came across the following “Freedom House” world map, which labels each country as “free,” “partly free,” or “not free” depending on how it scores on various indices of voting rights, free speech, etc.

I have one beef with this map: I think there should be a little red dot over Berkeley, California.

On an equally important note, while reading the Wikipedia entry for bear (don’t ask), I came across my favorite paragraph in the whole encyclopedia:

In a chance encounter with a bear, the best course of action is usually to back away slowly in the direction that you came. The bear will rarely become aggressive and approach you. In order to protect yourself, some suggest passively lying on the ground and waiting for the bear to lose interest. Another approach is to constantly maintain an obstacle between you and the bear, such as a thick tree or boulder. A person is much more agile and quick than a bear allowing him or her to respond to a bear’s clockwise or counter-clockwise movement around the obstacle and move accordingly. The bear’s frustration will eventually cause disinterest. One can then move away from the bear to a new obstacle and continue this until he or she has created a safe distance from the bear.

Lastly, Reuters reports on an interview in which Bill Gates discusses why he hates being so rich. My mom tells me that, when I visit Microsoft Research a few weeks from now, I should help ease Gates’s burden by demanding immediate reimbursement for my travel expenses.

Follow

So it seems that Borat — the racist, misogynist, khrum-grabbing “reporter” from Da Ali G Show — has become a serious public relations problem for the former Soviet Republic of Kazakhstan. See here for an old New Yorker piece, and here for the latest on this important story.

Respek.

Follow

From Discovery News comes a report that Bernardo Provenzano, the recently-arrested “Boss of Bosses” of the Sicilian Mafia, was finally caught because he relied on an encryption system that consisted of ….. [cue the opening notes of The Godfather theme song] ….. adding 3 to the numerical value of each letter. Apparently this has really been a bad week for evil masterminds in Italy.

Follow