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?