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