Dominant Strategy?

STOC Registration fee for non-members of SIGACT is $100 more than the registration fee for SIGACT members. SIGACT membership is only $18. What gives?

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

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.