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.

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

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.

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.

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.

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.

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.

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.

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.  

STOC 2009, Business Meeting

Sampath Kannan gave his overview from the NSF. It was actually very positive (the last slide ended with "CCF is alive and well") -- there seems to be a wave of new funding, and funding rates have been relatively high (and improving) over the last few years, way ahead of the "low teen" years around 2004-2005. Sampath also gave some strong verbal support to applied theory, pushing for more theory interactions with the rest of computer science (and other areas) and for a theory of experimental algorithms. He suggested there may be discussions upcoming for a Theory+CS systems program. I admit I was very pleased to hear such a strong message in support of applied algorithms in particular.

Salil Vadhan presented the outcomes of the Theory Visions workshop from last year, with the goal to produce "nuggets" to help highlight excited efforts going on in theory to communicate to the NSF and other computer scientists. Example nugget titles include Algorithms for Understanding Data on a Massive Scale, P vs. NP, Making Economic Theory Tractable, Achieving Privacy and Utility, Efficient Computation in the Physical Universe, Computational Approaches to Modeling the Brain and Cells, Commuting as a Commodity, etc. The nuggets will be up at www.theorymatters.org.

The Godel Prize was awarded. I gave my conference report (I'll get the slides up at some point). Local arrangements report. Various other reports (SIGACT budget, STOC 2010 Boston, STOC 2011 FCRC). New Business - Theory of Computing, an open access journal, at www.theoryofcomputing.org. Princeton workshop Aug 25-29 on Barriers to Complexity Theory. New conference -- Innovations in Computer Science (ICS) to take place in China (most/all expenses paid) in 2010-201. "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)."

STOC 2009, Day 1

Just a couple of quick highlights from Day 1.

Costis Daskalakis, when discussing oblivious PTAS's for Nash equilibria, presented the following probability lemma that seems like it should be very useful (note: it's not clear I'm stating it correctly, or with all appropriate conditions): if we have collections of random variables X_i and Y_i and look at sum_{i=1}^n X_i, sum_{i=1}^n Y_i, and the sums agree on their first k moments, the variation distance between distribution of the sums in 2^{-\Omega{k}}. (I believe the X_i and Y_i have to all be independent.) The result is based on something called the Krawtchouk Expansion. I'm looking forward to seeing this argument; it seems like a potentially useful lemma for other contexts.

Aaron Bernstein gave a nice talk on his result with David Karger creating an oracle for All-Pairs Shortest-Paths result that can find the shortest path when a node or edge fails; that is, you can find and store shortest paths avoiding an individual node or edge, and you can do it in (up to polylogarithmic factors) the same time/space as for a standard APSP structure. This goes on my list of algorithms I'd like to have a student implement, to see how it really works.

STOC 2009, Day 0

The Saturday before STOC was devoted to a 60th birthday celebration for Les Valiant. The program is here. I'm afraid I missed most of the morning talks because I didn't fly in until the morning, but the afternoon talks were really very good. (I hope the speakers will all put their slides up on their web pages -- it's useful for everyone!) Some brief highlights, with apologies to those talks I don't describe:

Rocco Servedio started the afternoon with a short survey of learning theory, starting with the foundations laid by Valiant's PAC-learning paper and some of the early work in the area, and then connecting it to recent results and still-open problems in learning theory today.

Michael Kearns followed with a talk that highlighted the impact of this early work on the development of the machine learning community and how it is practiced today. One point he highlighted is that Les was not content to just publish his CACM article on the theory of the learnable, but was proactive in trying to ensure that the ideas reached other communities (in particular the machine learning community) so that they could really bloom. I think a hallmark of Les's work is his willingness to not only "focus the computational lens" on other areas but also to try to frame models in ideas in ways that those other areas can further build on them.

Vitaly Feldman provided a well-presented short survey of Les's more recent work on evolvability, and his own work in that area.

Avi Wigderson closed with a talk showing some of the threads and connections leading from Les's work, focused primarily on theoretical results related to the permanent. One of the really nice things about this talk was that Avi tried to close his quick discussions of each thread by listing some remaining open problems. I really enjoy surveys that are structured this way -- not just "here's what was done" but a clear sign of "and here's what's still left to do". I've encouraged Avi (and will do so again) to get the slides for this talk up on his web site as soon as possible; it should be a useful resource for people (especially graduate students) looking for problems to think about.

Perhaps the one disappointment for the day is Les himself didn't give a talk. But that's not surprising to me; Les avoids self-promotion, and lets his work speak for himself. I think the program itself pleasantly overwhelmed him, and provided a remarkable display of all that he has given the theory community (and the broader scientific community) through his work.

STOC schedule updates

I was asked to put up the following schedule changes for STOC on the blog. The information will also be available at the conference of course.

1. The business meeting will be held 8:30-10 PM Sunday, instead of 7-9 PM, with the venue being unchanged (the Haverford/Baccarat, which is one half of the Crystal Ballroom). This should allow people to have a more relaxed dinner rather than having to rush to get back to the business meeting.

2. The Athena Lecture on Sunday and the two prize talks on Monday will also be held in the Haverford/Baccarat instead of the whole Crystal Ballroom, since the latter is very large.

See you there.

SIGCOMM PC Report

The chairs of the SIGCOMM PC were asked to submit a note to CCR on the Commitee Process, available here. It's an interesting read. (Overall, I've found the systems community a bit ahead of the theory community in thinking about and reviewing its conference processes.) They also make some anonymized data available -- which looks safe to me, but if anyone thinks that's a bad idea, I think it's worth speaking up about it.

Some highlights:

1: "We do see a problem with requesting only 14-page submissions, and want to use this document to convey a position we frequently heard from TPC members as well: short papers could be an interesting addition to future CFPs. In a conference with such a low acceptance rate as that of Sigcomm, “small contributions” naturally find themselves at a disadvantage. The issue is that the description and evaluation of an ingenious but small idea certainly takes less than 14 pages. The same is true for work that improves on prior work or presents tools with important practical use but small technical contribution."

Short papers are, in my mind, also a potential mechanism for mixed theory/practice papers to get into SIGCOMM. One issue that arises is that theory papers aren't written in the way systems papers are. In a theory paper, if we're describing an algorithm or data structure, our goal is to make it as GENERAL as possible -- here's a neat idea, here are some places it might be useful, please find others. SIGCOMM pappers are designed almost the opposite way -- to show an algorithm or data structure is useful requires looking at a very specific application and experimentally detailing exactly what performance gains arise in the context of that specific application. I will push for short papers to include interesting algorithms and data structures that might be GENERALLY useful to lots of people and applications but may not yet have been shown to offer groundbreaking performance for a specific application. (As pointed out in the PC meeting, my work is often in that space, so I have a bias in this argument...) Suggestions for making this workable are desired.

2: "ACM SIGCOMM defines a conflict of interest between an author and a reviewer if the two have worked together in the past two years. Students and advisors are considered “conflicted for life” and of course any institutional or private relationship between the author and the reviewer instantly qualifies as a conflict."

I just had to point out the "of course" there, after some of the inane commentary regarding my introducing much weaker conflict of interest policies and goals for STOC. (See here and here.) [When I've talked about the theory community's standard conflict practices to systems people, most politely shake their heads and mumble, "Well, if that's the way it's done..." The more open people privately make clear their opinion our approach opens the door for all sorts of systematic biases and seems remarkably backward. And I'm phrasing that politely.]

3: "For a few years Sigcomm has used a two-tier TPC: “light” members are asked to do 10-15 reviews and are not invited to the meeting; “heavy” members are enrolled for 20-25 reviews plus mandatory participation in the TPC meeting. The split is mostly motivated by keeping the TPC meeting of manageable size. This year we introduced a third tier, called “senior” for lack of a better name. The role we intended for senior TPC members was a mix of conflict solver, an additional voice during the TPC meeting, helping hands for last minute reviews, and possibly carriers of a different perspective that could put the submitted research under a more positive light."

Compare with the theory discussion taking place here on the roles of junior/senior PC members in theory conferences. Also, compare with the theory conference practice of using 100+ subreviewers with PC members responsible for 45+ reviews. I'm not claiming this approach is better; but it is food for thought.

Grades Out, Complaints Begin...

Apparently, student who filled out their class reviews got access to their grades today. It's been a while since I've taught a class this large (80 students) -- how many e-mails do you think I'll get from students inquiring about why their grades were lower than expected?

I can't really blame them for asking. In their defense, so far those who have asked did poorly enough on the final that their grade did move down a level from before the final. However, the ones who suggest they want to go back over problem sets from earlier in the semester (that they've had back for some number of weeks) to get more points in an effort to improve their final grade could potentially annoy me. Even if a problem was misgraded, they've had plenty of time to bring it up before (the TAs, who graded the assignments, are generally not available now to ask if a question comes up), and it seems clear the goal is find a way to push themselves over the grade boundary line. Doing this after grades are turned in is a major hassle. Apparently, I should add a note to the syllabus with a statute of limitations on grade changes for assignments. Luckily (and by design) almost all students are far enough away from the grade boundary that even a substantial change on the homework won't change their final grade.

So far, before noon this Saturday morning, I've had 3 e-mails from students about their grades...

Godel Prize to Salil Vadhan

Congratulations to Professor Salil Vadhan of Harvard for winning SIGACT's Godel Prize.

(Oh, right, also congratulations to his co-authors Professors Omer Reingold and Avi Wigderson.)

Computer Science 222 : A Discussion

I'm reflecting on my Graduate Course on (vaguely) network algorithms from this year, and particularly the discussion I had with students at the end of the day. I view the class as being geared toward first-year graduate students, with explicit goals of the class being to introduce the students to research and how it's done and to build theory/systems connections.

1. The class really tries to mix theory and practice -- on good days, we discuss two papers on a topic, where I've tried to have one come from the theory side and one from the systems side. At the end of the day, not surprisingly, the theorists like the theory papers more and the systems people like the systems paper more. But it does seem that the course opens the lines of communication, and they have a greater understanding and appreciation for the other side. The payoff, if any, may only be seen in the long term -- but I'm pretty sure there's a payoff there.
2. The class can apparently be a lot of work at times -- the theory people have to pick up things (how does TCP work?), and systems people have to pick up things (what's that notation mean?). I hope that's good training, on both sides.
3. Students seem surprised that all papers we read aren't "blockbusters" (especially since we start with the papers for PageRank and HITS -- two clear blockbusters). That's on purpose. Beginning graduate students have exaggerated expectations -- what they've generally seen are the blockbuster results, and they wonder where their breakthrough will come from. (This matches my recollection of starting graduate school.) They're unaware that research is a skill to be learned, that it's perfectly OK to start out with a "mere" incremental result, especially to get one's feet wet. For typical graduate students, there's a learning curve in figuring out how dissect and analyze problems, organize and present experiments, write clear and compelling text, etc.; but many don't really think of their first year as training in this sense. Also, beginning graduate students tend to underestimate the potential value of innovative follow-on work; lots of incremental results are actually really valuable. (Few papers actually start new fields.) Several students said they were relieved in coming to realize while taking the course that their first papers didn't have to be top-conference breakthroughs.
4. The most popular topic by far (for both systems and theory people) was information theory (particularly compression and related algorithms). Many said it was their first real exposure to information theory -- why hadn't it come up before? Some asked where there was a course on information theory algorithmics. (None other that I know at Harvard -- is there a course to recommend at MIT?) And really, you can't go through the Burrows-Wheeler compression algorithm without being completely floored. If I ever stop teaching undergraduate algorithms and data structures, maybe I should put together an advanced undergraduate course merging (practical) algorithmics with information theory and queueing theory.
5. There's demand to expand these theory/systems connections; while I focused on networks, there was interest in covering related topics in databases, distributed systems, and other areas.
6. I'm hoping that several of the class projects -- with or without my assistance and input -- can be expanded into research papers. A number of them look promising. However, I usually teach this course in the fall, and can use the momentum to work with students in the spring to realize the results more fully. I'm not sure that will work this year (especially with some projects being done by graduating seniors...)

Sadly, I probably won't teach this class again until Fall 2010 or 2011. Something to look forward to. (If anyone from the class reads this, feel free to post comments anonymously or mail me directly...)

Grading Time

I have to get in my final grades in the next day or so. Some thoughts and questions.

1) What's the average grade you give? (Anonymous answers are fine.) Without getting too specific, my average for my undergraduate class is usually somewhere between a B and a B+ depending on the year. (I would happily give straight A's in my undergraduate class if I felt it was merited. Hasn't happened yet.)
2) My course seems to have recently become a "proving ground" for freshmen who consider themselves good at math/CS. I had more freshmen than ever this year... and on the whole, they did MUCH better than average. (I had about 10-15% of the class as freshmen this year -- and they got about 1/2 the A grades...)

