A strategic vote from the heart

So it came down to two issues for me -- the level of detail and thoroughness of various plans (esp. universal health care) and the candidates' stand on (the Iraq) war.

Clinton clearly has the better resume on the first count -- meticulous and well-crafted plans all around, reflecting her experience and how deeply she cares about issues. For example, see this Krugman article (timed slightly poorly, coming as it did the day before Super Tuesday, compared to the Kennedy family endorsement, which gave voters some time to let it sink in) for a nice analysis on how the Clinton health care plan would cover nearly twice as many people as the Obama plan would.

On the Iraq war front, Obama had the clarity of thought to step up in October 2002 (on Gandhi's birthday, in fact) and call it a dumb and rash war, adding:

I know that even a successful war against Iraq will require a U.S. occupation of undetermined length, at undetermined cost, with undetermined consequences.

I know that an invasion of Iraq without a clear rationale and without strong international support will only fan the flames of the Middle East, and encourage the worst, rather than best, impulses of the Arab world, and strengthen the recruitment arm of al-Qaeda.

In a matter with complex details, Obama (and his team) didn't possibly have the best analyses of their health care package, but that's something that is fixed at a smaller cost: the studies of the kind Krugman points out might lead to Obama's plan being revised, Obama might simply incorporate several elements of Clinton's health care proposal, etc. However, in a matter of international significance, in a matter that involved serious cost (and not just in dollars) to the country, Hillary Clinton failed, where the junior senator from Illinois displayed tremendous foresight and levelheadedness.

For this reason, I voted for Obama.

The vote is also strategic, to some extent: my thinking is that McCain (or any of the other Republican candidates) might find Hillary an easier opponent to defeat simply because I think that America is less racist than it is sexist. And that is an outcome that I wish to avoid entirely.

How to increase your odds of winning the Turing Award

Consider working in some area related to the broad theme of correctness:
formal verification of software/hardware, model-checking, program correctness, program specifications, etc. I can count 8-10 Turing awards in these fields (algorithms/complexity is up there as well, though not in recent years).

The 2008 (or is it 2007?) A. M. Turing award recipients have been announced -- Ed Clarke, E Allen Emerson, and Joseph Sifakis have received the award "[f]or [their] role in developing Model-Checking into a highly effective verification technology, widely adopted in the hardware and software industries."

Congratulations to the winners!

It is clear that the theme of correctness of programs and hardware, etc., is fundamentally important to the evolution of CS into a sound scientific discipline. However, an outsider to these fields (I should know - my programs and theorems have bugs more often than I'd like), I must complain that I find it hard-pressed to find examples of work by these Turing award winners that have made it to the "mainstream" (say, a typical Masters or a strong undergraduate program in CS). This is the opposite of the situation in algorithms/complexity (despite some counterexamples like Yao's work on pseudo-randomness).

Where will Edwards supporters go?

John Edwards did a very responsible thing by dropping out of the contest for the Democratic party nomination. He had little chance of winning the nomination, but held the support of a non-trivial fraction of Democratic voters (see the NYT Dem Election Guide for fractions that go up to 17% in NH and SC). Given the tight race between Senators Clinton and Obama, it may very well be the case that where the Edwards supporters go will be a decisive force in the contest.

In this article praising Edwards for his "unabashed populism" and "campaign based on ideas", Paul Krugman explicitly articulates this question:

And so Mr. Edwards won the arguments but not the political war.

Where will Edwards supporters go now? The truth is that nobody knows.

Here is one crude analysis of where they'd go:

Look at Jan 2008 Google Trends for "clinton obama -edwards" -- (I think) this means volume of queries that mention Clinton and Obama but not Edwards -- this could be taken as a measure of how many people are comparing Clinton and Obama, without mentioning Edwards. Now look at the Trends graph for "obama edwards -clinton" (queries that mention Obama and Edwards, possibly comparing the two) and for "clinton edwards -obama". The interesting fact is that when you look at all three graphs or just the latter two graphs (for a closer view) you'll notice that there are a lot more queries that "compare" Obama and Edwards than there are queries that "compare" Clinton and Edwards. This "implies" that a lot more of Edwards supporters will likely vote for Obama than they would for Clinton.

So you heard it here first - be sure to pat my back after Super Tuesday :-)

