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?

This is San Francisco

A truck selling mini-cupcakes is parked in the Castro and doing business. It has its Twitter feed printed on the side. By subscribing to the mini-cupcakes truck Twitter feed, you can know in advance when it’s in your neighborhood. Or, if so inclined, you can follow it around the city.

A large man with a tiny dog looks at the cupcakes, then he turns to the tiny dog. “Would you like a cupcake?” he asks the dog, “remember when you had cupcake last time, you liked it.” The dog is not making eye contact with the man. “So, do you want a cupcake, or not? Tell me.”

Homomorphic Encryption

Academic Kakistocracy

Via Izabella Laba and Crooked Timber, I have found this very interesting book review by Scott McLemee of Diego Gambetta’s book Codes of the Underworld: How Criminals Communicate.

Gambetta, a professor of sociology at Oxford, has studied the problem of trust from a game-theoretic perspective, and he considers the issue of signaling in trust games. Signaling is a process in which a party in a game-theoretic setting indicates that he is going to follow a certain strategy. For example, it is well known that a way to win a game of chicken is to visibly rip off your steering wheel and wear a blindfold. Then your opponent will see that there is no way you can steer, and so he will steer. (Cf. Bush administration foreign policy.)

In the book, Gambetta considers trust in criminal organizations, in which one cannot rely on the rule of law to enforce compliance. He posits that a signaling strategy for members of crime organizations is to signal incompetence; the logic being that if you are unable to do anything else, then you are not going to try to go ‘legit’ and so (i) you are not a threat to the businesses that you are shaking down of eventually becoming a competitor, and (ii) you are reliant on the crime organization to provide for your livelihood and so you are not going to antagonize it.

Perhaps tongue-in-cheek, Gambetta goes on to explain how this applies to Italian academia. I don’t have to book, so I quote McLemee as he quotes Gambetta:

Gambetta argues that something similar takes place among the baroni (barons) who oversee the selection committees involved in Italian academic promotions. While some fields are more meritocratic than others, he says, the struggle for advancement involves a great deal of horse trading. “The barons operate on the basis of a pact of reciprocity, which requires a lot of trust, for debts are repaid years later. …The most powerful figures in this system, says Gambetta, tend to be the least intellectually distinguished. … “… and this is what is the most intriguing, they do not try to hide their weakness. One has the impression that they almost flaunt it in personal contacts.” … Gambetta argues that the cheerful incompetence of the baroni is akin to the mafioso’s way of signaling that he can be “trusted” within his narrowly predatory limits.

“Being incompetent and displaying it,” he writes, “conveys the message I will not run away, for I have no strong legs to run anywhere else. In a corrupt academic market, being good at and interested in one’s own research, by contrast, signal a potential for a career independent of corrupt reciprocity…. In the Italian academic world, the kakistocrats are those who best assure others by displaying, through lack of competence and lack of interest in research, that they will comply with the pacts.”

The comments at Crooked Timber are also worth reading.

Anthony Bourdain is my new hero

He won’t serve me a cruelty-free tomato, but he’ll serve me a delicious one. And, after dinner, I am on my own.

Alice Waters in full self-parody mode is also priceless. (Hot dogs from grass fed cows?)

Good Reads

Arora, Barak, Brunnermeier and Ge have a new paper showing that it is possible to construct “toxic” financial derivative products such that detecting the bad assets is computationally intractable and even proving that a fraud has been committed is impossible. The paper gets a mention in BoingBoing.

The book “Concentration of Measure for the Analysis of Randomized Algorithms” by Dubhashi and Panconesi is out, and is fantastic.

It starts with the basic Chernoff-Hoeffding bounds: if are independent bounded random variables, each ranging in , then

and similar bounds hold also if the have bounded variance.

In many applications, however, one may have to deal with random variables which are correlated, and with operations that are more complicated than sums. For example, suppose we want to prove that there are expanding -regular graphs. Then we may try to apply the probabilistic method, and generate a -regular graph by picking random matchings and taking the union, then showing that for every cut , and every subset of vertices, the probability that the set of vertices is non-expanding is much less than , so even summing over all sets we have probability less than one that the graph is non-expanding. The difficulty is how to reason about the number of edges leaving a set of size in a process in which we pick random matchings. Each of the edges we generate has probability of leaving the set, but these events are not independent.

Usually, Azuma’s inequality is powerful enough to deal with such dependencies and recover a bound. In many interesting cases, however, the assumptions of Azuma’s inequality are not met, and one has to work with more powerful tools, such as Talagrand’s inequality, which is also covered in the book. Finally, in extreme cases, one may have to resort to log-Sobolev inequalities, which I have never had a chance to understand so far, and even they get a very clear treatment.

The book has its quirks. Lemma 2.3, for example, has a handwritten proof, attributed to Anupam Gupta’s penmanship.

Lies, Damn Lies, and Life Expectancy

“[that life expectancy in Canada is higher than in the USA] is to be expected, Peter, because we have 10 times as many people as you do. That translates to 10 times as many accidents, crimes, down the line.” Bill O’Reilly

via Good Math, Bad Math

Many Happy Returns

The PRC celebrated its 60th birthday on Thursday. After the many man-made disasters of the 1950s, 60s and 70s, the quality of life of apolitical Han Chinese living in big cities has been improving dramatically in the past seventeen years. Now if only they can reduce pollution, rein in corruption, establish an independent judiciary, allow freedom of expression, religion, and association, reverse the ethnic and cultural dilution of minority regions, and lift the quality of life of rural areas, the 100th birthday will be a truly joyous occasion.

This is the funniest commentary I have found on the festivities. The references to Hu Jintao will not make sense unless you watch this video

Bob Herbert on UC Berkeley

Tomorrow’s New York Times has an op-ed by Bob Herbert on the funding crisis at U.C. Berkeley. He makes the important points about the uniqueness of Berkeley in giving top-quality education (and a good chance to move on to grad school) to students of very diverse backgrounds, serving working class and middle-class students like no other top university. He also makes the following, very important, point

[The changes caused by the budget crisis] would most likely hurt students from middle-class families more than poorer ones. Those kids are caught between the less well-off, who are helped by a variety of financial aid programs, and the wealthy students, whose families have no problem paying for a first-class college education.