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

A Berkeley Journalism Professor questions Nutrition Science

I wrote (long ago) about the importance of breaking an assumption in doing science. In today's NYT, Berkeley journalism professor Michael Pollan questions the analytical approach to food (aka nutritionism). I found the first sentence in the following excerpt to be especially quote-worthy, and the genesis of this (a tad too long) article. One of the more thought-provoking essays in The Times in recent memory.

In the case of nutritionism, the widely shared but unexamined assumption is that the key to understanding food is indeed the nutrient. From this basic premise flow several others. Since nutrients, as compared with foods, are invisible and therefore slightly mysterious, it falls to the scientists (and to the journalists through whom the scientists speak) to explain the hidden reality of foods to us. To enter a world in which you dine on unseen nutrients, you need lots of expert help.

But expert help to do what, exactly? This brings us to another unexamined assumption: that the whole point of eating is to maintain and promote bodily health. Hippocrates’s famous injunction to “let food be thy medicine” is ritually invoked to support this notion.

Now that I've started blogging again after a year's hiatus, there's no telling where this might lead...

Earth Day Quiz

Answers tomorrow, on Earth Day, together with pointers to some Google goodies...

(0) What is E85?

(1) How many 16-oz bottles of bottled water does the average American consume each year?

(2) Why does Vinod Khosla (co-founding CEO of Sun Microsystems and venture capitalist extraordinaire) want California to add a new tax?

(3) Is it a coincidence that this (clickable) front-page ad from GM on nytimes.com bears colors from the Brazilian flag?

(4) Who is Vijay V. Vaitheeswaran?

(5) What is the single largest energy consuming appliance in a typical household?

Science du jour...

NYT has this article on the "science of services", whatever that means.

An ex-colleague of mine wonders: why is this article in the Business section of NYT?

I won't whine (in this post, anyway) about why this is not a science, but will merely lament NYT's lack of critical reporting: there's no discussion of operations research, industrial engineering, "management science", and other mathematical/engineering/business school disciplines (sciences and non-sciences) that subsume this field of deep scientific inquiry many times over.

Most Emailed-About Theory Geek

Geom
Blog
Makes it
To a most
Emailed article.
Congratulations, Suresh V!

Ashamed to be Indian

I am usually proud about the culture, heritage, yada yada of India - being the largest democracy, more or less peaceful coexistence of numerous languages, religions, an advanced intellectual core, tons of entrepreneurship, etc. etc.

This I fail to understand: a popular movie actor, whose last movie was probably a decade or two ago, dies at age 77 of natural causes, and his fans and others indulge in looting and violence and general unrest. At least five people have been killed following this burst of violence. And they threw stones at a Microsoft office in Bangalore. The technology capital remains shut for two days. This is absolutely idiotic. I fail to see even a sliver of logic behind this.

NYT's new design sucks

Decidedly more "content" (links to blogs, etc.), but I find the new design ugly and not user-friendly. Starting with the smaller font, longer pages, ad-heavy top screen, etc., I think I am going elsewhere for my hourly news fix. Both The Times and the BBC have better layout and navigation, I think. BBC even has a sidebar that gives links to the same story in other major newspapers of the world, a definitely cool feature: this site "gets" the web -- your overall value is not just a function of the content you provide but also a function of the links you provide.

Gapminder

Recently at Google, I got to watch parts of a very interesting "Tech Talk" by folks from Gapminder.org -- "... a non-profit venture for development and provision of free software that visualise human development. [This is] done in collaboration with universities, UN organisations, public agencies and non-governmental organisations."

The talk had really cool animations of time-series data about various correlations between health and income of populations across the globe. The talk had a strangely interesting kind of self-reference: it was as much about the presentation technology as it was about the data being presented, not unlike, but richer in content than, a power point presentation about powerpoint, or a coffee table book about coffee tables...

You can view the Gapminder talk in its entirety at Google Video (about 70 minutes).

First we had to factor prime numbers...