Of course, Edwards supporters might be Edwards supporters for a variety of reasons (can't stand a woman being President, can't stand an African-American being President, don't like Clinton, like his anti-poverty policies, much better haircut than either of the other candidates, etc.), and this "analysis" doesn't take into account any of these -- it's just a crude interpretation of relative query volumes. However, to the extent that search queries are a reflection of the society's thinking at large, this just might be a sound basis to predict an Obama victory.

ps: as I type this post on Blogger, its built-in spell-checker stupidly underlines the word "Obama" (but not "Clinton" or "Edwards") -- little does it know...

Two Americans

One of my favorite "lateral thinking puzzles" that I pose to young children is this:
Two Americans are standing in front of the main library in London; one of them is the son of the other one, but the second one is not the father of the first one -- how could this be?

Surprisingly, the fraction of girls that solve this is roughly the same as the fraction of boys that solve this, and in both cases, the fraction is low.

This article by Gloria Steinem in the New York Times revisits this bias in the context of the elections for the Democratic party's Presidential candidate, and includes this gem of a sentence: "...he is seen as unifying by his race while she is seen as divisive by her sex".

Softball data

From an IM conversation...

...
Ravi: Next time you write a paper with simulations, you can cite these guys

Sent at 11:05 AM on Saturday
...

Klawe on math education, teaching...

An op-ed piece in this week's Mercury News by Maria Klawe. See (Listen to?) also this interview by Klawe.

You See Berkeley

This had to happen, right?

Modern Health Science

Gotta love it...

Gödel Prize, Naturally

Sasha Razborov and Steve Rudich have been chosen as this year's Gödel Prize winners for their brilliant work on Natural Proofs. Congratulations!

So what are natural proofs?

A computer scientist who did some work in complexity theory once quoted someone: "if you wish to separate NP from P, it is not NP that you need to understand, it is P that you need to understand".

The natural proofs argument says: if you're going to do that, watch out -- you might need deeper thoughts than you're capable of.

Let's say we don't like a circuit complexity class C - we think it's too weak in its computational power (think AC^0, nonuniform versions of Logspace or P). We go into our laboratory, cook up deep thoughts about C, and come up with "nutshell" observations like: if a Boolean function can be computed by C, then it can't be too special -- in fact, it must have property P. [Running example: if a function can be computed by an AC^0 circuit family, it can't be "too sensitive" (the function's value on a random point of the Boolean hypercube must agree with all but polylog many neighbors of the point, whp)]. Then we think a little bit more, and say, "Hey, but wait, here's this function g that doesn't have property P" [Running example, contd: The parity function is like a sweet-tooth on a dentist's chair -- too damn sensitive.] And voila, we've shown a lower bound against class C.

All's well, but now let's go and analyze our thought process, specifically, let's try and ask: what's the computational complexity of our deep thought that led to the lower bound? In other words, what's the computational (say, circuit) complexity of the property P? Suppose that P(f), a function on N = 2^n bits, can be computed by some circuit of type/complexity D.

On the other hand, by virtue of the fact that we were able to succinctly describe property P in one or two English sentences, it ought to be the case that a random Boolean function almost surely won't have property P. Since we're supposed to be formal mathematicians, let's not handwave, instead let's turn this into an assumption: let's assume that P(f) is False for a random Boolean function f wp. 1 - o(1).

The punchline of this kind of dont-attempt-early-in-the-morning-before-a-pot-of-Earl-Grey thinking is that if class C is capable of producing pseudorandom functions that can fool class D, then this scenario is impossible -- after all, given a function from the pseudorandom ensemble of functions produced by class C, what is the class D circuit to do? Since it can tell that the function has property P, it can identify that it was manufactured in the C-factory, something it wasn't supposed to be able to (by defn. of pseudorandom function generator)...

Moral of story, illustrated: if there's a pseudorandom function generator computable by polynomial-sized circuits that can fool circuits of size poly(2^n) (or even 2^n^eps), then the property P that you need to come up with to prove a lower bound against polynomial-sized circuits needs to be more complex than can be recognized by a circuit of size 2^n^eps... whew, there I said it in one sentence. In English: to separate C1 from C, it might be futile to pick on C and try and find some human-interest property of all functions computable in C and hope that something in C1 doesn't have that property... you might actually have to be smart and find weirdo functions (like the diagonal language, complete languages, hard-on-average problems) in C1 that are not in C for less blatant reasons.

[Technical clarification of the previous sentence: Imagine a circuit T with two inputs, an n-bit string x, and an n^k-bit string s. Via T, one obtains a collection of functions T_s(x) by sticking in all possible "seeds" s. Suppose there is some fixed c (much smaller than k, naturally) such that any circuit of size 2^{n^c} that takes 2^n inputs cannot tell the difference between a random function from the collection {T_s(.)} and a totally random function. Then what we have on our hands is a polynomial-sized-circuit-computable-pseudorandom-function-generator, the kind of thing Moni Naor might be willing to talk about before breakfast, but one that you shouldn't try making at home.]

Next post: the most complex lower bound property I've seen..