I'd like to encourage this. I'm thrilled to get bright freshmen into algorithms and data structures early (and I hope to get them in my grad classes or to do a thesis later). I have to remind myself to send these students a note and see if they want to be teaching assistants next year. It's great when you get a TA who can do the course multiple years...
3) My grades for my graduate class will be much higher than for my undergraduate class on average -- even for the undergraduates who take the class. This isn't really surprising. The graduate class is very self-selecting. (One interpretation is that only the very top undergrads from my undergrad class choose to take the graduate class, so of course they do well; the other is that the undergrads who like me as a teacher choose to take the class, and I'm just therefore easier on my grad class. What's the Jaccard coefficient of these two sets of students...?) And grad classes generally seem to have a higher curve, since most institutions (Harvard included) require grad students to maintain something like a B average, so anything less than a B is like a failing grade. Is there a huge difference between grades for your grad classes and undergrad classes at your institution? Even if you get undergraduates in the grad classes?

A Problem Archive?

Having just gone through the painful process of making up my final exam (again), I'm inspired to think that there must be a better way. We should have a problem (and solution) repository so professors/instructors can easily find a collection of problems to borrow from or to use as a creative inspiration. It would be nice to be able to say, "I need a dynamic programming problem, a linear programming problem, and an approximation algorithm problem..." and go to one place to start getting ideas. (Right now, all of you that keep your exams online, I'm probably cribbing from you, thanks to Google... I notice more of you are keeping such info password-protected than a few years ago...)

