Expert, Shmexpert

About a week ago, the email server used by climate scientists at the University of East Anglia was hacked, and emails dating as far back as 1996 were posted online.

National Review, the conservative magazine, “asked its environmentalism experts to weigh in” on the implications of the leak. One of the experts is Henry Payne, billed as “an editorial writer and cartoonist with the Detroit News.” According to wikipedia, Mr. Payne is a history major.

As a computer scientist and Chinese food enthusiast, I believe I am more qualified than Mr. Payne to discuss climate change, and I hope National Review will consider asking me to write a piece on the subject next time.

Update: in the next episode of the series everybody is an expert, Sarah Palin writes an op-ed on climate change for the Washington Post. “I’ve always believed that policy should be based on sound science, not politics,” writes Sarah Palin. I am looking forward to zombie Ronald Reagan‘s take on the matter.

The Money Troubles of the University of California

Last week, at BATS, a colleague from a research lab was asking me what exactly is going on with the budget of the University of California. The conversation went like this:

“How much does the state contribute to the UC Budget?”

“About a third”

“And how much has the state contribution decreased this year”

“About 20%”

“So that’s about 6% of the total budget. How come they need to cut salaries by 8% and increase tuition by 32% in order to recover from a 6% budget cut?”

How come, indeed? Over the weekend I have tried to make sense of this question, but unfortunately it is very difficult to make sense of the UC budget, not to mention that the numbers in the 2008-09 budget document from the office of the president are quite different from the number in the 2008-09 audit.

Here is, however, what I have understood so far:

The Berkeley Way

On Thursday, the Regents of the University of California met at UCLA and voted to increase student fees (tuition) by about 32%. There will be a 15% increase this Spring, and another 15% increase in Fall 2010.

Friday, while the theoreticians where at the Bay Area Theory Symposium, was a day of protest on campus, which showed the best and the worst of Berkeley.

Protesters went around campus buildings pulling fire alarms (bad), resulting in my colleague David Tse teaching probability and combinatorics outside in the rain (very good — or as one of the youtube commenters put it, “epic WIN”):

A group of about 40 students tried to occupy some rooms of Wheeler hall, the English department building, and up to 2,000 students showed up outside the building on a cold (by California standards) and rainy day (very good).

A few days of occupation at Wheeler would have probably received ample news coverage and would have publicized the fundamental fact of the present situation: that the University of California, and U.C. Berkeley in particular, will lose its character of public university if the funding crisis persists, and that the budget cuts are not free money for the tax-payers; they will have real negative consequences of hundreds of thousands of middle-class families.

Yet, the administration (very bad) instead of supporting the students sent the campus police first, and then police in riot gear from the Berkeley police department and the Alameda county’s Sheriff’s force (and possibly Oakland police, whose presence is disputed) to arrest the would-be occupiers and beat up the crowd outside Wheeler.

It’s anybody’s guess what the Chancellor might have been thinking.

The Large Deviation of Fourwise Independent Random Variables

Suppose are mutually independent unbiased random variables. Then we know everything about the distribution of

either by using the central limit theorem or by doing calculations by hand using binomial coefficients and Stirling’s approximation. In particular, we know that (1) takes the values with probability each, and so with constant probability (1) is at most .

The last statement can be proved from scratch using only pairwise independence. We compute

so that

It is also true that (1) is at least with constant probability, and this is trickier to prove.

First of all, note that a proof based on pairwise independence is not possible any more. If is a random row of an Hadamard matrix, then with probability , and with probability .

Happily, four-wise independence suffices.

Distinguishers from linear functions

In the last post we introduced the following problem: we are given a length-increasing function, the hardest case being a function whose output is one bit longer than the input, and we want to construct a generator such that the advantage or distinguishing probability of

is as large as possible relative to the circuit complexity of .

I will show how to achieve advantage with a circuit of size . Getting rid of the suboptimal factor of is a bit more complicated. These results are in this paper.

Efficiently Correlating with a Real-valued Function and Breaking PRGs

Suppose we have a length-increasing function , which we think of as a pseudorandom generator mapping a shorter seed into a longer output.

Then the distribution of for a random seed is not uniform (in particular, it is concentrated on at most of the elements of ). We say that a statistical test has advantage in distinguishing the output of from the uniform distribution if

If the left-hand side of (1) is at most for every computable by a circuit of size , then we say that is -pseudorandom against circuits of size , or that it is an -secure pseudorandom generator.

How secure can a pseudorandom generator possibly be? This question (if we make no assumption on the efficiency of ) is related to the question in the previous post on approximating a boolean function via small circuits. Both questions, in fact, are special cases of the question of how much an arbitrary real-valued function must correlate with functions computed by small circuits, which is answered in a new paper with Anindya De and Madhur Tulsiani.

Approximating a Boolean Function via Small Circuits

Suppose that is an arbitrary boolean function, and that we want to construct (or rather, show the existence of) a circuit of size that approximates as well as possible. How well can we hope to do?

Certainly, we can get a -size circuit that computes on of the inputs, by either choosing the circuit that always outputs 0 or the circuit that always outputs 1.

Also (ignoring factors), we can construct a circuit that has hardwired the values of at places, and then outputs always zero or always one (whichever is better) on the remaining inputs. This circuit will work on a

fraction of inputs, and this seems like the best we can hope for.

We may then try to prove the optimality of the above construction by considering a random function , using the Chernoff bound to show that, for a fixed circuit of size , and have agreement less than except with probability less than , and then taking a union bound over the roughly circuits of size . (It’s actually , but we said we would ignore .) Unfortunately, this calculation only leads us to a proof that, in general, we cannot hope to compute a random function on more than a

fraction of inputs using a circuit of size . This is a disappointment because we were hoping to prove that (1) was tight.

If we think about it, however, we see that the bound in (2) is actually typically achievable for a random function: partition the possible inputs into blocks, each of size . (Based, for example, on the value of the first bits.) Now, the value of in each block are just a sequence of random bits, so, with constant probability, there is either an excess of ones or an excess of zeroes. For each block, hard-wire into the circuit the majority value of among elements of the block. Clearly we are getting an fraction of inputs correct, and our circuit has size .

What about general functions? Is it possible to do better than (1) for every function?