Wednesday, July 29, 2009

Implications of a Microsoft-Yahoo Deal for Research?

After months of speculation, the news today is full of reports of a Microsoft-Yahoo deal for search. Here is a CNN article, and I'm sure you can find others.

One thing I've read about the deal is that by using Bing, Yahoo will save on research and other expenses for its own search. Similarly, since Yahoo will focus on the advertising network to monetize the search, perhaps Microsoft will invest less on research there. Of course this is speculative; while I'm sure cost savings will come to mind, I imagine engineering and infrastructure are more obvious place for cost saving cuts than research.

But I am certainly hoping this will not adversely affect the research going on these places, especially at Yahoo, which seems to me to be more at risk (given the company's financial issues over the last several years), and which has really been doing a lot interesting and visible research lately. For example, check out their research blurb on their success at KDD/SIGMOD/PODS. Or check out their blurb on their current featured research project, Similarity Caching.

Let's be clear -- I'm very biased here. My past student Adam Kirsch did a summer internship at Yahoo; my past mentor Andrei Broder is there; I've received some research funding from Yahoo Research and written several papers with researchers there. From what I've seen, I think they're an impressive research organization. Two of their main focus areas are Search and Web Mining and Computational Advertising. I hope that nothing in the deal lessens the importance to Yahoo of supporting and developing research in these areas.

Friday, July 24, 2009

Various Harvard threads

Richard Bradley, author of Harvard Rules as well as other books, has plenty of Harvard related things to write about, including the Henry Louis Gates affair (which I've heard about seemingly nonstop for several days) and the Vanity Fair article, on his blog. And then there's a new Newsweek article on the months-old story of the student who was not allowed to graduate at the ceremony this year because of a purported connection (the nature of which is not, as far as I know, publicly known) to a murder that took place at a Harvard dorm.

The only "positive" news I've seen about Harvard lately is its portrayal as a hotbed of high tech activity in Harvard graduate Ben Mezrich's new book, the Accidental Billionaires, about the building of Facebook. Of course, even that's somewhat tainted, since Mezrich, according to several articles, essentially made up portions of the book.

At this point, I'm hoping that Harvard stops showing up in the press for a while. (And then starts showing up in a more positive light.)

Saturday, July 18, 2009

California Update Part 2

I spent the rest of my California trip visiting Yahoo, Google, and Stanford.

At Yahoo, I got the chance to hang out with my mentor, the ever-busy Andrei Broder, and talk research with Ravi Kumar and Flavio Chierichetti. Flavio is a graduate student of Alessandro Panconsei's; he previously visited Harvard and I got him to work on codes for flash memory, and we've also collaborated on the recent KDD paper On Compressing Social Networks. Flavio's been doing a lot of outstanding work primarily in applied algorithms; he'll be looking for a job/postdoc soon, and I suggest everyone keep their eye out for him.

At Google, I was hosted by Gagan Aggarwal, and gave the talk on An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets. Slides (ppt) are here; they were designed by Favio Vandin and passed to me by Eli Upfal. Highlights included seeing Deborah Weisser (another Berkeley grad school alum who overlapped with me) and Pei Cao (who always asks lots of interesting questions). And one of my TAs from last year -- interning at Google for the summer -- came to the this talk too. OK, I admit, lunch was also a real highlight. Unlike last year, the sushi line was short (indeed, the whole place was quieter than last year -- maybe I came on a less busy day), and they still had a freezer full of specially Google-branded It's It sandwiches.

Finally, I gave the Open Questions in Cuckoo Hashing talk at Stanford, after a nice talk with my always-interesting host, Tim Roughgarden. Sadly, I'd come down with a cold the night before, so it wasn't my best performance, but the audience peppered me with good questions. Again, another TA showed up -- this one just started her PhD in Statistics at Stanford.

Thanks to everyone who came to the talks, and I hope to be out again soon...

Thursday, July 16, 2009

Vanity Fair's Article on Harvard

I'm writing this on my flight back from California, where I've just been reading the August Vanity Fair article on Harvard's endowment situation. (It does not appear to be available online currently.) The cover blurb is Harvard's Big, Dumb Financial Train Wreck, and the actual title seems to be Rich Harvard, Poor Harvard, so you have some idea where it's coming from.

The article has its ups and downs, its mild exaggerations and understatements. But overall it's interesting reading. One interesting point is that it starts and ends with none other than our own Michael Smith, computer science professor currently on loan as Dean of the Faculty of Arts and Sciences. The article begins with Mike calmly addressing undergraduates and trying to forthrightly explain the financial situation. (Of course, the undergraduates are up in arms, insisting on things like no layoffs, as one would expect undergraduates everywhere to do, regardless of the actual situation.) The article ends with Mike talking to the reporter on the way back to Mike's car at the end of the day; the reporter describes a lack of success in otherwise getting information or meetings with Harvard's standard PR organization. (Strangely, I've also multiple times caught Mike heading for home, and chatted with him about various Harvard happenings at those times. He needs to change his car routine.) While this impromptu chat didn't seem to reveal significantly novel information -- Mike's smart enough to keep his cards close to his vest as needed -- it shows Mike talking more openly than one might naturally expect from a Dean in his situation. He's not a "no comment" kind of guy.

This, to me, highlights some of Michael Smith's strengths as a leader. He talks, and he listens. He sees the numbers, and doesn't hide from them, but thinks clearly and calmly about where we go from here. I'm happier knowing Mike's helping steer the ship here. (And I continue to wish him the best of luck.)

The article nails some things squarely. The fall in the endowment will have significant effects. Fewer TAs, fewer support staff, closed libraries, fewer perks all-around for students and faculty, and less money for all sorts of projects and initiatives. All this is, naturally, not good, but perhaps the article overstates the effects all this will have on Harvard as an educational institution. I, for instance, was a Harvard undergraduate in what must now appear to be the dark, dreary days of 1987-1991, when Harvard's endowment was just over 1/10 th the size it was before the crash, and I still liked the place and thought I received a good education. Harvard's resources are still remarkable, and I feel lucky to teach here; I'm sure we'll still manage to provide a high-quality education.

In terms of the question of how we got to this point, the article considers two main thrusts: the Harvard management company and how the endowment was run, and Harvard's unsustainable spending spree as the endowment increased. The first I don't feel qualified to talk about; it seems that Harvard's investment portfolio has become more risky over the years, but it's not clear to me how far the risk-reward ratio was out of whack, or that performance was out of line with other institutions. (It's hard to know what the right comparison is, given the flaws that seem to have been underlying the financial system of the last several years, of which there are several victims beyond Harvard.) It seems to me that more information is needed, and the article suggests that Harvard is not particularly transparent about these sorts of things.

On the spending side, I think it's clear Harvard went too far too fast in its spending plans, particularly under Larry Summers, who I think if anything gets insufficient blame in this article. It was under Summers Harvard dramatically increased spending on new buildings (financed by debt, and sometimes without getting sponsorship from donors first), faculty size increased, and financial aid plans zoomed. I have to admit, all of these things, particularly at the time, I thought of positively, at least in theory. Of course (duh), increasing space/faculty/aid money all always sound good. But it was also fairly clear at the time (and much clearer in retrospect) that Harvard was doing too much too fast and assuming the money would come from somewhere down the line. While my standing far outside the inner circles of Harvard administration means I can't claim to know who holds responsibility for this, from my standpoint Summers seemed to be leading the call for an overly ambitious agenda, never mind the costs.

(Indeed, the most rankling part of the article for me was the following quote: "The fact that they fired him is a symptom of everything that's wrong with Harvard," one of Harvard's big donors told me. "He's not politically correct or diplomatic -- he's incredibly provocative. What he really got fired for was attacking waste and abuse in the Faculty of Arts and Sciences." I don't think this donor knows what he/she is talking about, and no evidence in the article suggests otherwise. First, Larry Summers wasn't fired, he resigned. The faculty does not have the power to fire him; we did take a vote of no confidence, which had no formal power, but was a statement of how the faculty as a whole felt about him. Second, I'd enjoy hearing more about the waste and abuse he was attacking; in terms of profligacy, I think it's clear his tenure as president was a net negative. The previous paragraph of the article has a different take. "In reality, however, when Summers was president of Harvard, he alienated just about every faculty member who crossed his path. Instead of being admired as a visionary, he was said to be arrogant. Instead of being recognized as a bold and fearless leader, he was perceived as a cerebral bully." The current administration, under the gun, is dealing with financial waste through serious budget cuts, apparently more effectively than Summers ever did. And through a quite difficult situation, they appear thus far to have maintained the strong respect and support of the faculty.)

Anyhow, I encourage everyone to read the article, and to comment on the issues raised by the article -- both in terms of Harvard's situation and the corresponding situations at other universities -- as you like.

Friday, July 10, 2009

California Update Part 1

I spent Tuesday at the pre-EC tutorials and NetEcon workshop at Stanford. The highlight was watching Jon Feldman and Muthu Muthukrishnan give a tutorial on web advertising. While most of what they talked about was already within my range of knowledge, they presented it very well and it's interesting to see their view of a theoretical take on real-world advertising problems. (My experience with Google people, reinforced here, is unfortunately they only let out enough details to whet your interest, without giving enough details to be really useful. Not that I blame them. There are undoubtedly limits on what they can reveal, and obviously any individual can't know all the working details at a low level.)

Today I gave my version 0.1 talk on "Open Problems in Cuckoo Hashing" at Microsoft. I was blessed with a receptive audience, who asked questions and pointed out various typographical errors and other possible fixes. The highlight for me was when two of my TAs from last semester showed up for the talk. (One is doing a summer internship a few blocks away at Google, the other -- who will starting grad school in theory next year -- is the daughter of a Microsoft Researcher.) Since I'm sure they'll stumble across this, a big thank you for coming!

In the afternoon I saw an interesting talk by Rafael Pass on Game Theory with Costly Computation. The high-level idea is to include a notion of computation cost in the utility function, so that your utility can depend on how much computation you use, which might in turn affect your choice of game strategy. It seemed like an interesting conceptual idea, and the twist has some surprising implications (like Nash equilibria no longer always exist).

Tuesday, July 07, 2009

Self-Advertising : Talks and Such

I'll be on my annual summer pilgrimage to California this week. In case you're in town with nothing to do, I'll be giving a "practice talk" for my invited ESA talk:

Some Open Problems in Cuckoo Hashing

this Thursday at Microsoft Research Silicon Valley (10:30 am), and Tuesday July 14 at Stanford (4:00 pm).

On Monday July 13 I'll be at Google. giving a different talk, on the PODS paper An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets, by Kirsch, Mitzenmacher, Pietracaprina, Pucci, Upfal, and Vandin. See the previous blog post here.

If you're around please feel free to come to a talk. (At Google and Microsoft, if you're not an employee, I'm not sure how you get in the door, but I'm sure you can find a way...) Or if you're already at one of these places and want to see me, please try to get on the schedule.

Thursday, July 02, 2009

FOCS 2009 (Guest Post)

Guest Post by Dan Spielman.

The list of papers accepted to FOCS 2009 is now available at:

As Mike did after the STOC 2009 PC Meeting, I'd like to provide a short summary of what happened at the FOCS 2009 Meeting.

We arrived at the meeting having at least three reviews for each paper. To save time for discussions of papers during the meeting, we voted to reject many papers in the two weeks before the meeting. We also voted to accept a small number that had overwhelmingly strong reviews. I would like to have heard more about these papers, but it would not have been a productive use of time.

After our preliminary decisions we had 123 papers to discuss over 2 days. This gave us only a few minutes to discuss each paper. In spite of the short timeframes, the discussions of papers were remarkably insightful, intelligent, and witty. Things were said that I will remember always. Unfortunately, confidentiality prevents me from sharing them with you. As chair, my job was to prematurely halt these discussions so that we could vote and move on to the next paper.

As was done in many PCs before, I asked committee members with conflicts of interest to leave the room. Committee members were deemed to have a conflict of interest with authors who were their advisor or advisee, who were at the same institution, and with whom they were close friends. My test for friendship was "would you be proud if this paper was accepted?" As many observed, these are not perfect tests for COIs, but they are a first-order approximation. This policy did have some drawbacks, as it often meant that the person most expert in the area of a paper was excluded from the discussion. To ameliorate this problem, I solicited extra reviews of papers for which this was the case. I am thankful that so many in our community responded to my urgent requests for reviews.

I am VERY happy that we took this approach to handling COIs. I know that I would have had a difficult time being unbiased when discussing papers with which I had a COI. One advantage of this approach that I did not see discussed in the comments on Mike's blog is that it preserves the committee members' reputations for integrity. We accepted many papers with which I had a COI, and I am glad that I will not be suspected of tilting the process in favor of my friends.

Deciding which papers to accept is a very difficult process. With insufficient time and consideration, we were forced to make decisions that are very important to many people. We did the best we could, but I am sure we made mistakes. At least there is no paper on which a majority of the committee believed we made a mistake.

I hope you all will join us for the 50th IEEE FOCS.