I (obviously) haven't thought much about how this would work in practice, so consider this an open discussion. Of course, there's the problem of keeping such a repository protected from student eyes. Ideally, actually, perhaps we'd have a student site (unprotected) and a faculty site (password-protected). Would you use such a site? Would you contribute problems to it? What sort of incentives would make such a site work? What other uses (besides making up exams and problem sets) could such a site be good for?

Life After Rejection (Guest Post)

Guest blog post by Aaron Sterling.

Michael M. asked me to post about an academic journey of one of my papers, so here goes.

In November 2008, I submitted a paper, "Distributed Agreement in Tile Self-Assembly," to STOC. The paper was rejected, but the comments I got from the reviewers were superb. They were extensive and specific -- and I agreed with everything they said. I changed the paper to address each of the concerns raised, and resubmitted it to DNA 15 (the 15th Annual Meeting of DNA Computing and Molecular Programming). This time around, my paper was accepted, and I recently learned that it won the Best Student Paper Award.

Two points seem important to me.

First, I didn't (and don't) take rejection personally. I view paper submission not as an event, but as part of a process. If I get a quality rejection letter, and I improve the paper based on the comments in the letter, it's just a matter of time before an improved version of my paper will get published somewhere.

Second, the STOC PC reviewers played a role in advancing computer science, beyond just putting together a program for STOC. My experience may be unusual. One congratulatory email I received, from a well known theoretical computer scientist, basically said, "Congrats on your award, and I'm shocked that you got useful feedback from STOC reviewers. So congrats on that too." Therefore, I'd like to emphasize to anyone reviewing something, that even if a submission is not a good fit for your particular venue, providing useful feedback is scientifically important. I'm very grateful that I had reviewers who approached their role conscientiously.

I'll conclude by shifting gears into a soundbite of my paper's technical results. I was able to show connections between the geometry of self-assembling networks, and the theory of multiprocessor synchronization. For example, three-dimensional self-assemblies can simulate strictly stronger shared objects than two-dimensional self-assemblies. These connections seem to intrigue both the "nano people" and researchers in distributed computing -- and I'm now investigating synchronization problems in several subareas of natural computing. If nothing else, it looks as though it'll be a lot of fun.

A pre-proceedings version of the paper is available here.

Hoopes Prize Committee

I'm serving this year, as I have every year I've been at Harvard, on the Hoopes Prize Committee for Harvard science theses. This is one committee I don't mind serving on at all. I get to read (or at least skim) a number of senior theses in a variety of areas -- mostly computer science, math, applied math, and engineering, but usually I have a couple in fields more removed from my natural interest, like psychology, astronomy, evolutionary biology, and even geology. (I admit, I eagerly avoid the very large number of theses in biology and biochemistry; I'm sure my colleagues in related fields can better deal with the jargon there.) The worst of them is generally quite interesting; the best are high-quality publishable research. The committee sends in the reviews, and meets for lunch to work out who gets the prizes.

The committee exemplifies all the possible problems one can imagine in committees (that have arisen in the context of discussing PC meetings on this blog).

