Tuesday, June 30, 2009

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.

Monday, June 29, 2009

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.

Friday, June 26, 2009

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.

Monday, June 22, 2009

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:

Lance Fortnow, Northwestern University

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.

Thursday, June 18, 2009


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.

Wednesday, June 17, 2009

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

Tuesday, June 16, 2009

A Mathematics Museum

An old friend pointed me to this article about Glen Whitney, who is creating a math museum (after what I assume was a successful career in hedge funds). It's an inspiring story, and I wish him and this endeavor great success.

I first met Glen Whitney at the Ross Mathematics Program (also known as the Ohio State mathematics program) -- motto : "Think deeply of simple things..." -- and also saw him now and again at Harvard. The summer program has had a lot of influence on young mathematicians, and while one can measure its success in various ways (including the number of alumni who have gone on to have careers in mathematics or related fields), certainly the fact that it provided inspiration to Glen, who is paying it forward through this math museum, is one measure of its success.

Monday, June 15, 2009

SODA/INFOCOM deadlines

SODA info is up. Submissions page says you need to register (with abstract) on June 29, with paper due July 6, 5pm Eastern Daylight Time.

INFOCOM is July 24 register, July 31 paper due. Nice to see those deadlines finally separate.

Friday, June 12, 2009

Visiting AT&T Labs

I went down to AT&T Labs to give a talk and visit yesterday. The visit was primarily inspired by wanting to talk to Mikkel Thorup, who has done a lot of fantastic work related to hashing. (For example, his paper on "Tabulation based 4-universal hashing with applications to second moment estimation" with Yin Zhang, and his work on Priority Sampling.) I also had the chance to talk to several others, including Walter Willinger, Edith Cohen, and David Johnson. I haven't visited AT&T for a while; the lab has been through some tough times over the years, but remains the home of a number of truly outstanding researchers, and in particular of researchers who successfully bridge the divide between "theory" and "practice". Mihai Patrascu joins their ranks shortly.

I had a wonderful time, marred only by the fact that my flight home was delayed over two hours -- part weather, part mechanical trouble? I think every flight out of Newark I've ever had -- a small but not trivial number -- has been delayed at least an hour.

Saturday, June 06, 2009

Rajeev Motwani

I awoke this morning to find the tragic news of the death of Rajeev Motwani (from Lance and Suresh). I had the pleasure of meeting Rajeev as a Berkeley graduate student and later working with him on FOCS 1998 (he was program chair, I handled local arrangements). He was always encouraging and inspiring, an ambassador for the theory community to the rest of computer science and a role model for graduate students (his many own, and others such as myself). We mourn his passing.

Thursday, June 04, 2009

The ICS conference -- what should it be?

I'm a bit surprised by the lack of discussion on the announcement of the new ICS conference. (That's "Innovations in Computer Science", a new theory conference -- with a rapidly approaching deadline.) Perhaps that's because none of the organizers themselves are bloggers -- let me extend an open invitation to any of them to guest post here to discuss the conference. I also think in some part that's because there's confusion as to what ICS is supposed to or will be. Indeed, when talking about it to people at STOC, more than one person suggested to me that probably the organizers themselves didn't know what sort of papers they'd get, and that it would take a couple of years for the conference to find itself.

On the other hand, my previous post on ICS suggests some discussion would be helpful. Take the response of one anonymous commenter.

'It is clear from various discussions that many people in the community feel that FOCS/STOC has deviated from their original goals, and no longer serve the interests of the discipline as a whole. These conferences serve more as some sort of "proving ground" for graduates students and young reserachers and these people seem to be constitute the main attendees to these conferences these days. Hopefully, ICS will become a venue where more serious thinkers can present their work, without becoming contaminated by the career-related competitive issues that have ruined the STOC/FOCS conferences.'

Now, I have not been regularly attending STOC/FOCS of late, as my interests have shifted more to applications, and my more theoretical work is generally a better fit for SODA. But having just spent several days through the entire conference, I just don't get this comment.

It's natural for up-and-coming graduate students to aim for the top conferences, and it's the sign of a healthy community that they can get papers in. (Indeed, often they produce the best work!) While the competitive nature is unfortunate, basic supply/demand of top jobs explains it, and in my experience it's common across CS subfields. Is this really keeping out good work? I don't see it.

