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

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.

FOCS 2009 (Guest Post)

Guest Post by Dan Spielman.

The list of papers accepted to FOCS 2009 is now available at: http://www.cs.yale.edu/focs09/papers.html

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.

Netflix Prize in the News

A group (BellKor's Pragmatic Chaos) has announced that they've beaten the barrier needed to win the $1 million Netflix Prize. This sets off a 30-day clock -- this team will win unless some other team does better in this period.

While there's been various opinions as to what extent contests like this really drive forward science, it's certainly been memorable -- I remember lots of news articles when the contest was first announced, and a lot of excitement over it. I'm a little surprised as how muted the news is now that the contest has been "won"; a Google news query for "Netflix Prize" shows just over a hundred articles, reasonable for a tech story but certainly not high by any means. At the very least, it was an interesting challenge that non-scientists could relate to and demonstrated the importance of good algorithms.

Are there other similar prizes out there? (Google seems to have run a number of contests, such as this one.) Maybe we should create more of them, or encourage industry to do so? For many people science is inspiring for its own sake, but for many others, a little flair (and money) is more likely to attract their attention.

ISIT conference this week

The 2009 International Symposium on Information Theory is going on this week in Seoul, Korea. I'm not attending, although it sounds like there's plenty of interesting things going on. Amin Shokrollahi is giving a tutorial on fountain codes, Balaji Prabhakar is talking about models and algorithms for Internet data centers. Some of the plenary talks sound like they'd be of interest to CS folks: Randomized Dimensionality Reduction by Richard Baraniuk, It's Easier to Approximate by David Tse, Combinatorial Reasoning in Information Theory by Noga Alon. Plenty of sessions on low-density parity-check codes and their variations, and network coding. There's something relatively new out there called "Polar codes" that I should learn more about.

It's a bit disappointing to see in the program a lack of what I think of as "CS theorists" at ISIT, though perhaps this year Seoul was just too far to go for a conference that's more tangential to people working on related areas in this group. As I've said before, given the list of topics, one would think there would be more crossover. With eight parallel sessions over 4 1/2 days, there would certainly seem to be room. Maybe next year.

If anyone in the comments wants to point out exciting news or results from ISIT, or other blogs discussing the goings-on, please do so; I'd be happy to hear of news.

Another Harvard CS Professor Blogs

Stuart Shieber has started a blog focused on issues related to scholarly communication (particularly, Open Access) call The Occasional Pamphlet. I'd recommend the post on "Don't Ask, Don't Tell" rights retention as a starting point.

Deep Packet Inspection : Iran

I was interested to hear the words "deep packet inspection" -- a phrase I'm well familiar with -- used in conjunction with "Iran" on NPR on the way home. Here's the corresponding article in the Wall Street Journal.

SIGACT elections

The results of the SIGACT elections are complete, and the newly elected members are:

SIGACT Chair:
Lance Fortnow, Northwestern University

Members-at-Large:
Cynthia Dwork, Microsoft Reesearch
Anna Lysyanskaya, Brown University
Michael Mitzenmacher, Harvard University
Mike Saks, Rutgers University

I'm looking forward to working with this group, and to hearing what it is we actually think we'll plan to be doing. Given a blogging chair and member-at-large, there should be plenty of opportunity for people to comment on the job the SIGACT officers are doing for the next few years.

SLOGN

While people are all talking about ICS, another new conference was also being whispered about in the hallways at STOC. I'm happy to say that SLOGN now has a call for papers up (sent to me by Ryan O'Donnell and Rocco Servedio). It promises to be something different entirely.

Human-guided search survey online

New up on my papers page -- a survey of results from the human-guided search project I did years ago. Lots of fun stuff came out of that projects, my favorite being Bubblesearch. I'd like to return to those ideas sometime. I think there's a lot of potential in thinking about how people actually use algorithms, as well as thinking about the algorithms themselves.

And I just have to point out the new acronym I learned today... YHTMAAAIYP. I can't wait to use it in a review...