1. Only 2 reviews per work.
2. No guarantee the reviewer is an "expert" in the specific subarea.
3. Widely varying interpretations on what the scores mean. (In past years we've been told to aim for an average of 3. Most submissions are quite good; novice reviewers tend to end up with an average closer to 4.)
4. Widely varying interpretations on what the prize should be for. It's a writing prize, for the sciences. How should one judge math theses, which, arguably, if written entirely correctly, nobody in the room might be able to properly read in the time available? How much weight should be given to scientific novelty versus the writing itself?
5. Increasing numbers of submissions per reviewer. (When I started, I think we each had six theses to read; this year, it has hit ten. The barrier to entry is low, so perhaps there's an increasing tendency to submit...)

And so on... in some sense, it's great training for program committee work.

Despite the potential problems, it generally works out well. Some years there are many disagreements that have to be discussed; most years, surprisingly few. Overall, there's always the feeling that the student work is quite amazing, and that we at some point have to draw a line and just pick what we think is best. I wish all committees left me feeling as positive when I left the room.

Communications Technologies and Universities : No More Office Phones?

Here's an amusing article tying together budget cuts at universities and new technologies; the communications department at UW is cutting costs by getting rid of phones. Students who want to meet professors will have to e-mail them or find them.

I admit I would be loathe to give up my office phone. If only to save my fingers from potential RSI (I haven't been cursed yet), I think using a phone instead of e-mail is a good idea in many situations. And there's no way I'd give students (or even many staff people) my cell phone number. On the other hand, I must admit my office phone is not a highly used device, and students in particular almost never reach me by phone. Indeed, these days a number of the calls on the office phone are solicitors -- this has only really started happening in the past year or two, and I wonder if Harvard's phones were somehow off the grid of phone solicitors way back when or if there's been some other change. So while there's irony in a communications department getting rid of phones, I can see where the cost-benefit analysis might suggest it's the right thing to do.

An AMS Paper on Power Laws and Network Modeling

There's a new article on up at Notices of the AMS entitled Mathematics and the Internet: A Source of Enormous Confusion and Great Potential, by Willinger, Alderson, and Doyle.

It's an interesting read, although I've heard some of the main points in talking with them before. In terms of specific examples of how problems in the modeling of the Internet arose, my take on their take of the history is that the trouble started with the well-known Faloutsos^3 paper (On Power-Law Relationships on the Internet Topology), which first appeared in SIGCOMM 1999, and which claimed that the degree distribution of the Internet's router-level topology followed a power law. It has been argued that there are a number of flaws with this paper, most notably in the underlying data, as described in this article, making their conclusions on the power-law relationship unreliable. (Given my recent posts and corresponding discussions on the SIGCOMM PC meeting, it's interesting to reflect on the importance this paper has played after being published in SIGCOMM.) The second part of this troublesome history is the subsequent work of Barabasi and Albert, who leveraged this result to help proclaim that the underlying mechanism of the Internet topology is preferential attachment, explaining this power law behavior. The authors discuss how this claim was made without sufficient validation, and argue that there are other optimization-based models that much better explain the guiding mechanisms behind the Internet topology, based on actual Internet engineering.

To start, I should admit not-so-humbly that I think the authors could have mentioned my very-relevant survey and editorial on these issues (the editorial, in particular, discusses the validation issue in this context). But leaving that aside, it's an interesting read with many possible lessons to draw or questions to think about. Are we insufficiently critical at early stages (e.g., conference publications), so that once a result is accepted, it becomes difficult to point out where it may be flawed? How do we deal with "noisy" network data in analysis? Are we getting to the point where only teams from Microsoft, Google, Akamai or AT&T (or some other big company) can publish in certain areas of networking because they're the only ones that can get good enough data? What are the useful ways mathematicians can contribute to the study of networking topology (yet another power law model does not seem to be compelling)?

I have to admit, I have a side worry with this appearing in the AMS. Given how it sometimes appears that mathematicians view computer scientists, I worry that this article will reinforce the belief in the minds of some mathematicians that computer science is "non-serious" or "non-rigorous", which clearly wasn't the intention of the authors. The problem of explaining the history of "enormous confusion" and "great potential" is the risk that too many readers will focus on the former rather than the latter.

New Paper: On Compressing Social Networks

I'm posting online the "final version" of a paper that will be appearing at KDD, On Compressing Social Networks; the collaboration came out of a visit to Yahoo last summer.
(Co-authors: Chierichetti, Kumar, Lattanzi, Panconesi, and Raghavan.)

The paper definitely tries to look at both the "theory" and "practice" of compressing social network graphs. On the theoretical side, one contribution is that we formalize arrangement problems that are variations of the standard minimum linear arrangement problem that naturally capture features of the underlying compression problem. In the linear arrangement problem, we are given a graph G, and we wish to lay the nodes via a permutation mapping pi:V->[1,n] out on the number line (in positions 1 to n, the number of nodes) in such a way as to minimize sum_{i,j in E} |pi(i) - pi(j)|.

But when we're trying to compress edges in the graph, and we're given an ordering of the nodes, the "cost" of compressing an edge is the cost of the pointer from one vertex to another, and as the number giving the gap between the positions i and j in the node ordering is |pi(i) - pi(j)|, the cost in bits for representing an edge from i to j is (essentially) log_2 |pi(i) - pi(j)|. This suggests considering the minimum logarithmic arrangement problem, where the goal is to find an ordering to minimize sum_{i,j in E} log |pi(i) - pi(j)|. (More generally, one could consider other functions besides the logarithm of the gap --which could naturally correspond to different encodings of the natural numbers in this context -- but this seems the most natural.) We show that (in multigraphs) this problem is NP-hard. I admit, having pondered over this a bit, I wish we had a bit "nicer" of a reduction. In particular, we don't have hardness of approximation results (or an approximation algorithm), which would be a step forward. We also consider a more complicated variation of the arrangement problem that corresponds naturally to compressing successive gaps instead of individual gaps.

On the practical side, we explore several algorithms for compressing social networks, and see how they do on real data. Our main innovation here is to come up with a quick and useful method for generating an ordering on the social network nodes so that nodes with lots of common neighbors are near each other in the ordering, a property which is useful for compression. For Web graphs, this has generally been done using the external information of the URLs; sorting by URL naturally gives an ordering where nodes with common neighbors are near each other. In social networks, there are possible pieces of external information we could use -- zip code, or order of entry into the social network -- but these are much less reliable. We find a "shingle ordering" using the ideas used for document similarity based on min-wise independence; basically, we pick a (first) random ordering of the nodes, and then group nodes according to their first neighbor in this random ordering. Two nodes i and j with neighbor sets N(i) and N(j) are then in the same group with probability equall to the Jacard coefficient |N(i) intersect N(j)| / |N(i) union N(j)|; orders within the groups can be handled according to external information, a second random ordering, etc. This works quite well. (The best comparable technique we know of, which also works quite well, is to order nodes by Gray-code orderings of their neighborhoods; see this paper by Boldi, Santini, and Vigna.)

I enjoyed working on this paper quite a bit, for several reasons. Micah Adler and I wrote one of the early papers on Web graph compression, utilizing the idea of finding nodes with similar link structures; it was nice to return to this theme. I think the paper ended up being a good mix of theoretical framework and experiments based on implementation. It's also just pleasant when my regular trips out to California lead to concrete results -- it gives me a good excuse to continue taking regular trips to California!

Intradisciplinarity

I was reminded by that bizarre NYT opinion piece that interdiscplarity is all the rage, but people rarely talk about intradisciplinarity. How big is the discrepancy? Well, Google had about 27,500 documents for me when I search intradisciplinary, and over 17,000,000 for interdisciplinary -- over 600:1. (Naturally, Google suggested that I meant interdisciplinary when I searched for intradisciplinary.) On Google Scholar, it's still over 100:1; 4,050 to 697,000.

I'm a big fan of intradisciplinary work. I enjoy working with computer scientists (and EE people, who I'll add in the mix, as we're often working on the same problems) in a range of areas on different types of problems. I've designed my graduate class in networking algorithms to bring together systems and theory, with papers from both sides of the aisle represented. I find one of the benefits of being in a smaller department at Harvard is that it promotes intradisciplinary work, because you talk to a more varied mix of people.

I wish there was more attention given to intradisciplinary work, because from my standpoint, it's important and useful. It's great when computer science can influence the direction of biology, economics, and physics; but I think we also get amazing payoffs when networking people and theory people and machine learning people and architecture people work together too. While it does happen, and non-trivially frequently, thank goodness, on the whole I think the community could do a bit more to promote that kind of work.

The ACM Does NOT Support Open Access

UPDATED BELOW

I was a few hours ago cc'ed on some messages to some STOC authors -- well, really to Salil Vadhan -- with the opening statement:

"Dear Authors,

It has recently come to our attention that the "addendum" attached to your signed ACM copyright form is unacceptable (not recognized) with the ACM Copyright Office. Please let us know immediately if you can provide us with a new unaltered signed ACM copyright form..."

What happened? Well, Harvard's Faculty of Arts and Sciences (as of February 2008) has an open access policy; we're supposed to put our publications in a Harvard database that serves as an open-access repository for faculty work, and grant Harvard the right to distribute them. Our Office for Scholarly Communications -- the director of which is computer science professor Stuart Shieber -- has a standard boilerplate to add to the standard copyright forms saying, essentially, we work for Harvard and Harvard reserves the right to distribute copies of our scholarly work in this open-access repository.

Apparently, the ACM just now noted that Salil added these on (I should point out, the proceedings are going to press pretty much now), and refused them. Salil called to explain and work something out, and was told explicitly that the ACM does not support open access policies. So officially Salil is now directing Harvard to waive the policy for these articles (the policy provides a waiver mechanism) to keep the ACM happy and his papers in the proceedings. I'm sure it will work out, but because Salil is conscientiously trying to follow everyone's official rules, he's having an unnecessary headache to deal with. (If there were time, I imagine he'd make more of an effort to find someone in the ACM to approve the Harvard addendum, but again, they're letting him know just as the proceedings have to get produced.)

It is often hard to tell in these situations whether this is REALLY ACM policy or if the person in the office at the time just assumes the appropriate response is to say only the original ACM form is acceptable. But this not acceptable behavior of our professional society. I support the ACM and the many good people that work there, but I can't support such limitations on distribution of scholarly work.

If you feel similarly, please pass your opinion, politely, along to any ACM higher-up you know. But if we don't get their attention, things aren't going to change. There is contact information for people on the ACM council or executive committee, as found here. Perhaps if you feel strongly enough mailing president@acm.org is a good start.

President: Wendy Hall, president@acm.org
Vice President: Alain Chesnais, chesnais@acm.org
Secretary-Treasurer: Barbara G. Ryder, ryder@cs.vt.edu
SIG Governing Board Chair: Alexander L Wolf, alw@acm.org
Past President: Stuart I Feldman, sif@acm.org

UPDATE

Salil later received correspondence from the ACM, which included the following statement:

ACM Copyright Policy allows authors to retain several rights, many of which are contained in the Addendum, including distribution from authors’ personal and institutional web sites and use in lectures, presentations, etc., however, the right to grant permission for reuse is not among them and several other stipulations run counter to ACM’s established policies and interests.

Apparently discussions between the ACM and Harvard's office to come to an agreement are ongoing. Regarding the issue on the right to grant permission for reuse, there's some explanation on Harvard's side on the policy FAQ. Salil's response also reinforces that this was not what he was told when he called to discuss the issue:

Thank you for the clarification. It would have helped to hear some of these explanations during our conversation. Individual Harvard authors such as myself have no way of knowing what discussions are underway between ACM and the Office of Scholarly Communication, and do not appreciate being told to use the waiver option with no explanation beyond being told that our professional society does not support open access.

The Taylor Editorial

My students and colleagues today pointed me to this New York Times editorial by Mark C. Taylor, the chairman of the religion department of Columbia, that begins with "Graduate education is the Detroit of higher learning." As pointed out by my students and by my colleague Matt Welsh on his blog, a lot of his arguments seem to break down when viewed from the perspective of computer science and engineering departments -- where, generally, we do try to train students to possibly do something besides becoming an academic -- and it's fun to deconstruct his article with this in mind. In particular, let's look at his 6 steps to fixing American higher education.

1. Restructure the curriculum, to become more cross-disciplinary.

I think CS (and in particular theory) does a very good job with this already, thank you, what with algorithmic game theory, quantum computing, the study of social networks, etc. And outside of theory I can point to my colleagues like Matt Welsh using sensors to monitor volcanos or Radhika Nagpal studying cell behaviors as multi-agent systems as further examples. (Yes, I know David Parkes and Yiling Chen are also obvious choices of cross-disciplinarity in action...)

One thing I generally think people (or perhaps just chairs of religion departments) fail to understand when saying education should become more cross-disciplinary is that before trying to do cross-disciplinary work it is, in my opinion, extremely beneficial to actually be an expert in (at least) one field so one has a base to work from. The corollary is that you can't just erase traditional structures and expect wonderful things to suddenly bloom.

2. Abolish permanent departments and create problem-focused programs.

Again, my opinion (and to be clear, it's an opinion) is that while problem-focused programs have their place, you need a solid base to work from. In his own example, to handle the problems with the future of water, he suggests bringing together people from humanties, arts, social science, natural sciences, law, medicine, and business together to deal with the problem in the large. That's great, but it implies you need experts in these areas in the first place to get together, which means you still need a great deal of specialized training.

3. Have smaller, more focused institutions; use technology to offer best-of from all over.

This is certainly an area for exploration, though I know it's the subject of wide debate whether distance education methods are as good as "being there". Certainly, many universities are already doing this to various degrees. I don't think we know all the answers on how to best make use of technology in this way yet, although our understanding will keep getting better.

4. Transform the traditional dissertation.

I don't think he explains exactly what it should transform into, but he seems here to be speaking to humanities people whose dissertations are essentially books nobody ever reads. Computer science dissertations are rarely read, but generally they're a collected form of papers that hopefully some people have read. I think we're fine here.

5. Expand the range of professional options for graduate students.

Good idea. CS graduates can, as again my colleague Matt Welsh pointed out, go into work in academia, research labs, industry, and government -- never mind entrepreneurial opportunities. (As a whole, theorists are perhaps a bit behind in this regard -- we really should make sure our graduates obtain some practical CS skills as well -- but apparently we're much better off than our other university counterparts.)

6. Abolish tenure.

In CS, tenure has always seemed less about "academic freedom" (a common argument for it for humanities) and more about providing a perk (commensurate with academic traditions) to make up for the generally lower pay scale versus industry. And it's a perk that demonstrates its value in periods like the current economy. What would abolishing tenure do to the university system? Who knows. It seems a situation ripe for the Law of Unintended Consequences, and I'm loathe to try to predict whether it would be a good or bad thing. Mark C. Taylor, naturally, is more confident of the benefits.

For several other criticisms of this editorial, there are plenty of comments at the NY Times site. I know these anti-University diatribes come out from time to time, but it's sad to see such a poorly argued one. While it's beneficial for universities to be self-reflecting, in this case the article just made we wish for some clearer, more rational, dare I say more SCIENTIFICALLY thought out criticism.

Will Network Coding Become Part of the Network? A Class Experiment

This week in my graduate class on networking algorithms, I asked my class to focus on the question of whether network coding will become a part of "the network" (whatever you choose that to mean). Given the wealth of papers that have appeared its clear the academic community has embraced the notion of network coding, and there's certainly lots of interesting theory. But I don't know of what I would call a significant real-world deployment -- will we see one in the next decade or so? This is, to me, an important question -- certainly I'd be more inclined to work on network coding problems if I think there's a potential for real-world impact. The class has read a few current papers, and I wondered what they would think.

Interestingly, the class pretty much split down the middle, with perhaps a slight bias toward no. The main reasons cited against the development of practical network coding was that there didn't seem to be an immediate killer applications, and the gains, while non-trivial, weren't enough to cover many of the inherent problems (network support, backward compatibility, etc.) in deploying network coding. A common example given was that there were many challenges in mesh/ad hoc networks, and network coding (while useful) wasn't solving the really important ones. On the more optimistic side, several students saw situations (wireless mesh network, "closed" networks where complete control is centralized so network coding can be set up easily) and possible important issues (can network coding improve energy usage?) that would lead to more widespread network coding use in the years to come.

The discussion reminded me of short survey I once wrote up on "Digital Fountains" (and hey, when Googling I see the powers-that-be even posted my slides) where besides discussing their applications I asked why they weren't now in widespread use. The issues sound familiar.

I'd be happy to have others offer their opinions to my class on this issue. Feel free to comment on whether you think we'll see real-world deployments of network coding systems in the future (or let me know of any in existence now!), and what you see the challenges being for network coding going from an interesting idea to a deployed solution.

Two Talks : Savage and Upfal

Today was a busy day with talks.

Stefan Savage of UCSD gave a talk at Harvard's Center for Research on Computation and Society on his work on Spamalytics, which is really about the economics of botnets. Essentially, they "infiltrated" a botnet in order to (mostly passively) monitor its behavior and learn what these networks actually do and what their economic potential is. It's fascinating both from an engineering perspective (how do you do it) and an economics perspective (what do you learn about the behavior of the participants), and should guide both anti-bot technical efforts and policy. While it's not clear to me there's much in the way of "science" in the pure sense of the word in this work, I liked Stefan's analogizing this work to anthropology: the goal here is to study what's going on and learn the relationships among the actors.

I look forward to cornering Stefan sometime and hearing more about the "issues" that arose with this work -- somehow, the FBI kept coming up at points in his talk, but he didn't really have time for the details. (He did seem to state they're more in touch with the FBI now than initially -- to help make sure the FBI doesn't mistake them for the botnet!) What's interesting in my mind is there must be more projects like this where the government-powers-that-be would both like and benefit from active research into the misuse of computer systems and related computer security problems. How can that cooperation be fostered, in a way that maintains the academic goals like publication and dissemination of the knowledge learned? I'm not sure it works by government agencies initiating the project; it seems it would have to start the other way around, as this project did. But I don't envy the time Stefan (or his team) must have spent with lawyers making sure they weren't breaking the law because they weren't working under government supervision.

[The question I didn't get to ask Stefan: what grant do you use to cover "legal expenses" for projects like this? Can that be an NSF line item, or did the corporate donations cover that part?]

The second talk of the day was Eli Upfal visiting MIT to talk about his work on multi-armed bandit problems (see the paper list here). His variations were all nicely motivated by related problems for search engines, specifically matching ads to web pages. (I recall hearing about these motivations when we were both visiting Yahoo! Research, so they resonated with me.) The variations include when the bandits are mapped to a metric space and their value satisfies a Lipschitz condition, when the bandits value can change over time (specifically the mean changes according to a Brownian motion process), and when the useful lifetime of a bandit is given by a stochastic distribution. The talk was at the opposite extreme from Stefan's -- very theoretical, with a focus on both upper and lower bounds and the techniques behind them. I had thought of multi-armed bandits as a fairly well-mined area of research, so it was interesting to see multiple novel, well-motivated examples -- suggesting there's plenty more interesting questions left in this area.

Conference Sign Ups : STOC

Just a reminder that the early registration cutoff for STOC is approaching -- April 28. Go on and register! Having done local arrangements, I know all too well how important it is to have a solid count as early as possible; let them know you're coming. And you won't want to miss it (and ancillary activities such as Valiant day.)

In other news,a reminder that NSDI is in town this week.

SIGCOMM PC, Post-Analysis

1) Setting a new high bar for local arrangements, outside the conference room was a cappuccino/espresso machine, and (for most of the time) a barista just for the PC.
2) There seemed to be widespread agreement that the quality of submissions this year was not as high as in previous years. (Just my luck...) Whether this reflects reality or we were all just very grumpy is open to interpretation. (I do not think we were grumpy.)
3) Because of this feeling about paper quality overall, there will be, I believe, fewer accepted papers this year than in the last few previous years.
4) I was amused to see when the classified papers into groups there was a whole category of papers labelled "theory". Theoretical SIGCOMM papers generally refer to new and interesting algorithms or data structures for applications, but still generally require an implementation demonstrating the effectiveness of the idea in practice (or a suitable simulation). Overall, theory papers seem to do reasonably well at SIGCOMM. George Varghese is the master of writing such papers, if you are looking for an example to emulate.
5) Indeed, there seemed to be some enthusiasm for more openness to theoretical work on the committee, which seemed in line with my open complaint to networking/systems people. There may be a push (I'll be pushing!) to aim for a "cool algorithm/data structure implemenation tricks and ideas" next year. (The hard part of this is writing down what the right criteria for such papers are... clear practical utility in a network setting being what I'd aim for.)
6) The 5-point scale did seem to have its problems. There was the usual problem that people did not work with the scale appropriately/treat it consistently. The other problem was, because of the impression there were few strong submissions, there were very few 5's and comparatively fewer 4's than usual, effectively collapsing the scale. I'm not sure the 5-point scale itself is to blame for these problems.
7) The 5-point scale was very effective for initially dismissing a lot of papers quickly.
8) Probably because there are fewer papers at the PC meeting to deal with, there seems to be more intense discussion of papers overall and in particular of controversial papers at the SIGCOMM PC as compared to say the STOC PC. Also, more people on average are able to (and more than willing to) give an opinion on any given paper.
9) While there was plenty of discussion, there were no real fights -- at least while I was in the room. Indeed, the sharpest discussion -- all about what is expected of a SIGCOMM paper -- was probably instigated by me, regarding a more theoretical paper, leading to a discussion of what exactly was expected in terms of evaluation of an interesting idea for SIGCOMM. Again, I'm hoping this dicussion might lead to a special session of possibly shorter papers with useful algorithmic tricks for networking people... though we'll have to see if enough such papers actually exist!
10) The PC dinner involved, among other food, an entire roast boar.