My take on this comment was that there are still people frustrated with the issue of "conceptual papers" being rejected from FOCS/STOC, which seem to be the commenter's view -- that ICS could become a forum for these works . My take is that the community has heard the complaint and taken it into consideration. FOCS/STOC seems to be happy to accept good conceptual papers. A HotTheory conference, which takes work too preliminary for FOCS/STOC but with clear potential, could be worthwhile in my mind; but somehow I don't see a conference for papers rejected (or that would be rejected) from FOCS/STOC because the supposedly unwise committee couldn't understand the conceptual contribution as being what the community needs. I personally hope ICS becomes the former rather than the latter.

But that's just my view. The broader point is, while the organizers will try to make the conference the best it can be, as a community, shouldn't we try to discuss it more? Perhaps not here on this blog, but in general?

In a related vein, please see the thread below, which I've opened for more general comments and feedback on this year's STOC.

Tuesday, June 02, 2009

Valiant Day slides and such

Michael Kearns has put up photos and slides for many of the talks for Valiant's day here. Avi Wigderson has the slides from his talk (with many open questions) here (bottom of the page).

STOC 2009, Feedback

The conference is over. I thought it would be useful to provide a thread for feedback on the conference. The point here is, in my mind, to offer feedback that might be useful to the next Program Chair (Leonard Schulman) and/or possibly the next Local Arrangements team. Did you like the mix of papers? Were there enough conceptual/technical papers? Was the schedule reasonable? How were the talks? There could be more institutional memory in our conference processes; perhaps this can add some. Or discuss some of the previously raised issues from this blog I brought up at the business meeting (slides). Or just to say you enjoyed it or hated it. In order to avoid this becoming a "discussion" with me, I don't plan on commenting on comments, so now is a good time to say what you think -- although do keep in mind constructive criticism is significantly more helpful than criticism.

STOC 2009, Day 2

The highlight of Day 2 was the Award Paper session. The papers of Chris Peikert and Robin Moser were already amazing; but the two of them further impressed with fantastic talks. I'd go on and on about Robin's talk on a constructive proof of the Lovasz Local Lemma (which matches my interests more), but Lance Fortnow and Dick Lipton have already posted on it here and here, respectively. I really encourage reading these posts.

Monday, June 01, 2009

Innovations in Computer Science Conference

One of the more interesting things to be announced at STOC is a new Innovations in Computer Science Conference.  As it says in this call

Innovations in Computer Science (ICS) is a new conference in theoretical computer science, broadly construed, encouraging new ideas, approaches, perspectives, conceptual frameworks and techniques. ICS aims to regain and support the interest in works that are focused on exploring novel directions in computation and communicating new conceptual messages (e.g., introduction of a novel model, problem, or technique).

Now I think this is interesting in spirit -- after all, it was almost two years ago now on this blog I asked whether there should be a HotTheory workshop, similar to the HotOS and HotNets workshops.  This seems to be a new conference in that spirit.  

I wonder, however, why the steering committee didn't take more of a lead from these already long existing workshops.  Calling it HotTheory, for instance, would have made it consistent with the now many similar workshops in CS, so that it would have an immediate resonance with those outside of theory.  There are, however, other important questions, most of which have been answered by other HotWorkshops, that the ICS call does not make particularly clear:

1)  What kinds of papers are being asked for?  Other Hot workshops are very clear that they are seeking positions papers, which seems to have a fairly consistent translation in systems : you may have done some initial experiments (or just have an idea for experiments to do), but you haven't built the full system and don't have complete results.  Indeed, many such workshop papers seem designed to get feedback on work in progress, although there are some where the paper is more of a statement of a direction that should be followed.  What is the equivalent for theory?  You have some lemmas but only conjectures of a big theorem?  Could you write an ICS paper with no theorems and just ideas of something that should be studied?  Some guidelines would be very helpful.  Perhaps, even, some example papers.  
2)  How will work be disseminated?  The authors mention a printed proceedings from Tsinghua University Press.  Will they also be available on-line, as for other HOTworkshops?  Will there be an effort to get them into an electronic archive (ACM or IEEE)?  
3)  Will these papers be able to be published in other conference (e.g., FOCS/STOC)?  The other Hot workshops typically limit the papers to 5-6 pages, and the assumption is that a more complete, fleshed out version can be sent to a conference subsequently (where the papers are typically 10-14 pages).  [Sometimes the question of "does this have enough more than the Hot paper?" can come up in PC meetings for the big conferences;  in general, in my experience, significant deference is given to the notion that the Hot workshops publish position papers, and that much or even all of a Hot paper can be repeated within a larger conference paper as long as some non-trivial new material is included.]  The ICS call is for 10 page papers;  is it assumed this is the final home of the work?

I'll be trying to get answers to these questions at STOC, and posting them (or having people from the steering committee) answer them here.  If you have questions as well, please post them.