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.
Sunday, May 31, 2009
Thursday, May 28, 2009
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.
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.
Tuesday, May 26, 2009
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.
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.
Saturday, May 23, 2009
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...
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...
Wednesday, May 20, 2009
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.)
(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...)
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...)
Tuesday, May 19, 2009
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?
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?
Thursday, May 14, 2009
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?
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?
Wednesday, May 13, 2009
Life After Rejection (Guest Post)
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.
Friday, May 08, 2009
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.
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.
Thursday, May 07, 2009
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.
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.
Tuesday, May 05, 2009
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.
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.
Monday, May 04, 2009
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!
(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!
Thursday, April 30, 2009
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.
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.
Wednesday, April 29, 2009
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:
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.
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.
Tuesday, April 28, 2009
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.
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.
Thursday, April 23, 2009
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.
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.
Wednesday, April 22, 2009
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.
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.
Tuesday, April 21, 2009
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.
In other news,a reminder that NSDI is in town this week.
Saturday, April 18, 2009
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.
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.
Friday, April 17, 2009
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:
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.
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.
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.
Thursday, April 16, 2009
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.
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.
Wednesday, April 15, 2009
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.
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.
Tuesday, April 14, 2009
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.
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.
Monday, April 13, 2009
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.
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.
Wednesday, April 08, 2009
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.
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.
Monday, April 06, 2009
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.
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.
Wednesday, April 01, 2009
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.
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.
Monday, March 30, 2009
PODS paper
I'm a co-author of a paper that will be appearing in PODS: An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets, by Kirsch, Mitzenmacher, Pietracaprina, Pucci, Upfal, and Vandin. This version isn't quite the final official version (which is due shortly), but should be much the same. I think this is my first official "database paper", which is very exciting. (I'm grateful to Eli Upfal for inviting me and Adam to work on this project.)
The motivation, roughly, is the following. The setting is a standard data mining problem: we have transactions, where each transaction is a set of items, and we are looking for interesting correlations. Suppose we have 1,000,000 transactions, on 1,000 items, where each item appears in 1/1,000 of the transactions. We observe that the pair of items (i,j) appears in 7 transactions. Is this a significant observation? If we compare to a "random model" where each item appears independently in each transaction with probability 1/1,000, then it might appear so; on average, the pair should appear in only 1 transaction. But the problem is there are almost 500,000 pairs of items. It's not surprising that some pair should appear 7 times; in fact, we'd expect about 50 such pairs. So if we were mining for common pairs, the count alone should not necessarily flag this pair as unusual; it would also matter how many such pairs with this count that we've seen.
The underlying issue is that we're doing multi-hypothesis testing. We're asking "do any pairs appear a statistically significant number of times", not "does this specific pair appear a statistically significant number of times." The first question is naturally harder to answer, since it also should involve the global behavior of all pairs of items, not just the counts from each pair.
Our theoretical starting point is therefore to look at the distributions we obtain on frequencies of subsets of items under our random model. Let Q_{k,s} be the number of itemsets of size k that appear together in at least s transactions in the random model. We can show that, for sufficiently large s (and under certain other conditions), Q_{k,s} is well-approximated by a Poisson random variable, using the Chen-Stein method. (As with all things probabilistic, that sounds very intuitive if we could just assume independence everywhere, but there are dependence issues to take care of -- hence the Chen-Stein method.) We can then leverage this to design statistical tests for finding interesting itemsets, based in part on how far the corresponding values in our observed data set are from the Poisson distribution.
The idea is to expand on the approach of "return all itemsets of size k that appear at least this threshold many times", both so that we have a more rigorous notion of what that threshold should be, and so that we can tell if there are enough such itemsets that what we're seeing is likely to be important. This appears to effectively cut down on the number of spurious itemsets we return, or what in the literature is called the False Discovery Rate. Hopefully, this approach will prove interesting enough for further exploration from data-miners.
The motivation, roughly, is the following. The setting is a standard data mining problem: we have transactions, where each transaction is a set of items, and we are looking for interesting correlations. Suppose we have 1,000,000 transactions, on 1,000 items, where each item appears in 1/1,000 of the transactions. We observe that the pair of items (i,j) appears in 7 transactions. Is this a significant observation? If we compare to a "random model" where each item appears independently in each transaction with probability 1/1,000, then it might appear so; on average, the pair should appear in only 1 transaction. But the problem is there are almost 500,000 pairs of items. It's not surprising that some pair should appear 7 times; in fact, we'd expect about 50 such pairs. So if we were mining for common pairs, the count alone should not necessarily flag this pair as unusual; it would also matter how many such pairs with this count that we've seen.
The underlying issue is that we're doing multi-hypothesis testing. We're asking "do any pairs appear a statistically significant number of times", not "does this specific pair appear a statistically significant number of times." The first question is naturally harder to answer, since it also should involve the global behavior of all pairs of items, not just the counts from each pair.
Our theoretical starting point is therefore to look at the distributions we obtain on frequencies of subsets of items under our random model. Let Q_{k,s} be the number of itemsets of size k that appear together in at least s transactions in the random model. We can show that, for sufficiently large s (and under certain other conditions), Q_{k,s} is well-approximated by a Poisson random variable, using the Chen-Stein method. (As with all things probabilistic, that sounds very intuitive if we could just assume independence everywhere, but there are dependence issues to take care of -- hence the Chen-Stein method.) We can then leverage this to design statistical tests for finding interesting itemsets, based in part on how far the corresponding values in our observed data set are from the Poisson distribution.
The idea is to expand on the approach of "return all itemsets of size k that appear at least this threshold many times", both so that we have a more rigorous notion of what that threshold should be, and so that we can tell if there are enough such itemsets that what we're seeing is likely to be important. This appears to effectively cut down on the number of spurious itemsets we return, or what in the literature is called the False Discovery Rate. Hopefully, this approach will prove interesting enough for further exploration from data-miners.
Friday, March 27, 2009
FOCS Brief Descriptions
I too got Muthu's request to point to Umesh's writeup to motivate the brief descriptions for FOCS this year. But I was busy with family duties this morning, and didn't get a chance to say anything before all the other blogs did. And now it's all been said. But I'll link anyway, in case somebody's missed it.
Of all the posts, I'd say JeffE's should be required reading. Of course, I consider anything with the slightest hint of snarkiness from Jeff required reading, both for amusement value and to see what points he makes, and this post exceeds the minimum recommended daily allowance of snark.
Of all the posts, I'd say JeffE's should be required reading. Of course, I consider anything with the slightest hint of snarkiness from Jeff required reading, both for amusement value and to see what points he makes, and this post exceeds the minimum recommended daily allowance of snark.
Thursday, March 26, 2009
Parallel Session Madness
One of the last tasks I have as STOC chair is trying to organize the schedule, which involves the unpleasant subtasks of trying to group the talks into coherent sessions, and then figuring out what sessions go when, including what sessions will "compete" since we'll have two parallel sessions running. These tasks are frustrating since in some cases it's hard to find coherent subtasks, there are annoying constraints that arise (4-paper sessions should only run against other 4-paper sessions so there aren't holes; in general, an "algorithmic session" should run opposite a "complexity" session?) and decisions that people surely won't be happy with (nobody likes being opposite a "trendy" session or a "name" author, and nobody likes being placed in the last session of the day). And, of course, there aren't any tools for this (that I know of).
Last night, after already putting hours into this, it hit me -- slots should just be assigned randomly. Obviously this idea partly stems from my own frustration -- why am I spending time on a problem with no well-defined solution (and that I'll only hear complaints about afterward)? It has the advantage of making any "decisions" that people might find disagreeable an act of chance, instead of an act by me.
But I also thought of a good reason to do it this way. Categorizing and grouping talks in this way exacerbates the subdividing and splintering of theory into subgroups that know little to nothing about what everyone else is doing. Not working in property testing? Great, there's a whole session you can skip. Not so interested in computational geometry? Now you can sleep in for the morning session.
If FOCS/STOC are supposed to be flagship theory conferences each year, and they're the conferences where all these subgroups come together, maybe this session grouping is actually detrimental. Random mixing of papers could encourage people to stay in the room and see something new. As long as you're down there for the talk you wanted to see, you might stick around and see that next talk that would have been in a session you never would have gone to.
Yes, I know the price might be a few more times where two papers with a potential shared audience run at the same time. (Maybe we can still use that session information; find a random schedule that doesn't put two papers in the same nominal session at the same time.) But it seems like the payoff could outweigh this consideration.
Not that I'd really do this. I don't know of any conference that has. Although there is still time before I have to turn in the schedule. What would all of you think?
(PS -- yes, I know about the approach of having each talk given twice randomly, to help avoid conflicts -- nice in theory, not do-able in practice. :) )
Last night, after already putting hours into this, it hit me -- slots should just be assigned randomly. Obviously this idea partly stems from my own frustration -- why am I spending time on a problem with no well-defined solution (and that I'll only hear complaints about afterward)? It has the advantage of making any "decisions" that people might find disagreeable an act of chance, instead of an act by me.
But I also thought of a good reason to do it this way. Categorizing and grouping talks in this way exacerbates the subdividing and splintering of theory into subgroups that know little to nothing about what everyone else is doing. Not working in property testing? Great, there's a whole session you can skip. Not so interested in computational geometry? Now you can sleep in for the morning session.
If FOCS/STOC are supposed to be flagship theory conferences each year, and they're the conferences where all these subgroups come together, maybe this session grouping is actually detrimental. Random mixing of papers could encourage people to stay in the room and see something new. As long as you're down there for the talk you wanted to see, you might stick around and see that next talk that would have been in a session you never would have gone to.
Yes, I know the price might be a few more times where two papers with a potential shared audience run at the same time. (Maybe we can still use that session information; find a random schedule that doesn't put two papers in the same nominal session at the same time.) But it seems like the payoff could outweigh this consideration.
Not that I'd really do this. I don't know of any conference that has. Although there is still time before I have to turn in the schedule. What would all of you think?
(PS -- yes, I know about the approach of having each talk given twice randomly, to help avoid conflicts -- nice in theory, not do-able in practice. :) )
Monday, March 23, 2009
SIGACT elections
SIGACT elections are coming up. Online voting starts April 1. It would seem very important to remind you that election day is coming up, except that apparently you'll have a couple of months to vote. (I admit I'm a bit confused about why the election site would "go live" three separate times, but that probably won't effect anything.)
I was surprised to see that we're actually having an election this year, in that there's more than 1 person running for chair, and many people running for Member at Large. (See all the various SIG slates here.) It's good to see that people are interested in serving, and I think it reflects a healthy community.
It would be fun to say I'm surprised to see that I'm running (for Member at Large), but it comes as no surprise. I did indeed volunteer myself. I'm not planning on campaigning other than mentioning it here. (It's not really the sort of job one campaigns for, is it?) There are seven people running, and it's an excellent list -- the others running are Cynthia Dwork, Anna Lysyanskaya, Toniann Pitassi, Michael Saks, Baruch Schieber, and Alan Selman -- I think SIGACT will be well served by any subset. If you think I'd be a good Member at Large, vote for me, and if not, vote for the people you think will do better.
As has been mentioned elsewhere, Madhu Sudan and Lance Fortnow are running for chair. Again, that's an excellent choice to have. Apparently, platforms will go up when the election site goes live, and I'll be curious to see what both of them have to say about possible plans for SIGACT in the future. I'd be happy to host a debate here, on the blog, though again, this isn't really a position where there's a big debate necessary. But that's a good issue for comments : what would you like to ask them? (I can always send them a list of questions/point them to the blog post, if only so they can see what is on people's minds.)
I was surprised to see that we're actually having an election this year, in that there's more than 1 person running for chair, and many people running for Member at Large. (See all the various SIG slates here.) It's good to see that people are interested in serving, and I think it reflects a healthy community.
It would be fun to say I'm surprised to see that I'm running (for Member at Large), but it comes as no surprise. I did indeed volunteer myself. I'm not planning on campaigning other than mentioning it here. (It's not really the sort of job one campaigns for, is it?) There are seven people running, and it's an excellent list -- the others running are Cynthia Dwork, Anna Lysyanskaya, Toniann Pitassi, Michael Saks, Baruch Schieber, and Alan Selman -- I think SIGACT will be well served by any subset. If you think I'd be a good Member at Large, vote for me, and if not, vote for the people you think will do better.
As has been mentioned elsewhere, Madhu Sudan and Lance Fortnow are running for chair. Again, that's an excellent choice to have. Apparently, platforms will go up when the election site goes live, and I'll be curious to see what both of them have to say about possible plans for SIGACT in the future. I'd be happy to host a debate here, on the blog, though again, this isn't really a position where there's a big debate necessary. But that's a good issue for comments : what would you like to ask them? (I can always send them a list of questions/point them to the blog post, if only so they can see what is on people's minds.)
Friday, March 20, 2009
Midterm Blues
Yesterday, just before Harvard's spring break, I gave the midterm for my undergraduate class, and then we spent the afternoon grading it. Hopefully, students don't actually read my blog, so they won't be anxious and disappointed over break. Because on average, they didn't do well.
My midterms are commonly both difficult and long; most students don't finish, and historically the average has been around 65-70%. This year, the average was about 50%.
I'm looking for possible explanations. Here's what I've come up with so far.
1) The test was harder this year. There may be something to that -- some of the new questions I've never used before people did quite poorly on. On the other hand, I also think the class did statistically significantly worse on some of my old stand-by questions than in previous years. This may account for some of the discrepancy -- possibly the top students, who usually can do almost everything on the exam, might have obtained lower scores than usual because of this -- but I don't think it can explain this big a discrepancy.
2) I'm teaching worse this year. There may be something to that -- I am teaching two classes this semester and I do have a 9-month old to cope with -- but I doubt this is an explanation. (Obviously, I'm a bit biased here.) My class doesn't vary significantly from year to year -- same topics, same lecture notes this year as usual. Again, even if I think this had an effect, I don't think it can explain this big a discrepancy. (Similarly, I don't think the issue is the TAs I have this year -- they seem like a really great bunch.)
3) The students are doing less well this year. Unfortunately, here there's some evidence -- the average scores, on the whole, are noticeably lower this year than last year across all assignments so far. That could be variance in TA grading style, and the discrepancy on assignments is nowhere as large as it was with the midterm. But my thought is that perhaps this is an unfortunate flip side to class sizes increasing. The class enrollment has dropped from the mid-80s down to 80 -- but this is still over twice as many people as were taking it last year, and still my second largest class ever. Does larger class size (less self-selection) translate into lower averages?
4) Random chance. Seems unlikely.
5) External considerations outside my scope. Maybe more students are having to deal with other midterms the same day or week this year than usual. Small changes in the class schedule can have big effects this way, since many people have multiple classes in common.
Whatever the reason, it's a situation I'll have to pay some attention to. I may have to adjust the pace and style of the lectures, to better maximize what students learn. But for now, I've got the midterm blues. Yes, professors get them too.
My midterms are commonly both difficult and long; most students don't finish, and historically the average has been around 65-70%. This year, the average was about 50%.
I'm looking for possible explanations. Here's what I've come up with so far.
1) The test was harder this year. There may be something to that -- some of the new questions I've never used before people did quite poorly on. On the other hand, I also think the class did statistically significantly worse on some of my old stand-by questions than in previous years. This may account for some of the discrepancy -- possibly the top students, who usually can do almost everything on the exam, might have obtained lower scores than usual because of this -- but I don't think it can explain this big a discrepancy.
2) I'm teaching worse this year. There may be something to that -- I am teaching two classes this semester and I do have a 9-month old to cope with -- but I doubt this is an explanation. (Obviously, I'm a bit biased here.) My class doesn't vary significantly from year to year -- same topics, same lecture notes this year as usual. Again, even if I think this had an effect, I don't think it can explain this big a discrepancy. (Similarly, I don't think the issue is the TAs I have this year -- they seem like a really great bunch.)
3) The students are doing less well this year. Unfortunately, here there's some evidence -- the average scores, on the whole, are noticeably lower this year than last year across all assignments so far. That could be variance in TA grading style, and the discrepancy on assignments is nowhere as large as it was with the midterm. But my thought is that perhaps this is an unfortunate flip side to class sizes increasing. The class enrollment has dropped from the mid-80s down to 80 -- but this is still over twice as many people as were taking it last year, and still my second largest class ever. Does larger class size (less self-selection) translate into lower averages?
4) Random chance. Seems unlikely.
5) External considerations outside my scope. Maybe more students are having to deal with other midterms the same day or week this year than usual. Small changes in the class schedule can have big effects this way, since many people have multiple classes in common.
Whatever the reason, it's a situation I'll have to pay some attention to. I may have to adjust the pace and style of the lectures, to better maximize what students learn. But for now, I've got the midterm blues. Yes, professors get them too.
Thursday, March 19, 2009
NSF Recovery Act
It's a good time to have proposals pending at the NSF. On the other hand, I suppose it will just be even more depressing for those who don't get funded this round.
There's also a chance your previously rejected proposals will get funded!
There's also a chance your previously rejected proposals will get funded!
NSF also will consider proposals declined on or after October 1, 2008. The reversal of the decision to decline must be based on both the high quality of the reviews received on the initial submission and the lack of available funding at the time the original decision was made. The cognizant program officer will contact the institution when a reversal is being considered by NSF. Specific procedural information regarding this new process is available on the NSF Recovery website.Anyone have any additional information to share on how (besides waiting) someone can get a rejected proposal reversed?
Tuesday, March 17, 2009
Would You Leave a Tenured Job?
As reported by Lance, Madhu Sudan is "leaving" MIT for Microsoft Research New England.
Of course, he's not really leaving his tenured position, but just going on leave. But it raises the question -- what would it take for someone (you?) to leave a tenured position? It does happen -- Micah Adler recently left U Mass to enjoy life as a serial entrepreneur -- but tenured positions are quite comfortable, and because of the apparent security tenure offers, it can be hard to leave a tenured position for anything except another one. Tenure is, in that sense, a double-edged sword; you have a position for life, but only if you stay where you are.
Mind you, there are other appealing aspects of academic life. And of course some less appealing ones. Perhaps part of the reason so few people ever give up tenure is that professor positions tend to attract people who enjoy being professors, who find the positives outweigh the negatives, and so they're not attracted to other possible positions or pursuits.
Of course, he's not really leaving his tenured position, but just going on leave. But it raises the question -- what would it take for someone (you?) to leave a tenured position? It does happen -- Micah Adler recently left U Mass to enjoy life as a serial entrepreneur -- but tenured positions are quite comfortable, and because of the apparent security tenure offers, it can be hard to leave a tenured position for anything except another one. Tenure is, in that sense, a double-edged sword; you have a position for life, but only if you stay where you are.
Mind you, there are other appealing aspects of academic life. And of course some less appealing ones. Perhaps part of the reason so few people ever give up tenure is that professor positions tend to attract people who enjoy being professors, who find the positives outweigh the negatives, and so they're not attracted to other possible positions or pursuits.
Sunday, March 15, 2009
Classes
Richard Lipton ends a recent blog post with the question:
My question today is how can we better educate students to solve problems, to apply knowledge across boundaries, and in general be better problem solvers? What do you think?
When talking with a visiting prospective graduate student, we discuss the fact that our requirements include taking 10 classes (recently reduced from 12). The student seemed to think that's a very large number of classes to have to take.
I'm a big believer in graduate students taking classes. I'm obviously biased having had to suffer through many requirements as a graduate student at Berkeley. And I freely admit, some of the classes felt like suffering.
But the classes provided me with a strong basis to build on. I found classes good for introducing me to the basics of an area, so that I could understand the problems and communicate with people in that area. Classes also introduced me a much larger group of people, working in a larger variety of areas, than I would have experienced on my own.
And while here I'm certainly talking here about theory people getting to know about things outside of theory (as well as systems people getting to know some theory and AI and other things as well), I think the argument holds as well solely for the increasingly balkanized theory community just knowing about what each other is doing. These days, there seem to be boundaries between different areas of theory that are as high as boundaries between theory and systems. (See, for example, this recent post and comments on "European theory".)
I've heard the arguments against classes. The biggest is that they take time away from research. There are plenty of counter-arguments. (Most students don't really spend 40+ hours a week on research. It's important to train for the long-term future career and not just focus on research. There are important other benefits of classes -- meeting people and being able, if needed, to teach in multiple areas.) Other complaints focus on specific implementations. (Why should I have to take a graduate OS class if I took one as an undergraduate? Fine, let's find something else worthwhile for you to take.)
I think one reason for the trend in reducing or even eliminating class requirements is students generally don't like taking classes, especially in areas not directly related to their research. Why should they? It's work they have to do right now, and the payoff is generally long-term. As educators, we should find ways to make this tradeoff better when possible -- but more importantly, as educators, we have to explain clearly to the students that this type of education really is in their long-term interest.
To my mind, classes (and class requirements) are still a powerful tool for educating students on how to solve problems, including across boundaries. The trend away from classes, which should include both "core knowledge" for computer science as well as opportunities (or even requirements) to explore connections between CS and other fields, does not benefit us.
My question today is how can we better educate students to solve problems, to apply knowledge across boundaries, and in general be better problem solvers? What do you think?
When talking with a visiting prospective graduate student, we discuss the fact that our requirements include taking 10 classes (recently reduced from 12). The student seemed to think that's a very large number of classes to have to take.
I'm a big believer in graduate students taking classes. I'm obviously biased having had to suffer through many requirements as a graduate student at Berkeley. And I freely admit, some of the classes felt like suffering.
But the classes provided me with a strong basis to build on. I found classes good for introducing me to the basics of an area, so that I could understand the problems and communicate with people in that area. Classes also introduced me a much larger group of people, working in a larger variety of areas, than I would have experienced on my own.
And while here I'm certainly talking here about theory people getting to know about things outside of theory (as well as systems people getting to know some theory and AI and other things as well), I think the argument holds as well solely for the increasingly balkanized theory community just knowing about what each other is doing. These days, there seem to be boundaries between different areas of theory that are as high as boundaries between theory and systems. (See, for example, this recent post and comments on "European theory".)
I've heard the arguments against classes. The biggest is that they take time away from research. There are plenty of counter-arguments. (Most students don't really spend 40+ hours a week on research. It's important to train for the long-term future career and not just focus on research. There are important other benefits of classes -- meeting people and being able, if needed, to teach in multiple areas.) Other complaints focus on specific implementations. (Why should I have to take a graduate OS class if I took one as an undergraduate? Fine, let's find something else worthwhile for you to take.)
I think one reason for the trend in reducing or even eliminating class requirements is students generally don't like taking classes, especially in areas not directly related to their research. Why should they? It's work they have to do right now, and the payoff is generally long-term. As educators, we should find ways to make this tradeoff better when possible -- but more importantly, as educators, we have to explain clearly to the students that this type of education really is in their long-term interest.
To my mind, classes (and class requirements) are still a powerful tool for educating students on how to solve problems, including across boundaries. The trend away from classes, which should include both "core knowledge" for computer science as well as opportunities (or even requirements) to explore connections between CS and other fields, does not benefit us.
Friday, March 13, 2009
Thinking Big (Memory)
I gave one of my standard programming assignments this year -- finding minimum spanning trees on big random graphs. It seems for many students this is the first time they've experienced the possibility of not having enough memory using a straightforward implementation; they actually have to think about memory issues.
Year by year I've slowly increased the size of the graphs I require from students. This year, I think I left it too small; some students got away without having to think too hard about the memory issues. I'll have to up it for next year. Part of the problem is that I leave implementation details -- like what language they program in -- up to them. My framework is that I care about them being able to get the results -- I don't care about the details like which language they use. On the other hand, this looseness leads to large variations in how much students have to worry about various things. Java can handle memory issues for you (at the expense of speed); your laptop might exhibit different performance (including whether or not it runs out of memory) than a campus account (which is where the code should eventually be able to run).
One issue that became big this year was students wanting to use Python. I tried to tell them it was a bad idea, but many students like the high-level language and the sleekness of the resulting code. Unfortunately, standard constructs in Python are memory hogs, causing crashes or impossible slowness. Many of the students who started in Python had to eventually rewrite their code in another language -- or failed to deal with graph sizes that the assignment asked for.
I didn't design the programming assignments in my algorithms class to teach students about programming. But I find these exercises really stretch some of their programming skills, making them think about questions (what's the best language to use? what's the bottleneck here -- time or memory? how can I debug/test my code effectively?) that they need to learn to think about sometime, and perhaps aren't dealt with sufficiently in introductory classes any more.
Year by year I've slowly increased the size of the graphs I require from students. This year, I think I left it too small; some students got away without having to think too hard about the memory issues. I'll have to up it for next year. Part of the problem is that I leave implementation details -- like what language they program in -- up to them. My framework is that I care about them being able to get the results -- I don't care about the details like which language they use. On the other hand, this looseness leads to large variations in how much students have to worry about various things. Java can handle memory issues for you (at the expense of speed); your laptop might exhibit different performance (including whether or not it runs out of memory) than a campus account (which is where the code should eventually be able to run).
One issue that became big this year was students wanting to use Python. I tried to tell them it was a bad idea, but many students like the high-level language and the sleekness of the resulting code. Unfortunately, standard constructs in Python are memory hogs, causing crashes or impossible slowness. Many of the students who started in Python had to eventually rewrite their code in another language -- or failed to deal with graph sizes that the assignment asked for.
I didn't design the programming assignments in my algorithms class to teach students about programming. But I find these exercises really stretch some of their programming skills, making them think about questions (what's the best language to use? what's the bottleneck here -- time or memory? how can I debug/test my code effectively?) that they need to learn to think about sometime, and perhaps aren't dealt with sufficiently in introductory classes any more.
Wednesday, March 11, 2009
New Cuckoo Hashing Paper
Moni Naor nicely pointed me to a new preprint he has up on de-amortizing cuckoo hashing. (The paper is entitled De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results, by Arbitman, Naor, and Segev.)
The "starting point" of the paper was the technique for de-amortizing cuckoo hashing Adam Kirsch and I suggested in our 2007 Allerton paper, which involved using a content addressable memory as a queue for move operations when doing cuckoo hashing. (See the blog post I wrote way back when here.) Our work was experimental, as we didn't analyze the queueing process, which is based on the number of moves needed when doing an insertion.
Their new paper obtains provable results, showing that there a cuckoo hashing scheme that has constant worst-case insertion time (with high probability over any polynomial number of steps), by utilizing a logarithmic-sized spare space (to queue pending moves, and stash items that can't be placed in the table, a la the Kirsch/Mitzenmacher/Wieder stash technique described here). They even show that only poly-logarithmic independent hash functions suffice, using a new result from Braverman. The only big caveat is that they analyze only the case of 2-choice cuckoo hashing, where the structure of the underlying random graph related to the cuckoo hashing process is better understood. Because of this, the result only allows loads of up to 50%.
It's a very, very nice result with a lot of theoretical pieces to put together. The use of the Braverman result appears to be a general technique for lessening the randomness requirements of these sorts of problems that is interesting in its own right, never mind the useful advance in the theory of cuckoo hashing. I was also excited to see that they used simulations to enhance their theoretical results (for example, providing a conjecture on how small a constant number of moves would be required at each step -- apparently 3 suffices, a quite reasonable number!) and show off how practical the scheme is. Imagine, a theoretical paper with simulations! (Hooray!)
Overall I think the paper is a strong step forward in demonstrating the practical applicability of cuckoo hashing, while at the same time providing strong formal theoretical guarantees. I still believe cuckoo hashing (along with multiple-choice hashing) will become a (the?) standard approach for hashing in the years to come, so of course I'm excited to see results like this. There remain plenty of further open questions -- more than 2 choices? tight bounds on queue sizes? -- so don't worry, there are still interesting things left to do.
The "starting point" of the paper was the technique for de-amortizing cuckoo hashing Adam Kirsch and I suggested in our 2007 Allerton paper, which involved using a content addressable memory as a queue for move operations when doing cuckoo hashing. (See the blog post I wrote way back when here.) Our work was experimental, as we didn't analyze the queueing process, which is based on the number of moves needed when doing an insertion.
Their new paper obtains provable results, showing that there a cuckoo hashing scheme that has constant worst-case insertion time (with high probability over any polynomial number of steps), by utilizing a logarithmic-sized spare space (to queue pending moves, and stash items that can't be placed in the table, a la the Kirsch/Mitzenmacher/Wieder stash technique described here). They even show that only poly-logarithmic independent hash functions suffice, using a new result from Braverman. The only big caveat is that they analyze only the case of 2-choice cuckoo hashing, where the structure of the underlying random graph related to the cuckoo hashing process is better understood. Because of this, the result only allows loads of up to 50%.
It's a very, very nice result with a lot of theoretical pieces to put together. The use of the Braverman result appears to be a general technique for lessening the randomness requirements of these sorts of problems that is interesting in its own right, never mind the useful advance in the theory of cuckoo hashing. I was also excited to see that they used simulations to enhance their theoretical results (for example, providing a conjecture on how small a constant number of moves would be required at each step -- apparently 3 suffices, a quite reasonable number!) and show off how practical the scheme is. Imagine, a theoretical paper with simulations! (Hooray!)
Overall I think the paper is a strong step forward in demonstrating the practical applicability of cuckoo hashing, while at the same time providing strong formal theoretical guarantees. I still believe cuckoo hashing (along with multiple-choice hashing) will become a (the?) standard approach for hashing in the years to come, so of course I'm excited to see results like this. There remain plenty of further open questions -- more than 2 choices? tight bounds on queue sizes? -- so don't worry, there are still interesting things left to do.
Tuesday, March 10, 2009
Friday, March 06, 2009
STOC Registration server up
I'm told you can now register for STOC 2009. Please sign up! (Early date is April 28.)
Other STOC work behind the scenes at this point involves getting the ancillary stuff ready for the publisher (not a particularly pleasant part of the job) -- including the paper schedule. I hope to have a preliminary schedule up next week (or the week after) to help people plan their trips.
Other STOC work behind the scenes at this point involves getting the ancillary stuff ready for the publisher (not a particularly pleasant part of the job) -- including the paper schedule. I hope to have a preliminary schedule up next week (or the week after) to help people plan their trips.
Thursday, March 05, 2009
A Note to Networking/Systems People
I am sure it sometimes seems on this blog that I'm "critical" of the theory community. I am! Because constructive criticism is, I think, a useful thing.
Today, I unleash some criticism of the networking community. This complaint is based on my own experience with my papers, as well as experience I have on the other side (as a PC member), on how for example data structure papers are thought of when submitted to these communities. Mind you, this criticism isn't universal -- several people seem willing to look at and accept more theoretical papers in these communities. But not everyone...
(Still, keep in mind, I'm taking an extreme point of view here, to make a point, which I understand may inspire some interesting comments.)
When a paper comes in to a systems/networks where the main contribution is a general data structure (in my papers, this has often been a hash table construction) that naturally could apply to various networking problems (e.g., hash tables are commonly used in MANY router-level applications), and the main point of the paper is how to better make these data structures work for these applications (i.e., we consider reducing accesses to slow memory, trying to get it down from say 2 to 1, or consider pin count/hardware parallelization tradeoffs), THIS IS A NETWORKING (OR SYSTEMS) PAPER. I often hear the argument "This is a general data structure, it belongs in a theory conference," and this is just wrong, for multiple reasons.
1) Please don't try to make generality a negative. I know in systems papers you are accustomed to seeing detailed results on a single application (and when a data structure paper also includes that, it can also be a very good thing). But generality itself is a good thing, not a bad thing. (For SIGCOMM this year, one of the review fields is "longevity" -- sometimes these papers aim to have an expected long lifetime, rather than focusing on the short-term impact of a particular application).
2) In the same vein, don't dismiss a paper just because in it's evaluation, it judges the data structure on raw performance (time per insertion/deletion/lookup in a hash table) and/or on simulated data. Yes, I know, by measuring performance at the data structure level instead of the application level we haven't shown this is better on "any particular" application -- but we have tried instead to show it's better for a wide range of present and future applications! (If we haven't demonstrated this effectively, then it makes more sense to reject.) Similarly, in many settings (e.g., hashing), all data is artificial. You may have to pick a good enough hash function for your data to look random (see e.g. Mitzenmacher/Vadhan), but then it doesn't matter what your initial data was.
The first two points can also be summarized the following way: your conference has page limits. We've decided to focus on using the pages available to show off the general, widely encompassing benefits of our approach; don't dismiss us just because we haven't dug into specific implementation details for a particular application (which can take pages to do, and months to program/gather data on, and really doesn't add nearly as much to the paper as what we've put in).
3) This type of work doesn't go to a theory conference: often, in such papers, there is little of "theoretical" interest -- these are engineering papers, not papers with new theoretical techniques or technically challenging theoretical proofs (when we have proofs in this type of paper). Theory people will wonder why we're caring about these details of the hardware/software/data model -- it's only interesting in the context of your applications.
4) Indeed, the point of writing such a paper is that we are looking (or trying to look) precisely at the application and systems issues. This paper is meant for you! In fact, sometimes on the theory side it seems the only way we can get you to notice a new and powerful technique is to write papers for your community, so please try to let us in -- it will speed up adoption of these new, powerful techniques, helping your community overall. (My examples are Bloom filters, d-left hashing, etc.)
One worry seems to be that you'll accept a paper that turns out not to have the payout you'd have expected. That will happen! (By the way, it's also happening with all the other less theoretical papers you're accepting now...) But you need to have a pipeline of these ideas coming in -- who knows where the next basic data structure idea that will have a lot of applications (e.g. a Bloom filter) will come from! I worry you're cutting off your pipeline.
I understand that these papers will face the same high bar that everyone else does to get into say SIGCOMM; that's not my complaint. But in multiple settings I've seen such papers essentially dismissed out of hand, which seems unfortunate. I often hear (and even promote!) the idea that theory people could be working on more practical things. When we do try to meet you halfway, leave the door open a little for us...
Today, I unleash some criticism of the networking community. This complaint is based on my own experience with my papers, as well as experience I have on the other side (as a PC member), on how for example data structure papers are thought of when submitted to these communities. Mind you, this criticism isn't universal -- several people seem willing to look at and accept more theoretical papers in these communities. But not everyone...
(Still, keep in mind, I'm taking an extreme point of view here, to make a point, which I understand may inspire some interesting comments.)
When a paper comes in to a systems/networks where the main contribution is a general data structure (in my papers, this has often been a hash table construction) that naturally could apply to various networking problems (e.g., hash tables are commonly used in MANY router-level applications), and the main point of the paper is how to better make these data structures work for these applications (i.e., we consider reducing accesses to slow memory, trying to get it down from say 2 to 1, or consider pin count/hardware parallelization tradeoffs), THIS IS A NETWORKING (OR SYSTEMS) PAPER. I often hear the argument "This is a general data structure, it belongs in a theory conference," and this is just wrong, for multiple reasons.
1) Please don't try to make generality a negative. I know in systems papers you are accustomed to seeing detailed results on a single application (and when a data structure paper also includes that, it can also be a very good thing). But generality itself is a good thing, not a bad thing. (For SIGCOMM this year, one of the review fields is "longevity" -- sometimes these papers aim to have an expected long lifetime, rather than focusing on the short-term impact of a particular application).
2) In the same vein, don't dismiss a paper just because in it's evaluation, it judges the data structure on raw performance (time per insertion/deletion/lookup in a hash table) and/or on simulated data. Yes, I know, by measuring performance at the data structure level instead of the application level we haven't shown this is better on "any particular" application -- but we have tried instead to show it's better for a wide range of present and future applications! (If we haven't demonstrated this effectively, then it makes more sense to reject.) Similarly, in many settings (e.g., hashing), all data is artificial. You may have to pick a good enough hash function for your data to look random (see e.g. Mitzenmacher/Vadhan), but then it doesn't matter what your initial data was.
The first two points can also be summarized the following way: your conference has page limits. We've decided to focus on using the pages available to show off the general, widely encompassing benefits of our approach; don't dismiss us just because we haven't dug into specific implementation details for a particular application (which can take pages to do, and months to program/gather data on, and really doesn't add nearly as much to the paper as what we've put in).
3) This type of work doesn't go to a theory conference: often, in such papers, there is little of "theoretical" interest -- these are engineering papers, not papers with new theoretical techniques or technically challenging theoretical proofs (when we have proofs in this type of paper). Theory people will wonder why we're caring about these details of the hardware/software/data model -- it's only interesting in the context of your applications.
4) Indeed, the point of writing such a paper is that we are looking (or trying to look) precisely at the application and systems issues. This paper is meant for you! In fact, sometimes on the theory side it seems the only way we can get you to notice a new and powerful technique is to write papers for your community, so please try to let us in -- it will speed up adoption of these new, powerful techniques, helping your community overall. (My examples are Bloom filters, d-left hashing, etc.)
One worry seems to be that you'll accept a paper that turns out not to have the payout you'd have expected. That will happen! (By the way, it's also happening with all the other less theoretical papers you're accepting now...) But you need to have a pipeline of these ideas coming in -- who knows where the next basic data structure idea that will have a lot of applications (e.g. a Bloom filter) will come from! I worry you're cutting off your pipeline.
I understand that these papers will face the same high bar that everyone else does to get into say SIGCOMM; that's not my complaint. But in multiple settings I've seen such papers essentially dismissed out of hand, which seems unfortunate. I often hear (and even promote!) the idea that theory people could be working on more practical things. When we do try to meet you halfway, leave the door open a little for us...
Subscribe to:
Posts (Atom)