Overall, a very interesting PC experience.

Theory and Many Cores Reflection

Since I'm at a lull point at the PC meeting, I'll write another post.

There's a call for a Workshop on Theory and Many-Cores at the University of Maryland the Friday before STOC. (Remember the Saturday before is Valiant's birthday celebration.) There's been some discussion in various blogs (as I note below) about it, so before discussing it, I'll repeat part of the call:

The sudden shift from single-processor computer systems to many-processor parallel computing systems requires reinventing much of Computer Science (CS): how to actually build and program the new parallel systems. Indeed, the programs of many mainstream computer science conferences, such as ASPLOS, DAC, ISCA, PLDI and POPL are heavily populated with papers on parallel computing and in particular on many-core computing. In contrast, the recent programs of flagship theory conferences, such as FOCS, SODA and STOC, hardly have any such paper. This low level of activity should be a concern to the theory community, for it is not clear, for example, what validity the theory of algorithms will have if the main model of computation supported by the vendors is allowed to evolve away from any studied by the theory. The low level of current activity in the theory community is not compatible with past involvement of theorists in parallel computing, and to their representation in the technical discourse. For example, 19 out of 38 participants in a December 1988 NSF-IBM Workshop on Opportunities and Constraints of Parallel Computing in IBM Almaden had theory roots. The lack of involvement of theorists should also concern vendors that build many-core computers: theorists are often the instructors of courses on algorithms and data-structures, and without their cooperation it will be difficult to introduce parallelism into the curriculum.

