You are currently browsing the monthly archive for March 2011.

The New York times has an interesting article (read it while you can) about MIT’s effort in the past 10 year to tackle discrimination against women, initially in the School of Science and then over the entire university.

A recently released report points out the progress, as well as interesting problems that remain open. For example (the following sentence is not attributed and does not appear in quotes):

Despite an effort to educate colleagues about bias in letters of recommendation for tenure, those for men tend to focus on intellect while those for women dwell on temperament.

This is very interesting if true. In principle, it is a testable assertion: one could take a large sample of recommendation letter, remove all direct reference to gender (she/her/ first names, etc.), use half of them to train a machine learning algorithm, and then see if the algorithm is able to guess better than randomly which of the remaining letters are for women and which are for men. (Among other things, the learning algorithm would pick up a higher frequency of words about temperament, if such comments were really more frequent about women.)

The article also points out societal issues on which MIT has little control but that are important, for example the fact that child care and family-work balance are seen as women issues, rather than parents issue.

In a way, it is good that now these are the kind of issues that remain to be addressed, compared to the outright discrimination that was determined to have occurred in a mid-1990s review, and compared to what happens in other fields and/or in other institutions.

Meanwhile, Mark Krikorian, in National Review, writes that the United States intervened in Libya because the women in the administration “nagged” Obama into doing so, and Mr. Krikorian worries about what foreigners will think of us because of it. Note the classy title of his post.

Edited to add: the top two students in my class CS261 were both women.

Despite no popular demand, I have collected all the notes from CS261, the course on algorithms for combinatorial optimization problems that I taught in the past term, in one pdf file, available here, and I have created a new page to collect links to my lecture notes.

For the occasion, I have also posted a single file containing the notes from my Spring 2009 class on the foundations of cryptography. As explained in the foreword to the crypto notes, they use a definition of CCA-security that is wrong, that is, a definition that is weaker than the standard one in a way that actually allows potentially dangerous attacks. The weaker definition, however, is much simpler to define and work with, and I think it is pedagogically justified. I believe that everything else in the notes is consistent with standard definitions. As far as I know, the notes are the only place in which one can find a concrete-security treatment of zero knowledge.

In which we show how to use expert advice, and introduce the powerful “multiplicative weight” algorithm.

We study the following online problem. We have {n} “experts” that, at each time step {t=1,\ldots,T}, suggest a strategy about what to do at that time (for example, they might be advising on what technology to use, on what investments to make, they might make predictions on whether something is going to happen, thus requiring certain actions, and so on). Based on the quality of the advice that the experts offered in the past, we decide which advice to follow, or with what fraction of our investment to follow which strategy. Subsequently, we find out which loss or gain was associated to each strategy, and, in particular, what loss or gain we personally incurred with the strategy or mix of strategies that we picked, and we move to step {t+1}.

We want to come up with an algorithm to use the expert advice such that, at the end, that is, at time {T}, we are about as well off as if we had known in advance which expert was the one that gave the best advice, and we had always followed the strategy suggested by that expert at each step. Note that we make no probabilistic assumption, and our analysis will be a worst-case analysis over all possible sequences of events.

The “multiplicative update” algorithm provides a very good solution to this problem, and the analysis of this algorithm is a model for the several other applications of this algorithm, in rather different contexts.

Read the rest of this entry »

This week the New Yorker has a profile of Magnus Carlsen, a young Norwegian chess player that is currently the #2 ranked player in the world (he has been #1 in the past).

The article discusses how the game has been changed by the availability of computer programs that are now unbeatable even by the top players, and the fact that the younger generation of players (but not Carlsen) grew up playing against computer programs. The following quote was interesting:

Computers have no skills and they have nothing approaching intuition. Carlsen finds their games inelegant, and complains about “weird computer moves I can’t understand,” whereas in talking about his own game he speaks of achieving “harmony” among the pieces on the chessboard, and even of “poetry.”

It struck me that we could see in our lifetime computer programs becoming better than human mathematicians in raw technical skills, and that the above quote could reflect our future attitude toward proofs found by computers. “Where is the statement of this lemma coming from?”, “this argument has no elegance!”, and so on.

So your prime minister pays underage girls for sex, but you have given the word Enrico Fermi, Sophia Loren, Italo Calvino, Federico Fellini, Luigi Pirandello, early algebraic geometry, neorealismo and futurismo. I’ll call it a tie.

(Related memory: one night during STOC 1997 in El Paso, a group of theoreticians that included Daniele Micciancio and myself goes to Juarez, and walks into the one bar that didn’t seem to have prostitutes sitting outside. Daniele and I are talking, and the man sitting next to Daniele stares at us oddly. Finally, he asks what language we are talking in. “Ah, Italy,” he then says, “Paolo Rossi! Edwige Fenech!”)

In which we prove properties of expander graphs.

Read the rest of this entry »

In a demonstration of impeccable taste, ACM bestowed this year’s Turing Award on Leslie Valiant, for several contributions, including the development of computational learning theory (the foundational theory of machine learning) and of a theory about the complexity of combinatorial counting problems.

It is also notable that the Knuth Prize maintains a perfect record at predicting future Turing awards for theory.

In which we introduce online algorithms and discuss the buy-vs-rent problem, the secretary problem, and caching.

In this lecture and the next we will look at various examples of algorithms that operate under partial information. The input to these algorithms is provided as a “stream,” and, at each point in time, the algorithms need to make certain decisions, based on the part of the input that they have seen so far, but without knowing the rest of the input. If we knew that the input was coming from a simple distribution, then we could “learn” the distribution based on an initial segment of the input, and then proceed based on a probabilistic prediction of what the rest of the input is going to be like. In our analysis, instead, we will mostly take a worst-case point of view in which, at any point in time, the unknown part of the input could be anything. Interestingly, however, algorithms that are motivated by “learn and predict” heuristics often work well also from the point of view of worst-case analysis.

Read the rest of this entry »

In which we define and analyze the zig-zag graph product.

Read the rest of this entry »

The Stanford theory group is starting a once-a-term distinguished lecture in computer science, in memory of Rajeev Motwani.

We were very happy that Moses Charikar agreed to deliver the inaugural lecture, which will take place tomorrow, Thursday, at 4:15pm, in the Mackenzie Room, on the third floor of the new Engineering Complex. Moses will talk about dimension reduction in L1.

If you are coming, please also join us at 3pm for wine and cheese at the second-floor library in the Gates building.

Parking is free everywhere after 4pm.

More about the goings on at Stanford: theory.stanford.edu

a

Follow

Get every new post delivered to your Inbox.

Join 263 other followers