and now, we need to factor numbers to generate cryptographic keys... (from "2020 Computing: Champing at the Bits" in Nature magazine's 2020 Future of Computing Web Focus. This kind of pedantic peeve aside, the web focus has some pretty interesting articles.

In fact, quantum computers are currently little more than two-trick wonders. In 1994, Peter Shor, now based at MIT, devised an algorithm that would allow quantum computers to factor numbers exponentially faster than conventional computers. Factorization is important in cryptography, where it is needed to make and break keys. And in 1996, Lov Grover, who is now at Lucent Technologies in Murray Hill, New Jersey, unveiled a quantum algorithm that can greatly speed up database searches.

Break an assumption

Every time I hear or read something about the story of how the Wright brothers built the first airplane, I find it inspiring in a new way. Yesterday, I watched a NOVA program on (the recreation of) the Wright brothers' Model B airplane. Here's an excerpt from the transcript:

TOM CROUCH: The great problem, really, that, uh, flying machine experimenters in the late 19^th and early 20^th century faced was the issue of control, and it was the Wright brothers' recognition of the fact that the control issue was going to be critical that initially set them apart from virtually everyone else.

NARRATOR: While most engineers assumed that a successful aircraft would need to be inherently stable, as bicycle builders, the Wrights made their living building vehicles which were inherently unstable. They knew that a bicycle was stable only if the rider kept it under control.

TOM CROUCH: Most other experimenters in the field assumed that the control issue was going to be so difficult that the best approach they could take was to build an airplane that had maximum sort of automatic stability, an airplane that would fly in a straight line until the pilot made some sort of control input to change its direction, and then it would continue going in a straight, straight line again.

NARRATOR: Early designers imagined aircraft as a kind of flying boat. If wind or waves rock a boat, it should be able to right itself. Instead of a boat, the Wrights thought of their flying machine more like a bicycle and rider: if the bike rolled to the left or right it was the job of the rider to keep it upright. The Wrights didn't worry about building automatic stability into their airplanes anymore than they designed their bicycles to go without riders.

TOM CROUCH: As cyclists, the Wright brothers said to themselves, "Well, if you tried to describe the act of riding a bicycle to someone who'd never seen one, um, what? You're going to roll down the street in this thing with two narrow rubber tires, and you're going to be balancing while you're operating the handle bars."

It would sound like the sort of feat that only the world's greatest acrobat could accomplish, and yet, they knew that once you learn how to ride a bike, you internalize that, and it becomes perfectly natural and instinctive; you don't even think about it. And they were sure that the same thing would be true of a flying machine.

In other words, they broke an unstated, implicit, assumption that was prevalent in their field. Geniuses often do. In computer science, this is probably a good algorithm design principle - check your assumptions, write them down. The space of possible solutions might include things that you might fail to consider because of your prejudices. Remember the puzzles "place four marbles that are equidistant from each other" and "two Americans were standing in front of the British Embassy in Buenos Aires - one was the son of the other, but the second one was not the father of the first one - how is that possible?"? In each of these, you might have to break an implicit assumption to get to the solution.

Strassen broke an assumption when he used subtractions in a matrix multiplication algorithm, as did Gill/Rabin/Solovay-Strassen/Carter-Wegman with randomized algorithms, and Codd with relational databases.

Aha! Insight by Martin Gardner has more interesting puzzles, some of which call for breaking assumptions.

So, whatever you're doing, go check your assumptions once more.

Several servings of India...

With President Bush's upcoming visit to India, there's a flood of India-related articles in the American popular media. I was lucky to catch most of a Charlie Rose interview with Prime Minister Manmohan Singh, the man widely credited with reforming India's economy. PM Singh was simply scintillating, in my opinion -- the clear, measured, analytical responses of the economics scholar failed to hide his underlying compassion for India's poor.

According to the Charlie Rose website, you may be able to find/download it at Google Video (free for one day after the airing and $0.99 after that). The rest of week includes more interviews with several prominent members of the Indian administration, business, and journalist communities.

Peter Norvig on Google Research

I have to link to this, right?

Arrgh... Indian Newspapers

Ask anybody who moved to the U.S. from India about what they miss the most about India. After the customary socially-correct responses of family, culture, yada yada, you will hear, nearly uniformly, that they miss the high-quality English-language newspapers in India. While the notion of a "favorite newspaper" will depend on where they come from (e.g., The Hindu is more popular in the South, the Times of India in the west, etc.), almost everyone will tell you how good their coverage of national and international topics are, how some of the sportswriters could create poetry out of a one-day cricket match, how well-thought-out and progressive editorials are, etc.

Indian newspapers, esp. my favorite "The Hindu" (which is totally non-religious, btw), could also be very frustrating. Here is an example. Somebody sued a State Government about an "entrace test", but I find it nearly impossible to figure out what the lawsuit claimed, what the legislation they're talking about is. What I see instead is a morass of legalese, with phrases like "make the writ petition infructuous" and "prayed for an interim injunction restraining the Government from issuing a notification"...

Speaking of esoteric legalese in Indian newspapers, here's a hilarious example of legal language about an overweight ex-actress... why can't they simply write "released on bail"? The story of why she was brought into "judicial custody" itself wasn't very amusing, though -- but you won't be able to figure it out by reading this article. There's just no habit of giving a bit of background to the news stories... I think it worked well in an era when readers were regular subscribers, and if they don't know what an article is talking about, they can reach for the previous day's newspaper. In the Internet era, where you stumble on an article through various means, it is truly frustrating. Evidently, they don't have the habit of placing good hyperlinks, either.

Lovely quote by Stephen Jay Gould

From today's Quotes of the Day:

In science, 'fact' can only mean 'confirmed to such a degree that it would be perverse to withhold provisional assent.' I suppose that apples might start to rise tomorrow, but the possibility does not merit equal time in physics classrooms.

No, I am not about to enter into an Inane Debate about intelligent design. That is too far on the road away from science, past the exit for philosophy, just before the religion rest stop.

I am wondering about provisional computer science theories like P ≠ NP. It seems to me that we're closer to ID people on this than to scientists or even philosophers. Do we even have a philosophical or socio-philosophical reason why this must be true or linked with other deeper philosophical questions? (e.g., If P = NP, then (using reasonable laws of physics) the universe should have evolved a lot faster than it did, or that the future would be a lot closer than it is, etc., or If P = NP, there cannot be free will, or If P = NP, then there would be no poverty in the world, etc.)