The main objective of the workshop will be to explore opportunities for theoretical computer science research and education in the emerging era of many-core computing, and develop understanding of the role that theory should play in it.

I view this call as an attempt at strong advertising -- this area is important, lots of other areas are working on it, it could be core for the future -- but it seems to have brought some strong negative reactions.

Both Mihai Patrascu and Bill Gasarch have blogged about this. Mihai's post is very sarcastic and (although he clarifies his point in the comment) is not very clear, but his point seems to be that this is something theorists should but won't get involved with, having worked too much in this area in the past (PRAM algorithms) with little success. And there are what I take as negative comments on Bill's post, which seem to say "shouldn't the systems people be explaining to us why this is interesting" and even that theory should be independent of what's actually going on in CS.

I don't think the advertising is over the top at all. There is an unfortuantely-too-small collection of theory-oriented people who like working on problems and algorithms that real people might use. Mulit-core seems to be a rapidly growing area, with potential for interesting challenges. The fact that years ago people got over-excited about what in retrospect (or even at the time) turned out not to be a suitable-for-practice set of models doesn't mean there's not interesting work to be done now. It won't appeal to all theorists, and perhaps this sort of work doesn't meet some (Mihai's?) definition of "fundamental work theorists should be doing". But when there's a burst of activity in area in CS, as a community theory should be there if they can contribute. Exploring the possibilities here is just a good idea. I don't get the negativity, but I do see it as another example of a subset of theorists pushing a separation of CS theory from the rest of CS that's ultimately unhealthy, in terms of our relevance (and related things like funding).

And let's face it -- what's going to happen in multi-core architectures and languages is likely going to happen without the input of theory (and could happen without theory input as all). Does that mean we can't make meaningful contributions or find interesting new problems? Of course not. But if we believe this is the direction computing is going to move (and I hear that an awful lot these days), it does mean that for the theory community to sit around waiting for systems people to come asking for input is not a good idea -- unless the community wants to highlight a lack of relevance and interest in actual computer science as being practiced.

Talk on Codes for Flash Memory

While here at SIGCOMM, I gave a talk at University College London on some new results for codes for flash memory. Here are the slides. Although it was a "theory" talk to a "systems" audience, it seemed to go well, I think because people are generally interested in flash memory and how it works.

As a reminder (also discussed at this old post) flash memory is strange. As a simplified model, you have blocks of cells, where each cell can take on a value in the range 0 to q-1 (where q is currently pretty small -- say 4, but seems to be growing with technology), and a block can consist of thousands (or more) of cells. Reads of cells are fast. When writing, you can INCREASE the value of a cell, but in order to decrease any cell value, you first have to ERASE (set back to 0) the entire block. And erases are bad -- it wears out the memory, and the number of erases is the primary factor in the memory lifetime.

So, for example, if you have a block of 6 cells, and q = 4, it's "easy" to make the change

0 2 1 3 1 2 -> 2 2 1 3 1 2

but "hard" to make the change

0 2 1 3 1 2 -> 0 2 1 1 1 2

since you'd have to erase to change that 3 back to a 1. In this setting, when talking about a code, I was not talking about error-correction, but rather data representation: how can we use blocks of cells to represent data effectively while minimizing erasures.

The talk had an overarching question, and some specific results.

1) The big question: how does flash memory change things, at the scientific level? Should we be designing algorithms and data structures specifically for flash? If so, what should these things look like? Similarly, what about memory hierarchies that utilize flash at one or more levels? [This seemed to be the part that interested in the systems people.]
2) Some deterministic, worst-case codes: this work was primarily the senior thesis work of Hilary Finucane, who is heading to Weizmann next year. We've made it available as a Technical Report which can be found here.
3) Average-case codes. We've actually extended our previous analysis from Allerton and submitted a journal version; at some point I'll put it up as a preprint (but mail me if you're interested).

I think flash memory is a potentially interesting area that seems to have slipped in under the radar of many people. After getting into it by way of codes, I'm currently trying to learn more and see if there really are worthwhile algorithmic questions there.

Blogging from the SIGCOMM PC

I don't think I'm revealing any big secret by saying I'm currently at the SIGCOMM PC meeting. So far, it's what you'd expect -- a crowded room of 30+ people, hashing out what papers we actually want to accept. Lots of discussion, some of it contentious, but no big fights (yet).

I'm realizing that a possible downside of bigger PCs (which I think theory conferences could use) is that just logistically it's harder to have over 30 people in a room having these sorts of discussions. It's harder to hear and see everyone. When it's your turn to talk, talk loud.

An interesting logistic difference is that we're discussing papers in numerical order by topic, not ranked by score. I'm still absorbing how well this works. (I've found it nice in other PCs to start at the top and bottom and quickly accept and reject "easy papers". This is different.)

People are removed from the room for conflicts. There are papers where I can't see the reviews or anything beyond the paper title. Yet we soldier on. Seriously, this is not a big deal. Being outside is a good chance to talk to people. There are plenty of non-conflicted people to offer opinions, of course, so the issue brought up by theory people that conflicted people need to be around so you have enough knowledgeable people doesn't arise. (Of course, I think it comes up much less in theory than people argue.)

After having chaired STOC, it's very nice to sit back and participate in a PC meeting without being a chair. I even have time to blog about it.

The Town Hall Meeting

I went to part of the "Town Hall Meeting" about Harvard's gloomy financial situation yesterday; some news writeups are available with more details.

I don't often see Mike Smith since he took leave of the Computer Science faculty to become Dean of the Faculty. And when I do, it's not usually in his Dean capacity. I have to say, I think he did a very good job with a bad situation yesterday. Mike's demeanor is generally calm, collected, composed -- he comes off as reassuring in the face of crisis. (Yes, I know the same is said of our still-new President -- the style is somewhat similar on its face.) I must admit I'm also reassured knowing there's a technical, engineering-oriented person up there who can deal with the numbers and tradeoffs -- somebody who just knows what it means when told something like you have to cut 10% from the budget and 50% of the budget is fixed. Finally, I thought he answered questions well. I've heard some thought he was "evasive", but I think he simply avoids giving details when he's not sure what the details are yet, or doesn't have the facts at hand. And he answers questions thoughtfully and respectfully, which wasn't the case with some previous higher-ups in the administration....

The situation is still a bad situation. But I, at least, have some confidence in the people who are supposed to be managing it.

Harvard Happenings

After I get done with teaching today, there's a lot going on around Harvard.

First, we will be having a reception to welcome our newly incoming Dean of the School of Engineering and Applied Sciences, Cherry Murray. I don't know much about her, unfortunately, but if anyone does and wants to send me e-mail with information, feel free. I admit, my major concern with a new Dean coming in is the question of how we're going to grow Computer Science -- and related fields, including Applied Math and Electrical Engineering -- at Harvard, particularly in the face of the financial crisis. I'd like to think it's clear we have the need, and I'd like to hear when we think we're going to have the means.

After that, this afternoon there will be a "town hall meeting" (as opposed to a faculty meeting) to discuss the dire financial situation at Harvard. Endowment funding is expected to drop by 8% next year, much more than originally expected. Staff layoffs are looking imminent -- perhaps some will be announced at this meeting. In short, the budget situation is grim. As an example that's both in some sense absurd and appropriate, next year for our regular Computer Science faculty lunch meeting, we'll have to brown bag it. As a perhaps more compelling example, the Teaching Assistant to student average ratio is going to have to go up substantially next year in computer science. (We've had an embarassingly luxurious TA-to-student ratio, so I believe that this change will only take us to something that most would consider normal, but it will still be a change for us.) The problem at a university is that so many costs are essentially fixed -- primarily staff costs -- that there's very little in the class of optional things that can be cut substantially. Until the economy turns around, I expect more grim news -- at town hall meetings or otherwise -- ahead.

New Preprint: An Analysis of Random-Walk Cuckoo Hashing

Some people have asked if being the chair of STOC destroyed my work life for several months. Not really. It certainly was work, and like other administrative duties, it took time away from research. But it didn't completely obliterate my research time. (Arguably, it had less effect than, say, having a new baby daughter...)

So here's an example of new research output: An Analysis of Random-Walk Cuckoo Hashing with Alan Frieze an Pall Melsted. For background, you can read one of my earlier posts on cuckoo hashing. The question we were aiming to answer is what I consider to be one of the big ones left for cuckoo hashing: why does the random-walk approach -- where when you have to kick out an element you choose one randomly and keep going -- work so well? The natural intuition is that in such a setting an insertion of a new element should take at worst logarithmic time with high probability -- each time an element is kicked out to make room for another element, it should have an empty space available with constant probability. But nobody has been able to make that intuition stick.

We obtained a polylogarithmic bound on the time for insertion with random walk hashing. The main idea is to use a 2-step approach: show that the set of items "close" to an empty space (within an augmenting path of length O(log log n) of an empty space) is reasonably large, and then show that a random walk reaches one of those items quickly (polylogarithmic number of steps). Once we get to a close item, there is an inverse polylogarithmic probability of taking the augmenting path to get to the empty space, so breaking it up in this way gives us the desired bound.

It takes a fair bit of analysis of the cuckoo graph to get this result (which has been open for a surprisingly long time). There's still plenty of room to work with in both directions -- a better upper bound, and is a super-logarithmic lower bound possible for some value for the number of choices each item has -- but it was gratifying to make progress on what I think is turning out to be a much more challenging problem than people originally might have expected.

ICALP paper list

The ICALP paper list is posted. It looks like a great set of papers; I encourage the authors to make them available on-line as soon as possible so those of us who can't travel the distance can have a look.

Some interesting titles (showing my bias):

Applications of a Splitting Trick by Martin Dietzfelbinger and Michael Rink: I tend to use the word "trick" when describing the key idea of a proof, although I was consistently told in graduate school not to. (I was told it makes it sound less like a mathematically important idea when you called it a trick. I admit, I don't interpret "trick" that way -- to me, a trick is exactly a clever and useful mathematically important idea in that context -- but I've generally avoided the term.) I want to know what the trick is.

A Better Algorithm for Random k-SAT by Amin Coja-Oghlan: I have a weakness for (random) SAT algorithms.

Sort Me If You Can: How to Sort Dynamic Data by Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian and Eli Upfal: I don't know what that means, but the title grabbed me.

Multiple Random Walks and Interacting Particle Systems by Colin Cooper, Alan Frieze and Tomasz Radzik
AND
Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies by Colin Cooper, David Ilcinkas, Ralf Klasing and Adrian Kosowski: I just gave my Algorithms + Data Structures lecture on the random-walk 2-SAT algorithm, so random walks are on my mind. And of course I have a weakness for random walk algorithms.

Geography, and Where to Send

This week I'm finishing up some work for submission, though I'm having trouble figuring out where to send them. Both ESA and APPROX/RANDOM have deadlines on April 12. Then WADS has a deadline April 24. (Update: my bad, I misread; that's the date for when acceptance i s announced, not the deadline!!!!) Actually, it looks like WADS and APPROX/RANDOM are scheduled on the same dates, and even though APPROX/RANDOM is at Berkeley, Christos Papadimitriou and Richard Karp are apparently invited speakers at WADS, so I probably wouldn't get to see them. Arguably one of the papers is big enough it could be worth waiting for SODA, but my co-authors seem disinclined. Arguably I'd like to submit both to the same place to minimize possible travel, and this also gives the edge to APPROX/RANDOM. (Berkeley's not close to me, but my co-authors may end up going, and if I go, there's always enough things for me to do in the Bay Area that I can make the trip worthwhile.) I'm sure there are other deadlines I'm missing that someone can tell me about in the comments.

While it's nice to have lots of possibilities, somehow all this makes me feel that our community has perhaps a few too many smaller conferences and workshops. Somehow when multiple things are scheduled on the same day with some frequency in our relatively small community, it seems like we ought to consider whether this is the right setup.

STOC schedule

The Local Arrangements Team have the preliminary schedule up at the STOC Web site. I hope it helps everyone make their travel plans.

Since it's (more-or-less) apparent from the schedule, I suppose I'll announce here that the Best Paper Prize will be shared by:

A Constructive Proof of the Lovasz Local Lemma
Robin A. Moser

Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
Chris Peikert

The former also was awarded the Best Student Paper. These talks will be given without a parallel talk. (Who wants to give a talk against an award paper?)

Please don't tell the authors, as I haven't let them know yet. Perhaps, if we all keep quiet about it, they'll be surprised at the conference.