Background: As part of the "getting a new Dean" process, we're undergoing a "make a 5 year plan" process. The School of Engineering and Applied Sciences (SEAS) had a mini-retreat just before classes started to discuss it all.
I wandered into lunch the other day and saw some other faculty from SEAS -- but from well outside computer science -- already eating, so I joined them. In our friendly discussions, they asked about our growth plan, and asked me to justify it further to them. One point I brought up was that we did a lot of "service" to the rest of the university. Sure, they said, they knew about the very large intro programming class, but that was just one class. What else?
I listed off several of our other classes that they didn't seem really aware of -- our course for non-majors CS 1 (Great Ideas in Computer Science) and our Gen Ed course Bits, our more advanced programming classes CS 51 and CS 61, our new interdisciplinary visualization course CS 171 and our new course on design of usable interactive systems CS179, and probably a few others. I then mentioned that even our theory courses (introduction to complexity, and introduction to algorithms and data structures) were attracting a lot of non-majors, and pointed out that they each had 80 students last year. (We have about 30-40 or so CS majors a year right now.)
Their jaws literally dropped. One of them asked me, multiple times, how there could be 80 people at Harvard who were interested in taking Algorithms. (While I, of course, always wonder why it's so few.) I still have doubts that they believed me; I think I ought to get something official-looking from the registrar and send it to them.
Now, admittedly, last year's class was big -- my class this year looks to be a more normal about 50 or so. But I was still surprised by their surprise. I check out the class sizes around SEAS to get a feel for what's going on every year (we usually get an e-mail with course counts). Also, I'm pretty sure I mention my class size fairly often to other SEAS faculty when the opportunity arises, but apparently less often than I think. I was left with the feeling that I, and maybe the rest of the CS faculty, needed to engage the other SEAS faculty a bit more and let them know more about what we're doing. In particular, as another faculty member said to me, "When they talk about a really big class, they mean 40 students. When we talk about a really big class, we mean over 100."
I'm not exactly a shy, retiring type. (I mean, c'mon, I blog.) But I'll be upping my efforts to make sure others at Harvard have a better idea of what we're doing, especially in terms of teaching our undergraduates.
Sunday, January 31, 2010
Friday, January 29, 2010
Paper updates
We updated our Swoopo paper, Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank, mostly making small writing improvements and typo fixes that came up when we were preparing our conference submission. It's still up on the arxiv. In an effort for student promotion, I'll point you to grad-student-co-author Giorgos Zervas's web site, which also contains links to our condensed submission version and our dataset.
Also now up on the arxiv is a preprint (submitted) by myself and Raissa D'Souza on Local cluster aggregation models of explosive percolation. We were looking at variations of the Achlioptas process. (I've promised myself I'll stop making fun of Dimitris for his keen ability to get a process named after himself -- sometime around 2020.) In the basic Achlioptas process you start with an empty graph of n nodes, and at each step you choose 2 edges at random, and add one to the graph according to some deterministic rule, such as add the edge that minimizes the size of the resulting merged component. Usually there is an associated goal, such as to delay (or speed up) the emergence of a giant component in the graph. As you might expect, the power of choosing an edge allows one to potentially delay or speed up the emergence of a giant component substantially. Our paper looks at what seem to be a simpler class of similar processes, the most basic of which is that at each step you choose 2 edges at random that are adjacent to some randomly chosen vertex v. That is, we look at local variations, where the choice can be thought of as the vertex v choosing which of 2 random edges to add to the graph. It doesn't seem these local variations have been analyzed previously. We look at differential equations that describe the underlying process and empirically examine whether such processes have discontinuous phase transitions, like the original Achlioptas process appears to have. We're promoting the idea that these "local variations" may prove simpler to analyze fully and rigorously than the original variations, for which there still remain many open questions.
Addendum: Just in case there's any confusion, I should add that Dimitris in no way named the Achlioptas process after himself. (I was just teasing him.) He was the first to suggest and promote the study of the process and when others wrote the first papers about it they nicely credited him by calling it an Achlioptas process. The name has rightfully stuck.
Also now up on the arxiv is a preprint (submitted) by myself and Raissa D'Souza on Local cluster aggregation models of explosive percolation. We were looking at variations of the Achlioptas process. (I've promised myself I'll stop making fun of Dimitris for his keen ability to get a process named after himself -- sometime around 2020.) In the basic Achlioptas process you start with an empty graph of n nodes, and at each step you choose 2 edges at random, and add one to the graph according to some deterministic rule, such as add the edge that minimizes the size of the resulting merged component. Usually there is an associated goal, such as to delay (or speed up) the emergence of a giant component in the graph. As you might expect, the power of choosing an edge allows one to potentially delay or speed up the emergence of a giant component substantially. Our paper looks at what seem to be a simpler class of similar processes, the most basic of which is that at each step you choose 2 edges at random that are adjacent to some randomly chosen vertex v. That is, we look at local variations, where the choice can be thought of as the vertex v choosing which of 2 random edges to add to the graph. It doesn't seem these local variations have been analyzed previously. We look at differential equations that describe the underlying process and empirically examine whether such processes have discontinuous phase transitions, like the original Achlioptas process appears to have. We're promoting the idea that these "local variations" may prove simpler to analyze fully and rigorously than the original variations, for which there still remain many open questions.
Addendum: Just in case there's any confusion, I should add that Dimitris in no way named the Achlioptas process after himself. (I was just teasing him.) He was the first to suggest and promote the study of the process and when others wrote the first papers about it they nicely credited him by calling it an Achlioptas process. The name has rightfully stuck.
Tuesday, January 26, 2010
Teaching, Day One
First day of classes for me today. It's "spring", sort of, so I must be teaching Algorithms and Data Structures.
Last year there were about 80 students in the class, a remarkable reversal after several years of decline -- the year before that there were fewer than 40. Of course, this was not successful for everyone, so even though our intro programming class has continued to grow, I'm expecting fewer students this year. The fall theory class (our intro complexity class) had about 60 students, and usually my numbers are a few less than that. They had about 80 students last year too. So my expectation for the final course size is in the (mid) 50s.
When I got to class I wondered if the room assignment hadn't been posted -- only about 20 people showed up. But lots of people wandered in a few minutes late, and then more and more as the class went on. The joys of Harvard's shopping period (though I can't recall ever quite such a number of late arrivals). I'm pretty sure at least 60 showed up at some point during the class; my initial estimate may be pretty close.
What's very odd this year is that on day one there's 48 people signed up for the Distance Education version of the class through the Extension School. (Still time to sign up!) That's definitely more than normal. A big fraction of those students are likely to drop out -- many quickly figure out the class is more than they can handle -- but that's still a much larger starting number than usual.
Hopefully, by next week, I'll have more accurate numbers for both versions of the class.
Lecture went fine. Very well, in fact, in that a number of students raised their hands in response to my questions, and they had, as a whole, very good answers and insights. Optimistically, I'm looking forward to an above-average class this year.
Last year there were about 80 students in the class, a remarkable reversal after several years of decline -- the year before that there were fewer than 40. Of course, this was not successful for everyone, so even though our intro programming class has continued to grow, I'm expecting fewer students this year. The fall theory class (our intro complexity class) had about 60 students, and usually my numbers are a few less than that. They had about 80 students last year too. So my expectation for the final course size is in the (mid) 50s.
When I got to class I wondered if the room assignment hadn't been posted -- only about 20 people showed up. But lots of people wandered in a few minutes late, and then more and more as the class went on. The joys of Harvard's shopping period (though I can't recall ever quite such a number of late arrivals). I'm pretty sure at least 60 showed up at some point during the class; my initial estimate may be pretty close.
What's very odd this year is that on day one there's 48 people signed up for the Distance Education version of the class through the Extension School. (Still time to sign up!) That's definitely more than normal. A big fraction of those students are likely to drop out -- many quickly figure out the class is more than they can handle -- but that's still a much larger starting number than usual.
Hopefully, by next week, I'll have more accurate numbers for both versions of the class.
Lecture went fine. Very well, in fact, in that a number of students raised their hands in response to my questions, and they had, as a whole, very good answers and insights. Optimistically, I'm looking forward to an above-average class this year.
Sunday, January 24, 2010
On Formatting
Matt Welsh's recent amusing-but-also-sad post on having two recent conference submissions rejected for violating format requirements reminded me how much I hate wasting time dealing with formatting. Matt calls for a standardized template -- as he writes:
But isn't it time that we define a single standard for conference paper formatting that everyone uses?
(With such a system, conferences could still vary the length of the paper they accepted -- but the style file would be the same.)
I think that would be a great step. In the same spirit, I'd also like to see less focus on page limits -- both for submissions and for the final version. (Ostensibly, the final version should be closely related to the actual submission -- so if you're going to relax page limits for the final version, it seems best to do so for the submission version as well.) I think the recent change for SODA -- allowing up to 20 page conference papers -- is a great idea.
I understand that, in some cases (where printing is involved), some sort of page limit may be needed -- although with less and less printing of full proceedings, it's less clear that this is an important consideration. I also believe that page limits can force people to improve their writing -- bad writing and excessively wordy writing generally go together. (If we remove page limits, we'll have to tell people in reviews more frequently when they need to cut things down or even out in their papers.)
But the effort spent on meeting arbitrary page limits -- just the time spent on formatting -- seems silly at this point. And often it forces you to cut content. I can't count the number of times I've had a review say, "You should have included this...", where my response would be, "We did include this, but had to cut it to make it fit into the page limit..." (Yes, you can create multiple versions, and post the full versions online -- except for double-blind conferences, like SIGCOMM, of course -- but that involves yet further overhead, when you have to update to deal with reviewer comments, and...) And if your paper is rejected from one conference, to submit to another, you have to re-format and create another version to meet their arbitrary format and page limit standards.
In some ways, I'm glad that Matt is out there, talking about the papers being rejected for formatting. And I hope it starts happening to more people, more often. Because I worry that the only way for change to happen is for bad things to start happening to good papers so that people will start to realize that the current system is just bizarre and broken, and a revolution needs to occur. Perhaps I'm wrong, and slow evolutionary change -- with 20 page papers a SODA being an example -- will lead us the right way. If so, I encourage PC chairs to experiment with flexibility in their formatting requirements.
But isn't it time that we define a single standard for conference paper formatting that everyone uses?
(With such a system, conferences could still vary the length of the paper they accepted -- but the style file would be the same.)
I think that would be a great step. In the same spirit, I'd also like to see less focus on page limits -- both for submissions and for the final version. (Ostensibly, the final version should be closely related to the actual submission -- so if you're going to relax page limits for the final version, it seems best to do so for the submission version as well.) I think the recent change for SODA -- allowing up to 20 page conference papers -- is a great idea.
I understand that, in some cases (where printing is involved), some sort of page limit may be needed -- although with less and less printing of full proceedings, it's less clear that this is an important consideration. I also believe that page limits can force people to improve their writing -- bad writing and excessively wordy writing generally go together. (If we remove page limits, we'll have to tell people in reviews more frequently when they need to cut things down or even out in their papers.)
But the effort spent on meeting arbitrary page limits -- just the time spent on formatting -- seems silly at this point. And often it forces you to cut content. I can't count the number of times I've had a review say, "You should have included this...", where my response would be, "We did include this, but had to cut it to make it fit into the page limit..." (Yes, you can create multiple versions, and post the full versions online -- except for double-blind conferences, like SIGCOMM, of course -- but that involves yet further overhead, when you have to update to deal with reviewer comments, and...) And if your paper is rejected from one conference, to submit to another, you have to re-format and create another version to meet their arbitrary format and page limit standards.
In some ways, I'm glad that Matt is out there, talking about the papers being rejected for formatting. And I hope it starts happening to more people, more often. Because I worry that the only way for change to happen is for bad things to start happening to good papers so that people will start to realize that the current system is just bizarre and broken, and a revolution needs to occur. Perhaps I'm wrong, and slow evolutionary change -- with 20 page papers a SODA being an example -- will lead us the right way. If so, I encourage PC chairs to experiment with flexibility in their formatting requirements.
Tuesday, January 19, 2010
Housework
The Chronicle of Higher Education has an article up titled Time Crunch for Female Scientists : They Do More Housework Than Men. Worth reading, understanding, and discussing, although I admit some trepidation, as such posts generally receive some bizarre commentary. (One point of note; this is not just an issue that affects scientists, but "...because a successful scientific career demands more than 40 hours a week, she said, female scientists could be especially affected.")
Monday, January 18, 2010
New TCS postdocs/jobs website at CCI
There's a new page http://intractibility.princeton.edu/jobs/ that was set up as a centralized location for advertising postdocs and jobs for theoretical computer science. There's been quite a bit of talk for some time that TCS could use a site like this, so I'd like to advertise it here and encourage people to use it. And thanks to those who are putting in the work behind the scenes.
Thursday, January 14, 2010
Letters and Rights
I generally assume (undergraduate) students know to waive their rights to look at a letter of recommendation when they ask me to write one, but I recently ran into a student that did not. I explained that my default was that they had to waive their rights, and I'd send in the letter after the checkbox had been changed. If you don't look, though, I find it's easy to miss which box they've checked as you're filling the form out on line.
I simply prefer my confidential letters to be confidential. I understand that waiving their rights is not any sort of guarantee that they won't see the letter, but I think the understanding is important: I'm writing an evaluation of them to my colleagues, and that information is, as a matter of default policy, not meant for their eyes, so I can be forthright in expressing my opinions.
I simply prefer my confidential letters to be confidential. I understand that waiving their rights is not any sort of guarantee that they won't see the letter, but I think the understanding is important: I'm writing an evaluation of them to my colleagues, and that information is, as a matter of default policy, not meant for their eyes, so I can be forthright in expressing my opinions.
Wednesday, January 13, 2010
Algorithms and Data Structures : Course Goals
Richard Lipton has an excellent blog post up right now on "What should a course on complexity theory cover?" where he describes what he is putting in his graduate course and what he expects students to get out of it. It seemed like a great idea, making me think that I should write a similar post for my undergraduate course (Algorithms and Data Structures).
I have a somewhat different take on the problem than Richard, though. He ends up creating a list of things (definitions and theorems) he thinks student should know after his class. I admit I think a bit more in terms of high-level concepts and skills I want students to get out of the course. (I think both approaches can work.) My list includes:
1. Students should understand the basics of algorithm/data structure language and notation; in particular: order notation, what it means (and doesn't mean!), and how to calculate running times of algorithms.
2. Students should learn how to model a problem through proper abstraction. In particular, they should learn how to set problems into the language of graphs, linear programs, etc.
3. Students should learn basic algorithmic techniques: greedy, divide and conquer, dynamic programming, linear programming.
4. Students should learn what is required for a formal and rigorous argument (even if they are not so good at writing one themselves). They should learn how to argue/prove correctness of algorithms and data structures in the contexts above.
5. Students should clearly understand the power of reductions -- not just to show problems are hard, but to show problems are easy, by using the solution of one problem to solve another.
6. Students should obtain some insight into the power of randomness in algorithmic thinking.
7. Students should practice translating algorithmic ideas into working code. It is hoped they will learn the importance of thinking before coding (choosing the right approach), and that issues such as memory requirements and running time can and should be reasoned about before implementation.
8. Students should learn that correctness, like computation time and memory, is just a "resource" that can be traded off with the others, by learning the notion of an approximation algorithm.
9. Students should learn the basic of heuristics and heuristic techniques, so that if asked in practice to solve an NP-hard problem (in the sense of coming up with a very good but not optimal solution), they have some idea of what approaches might give them reasonable answers.
10. Students should see some really cool, unusual, interesting algorithms and data structures, and be forced to work on some really hard, challenging problems, to challenge their thinking and demonstrate the power of theory.
There's probably more I could add, but those seem like ten clear objectives I have for the students who take my class. Perhaps in another post I can elaborate on how I try to see those objective are met.
Like Richard, I should end the post by asking the important open questions:
What have I left out? What should I leave out? What do you think?
I have a somewhat different take on the problem than Richard, though. He ends up creating a list of things (definitions and theorems) he thinks student should know after his class. I admit I think a bit more in terms of high-level concepts and skills I want students to get out of the course. (I think both approaches can work.) My list includes:
1. Students should understand the basics of algorithm/data structure language and notation; in particular: order notation, what it means (and doesn't mean!), and how to calculate running times of algorithms.
2. Students should learn how to model a problem through proper abstraction. In particular, they should learn how to set problems into the language of graphs, linear programs, etc.
3. Students should learn basic algorithmic techniques: greedy, divide and conquer, dynamic programming, linear programming.
4. Students should learn what is required for a formal and rigorous argument (even if they are not so good at writing one themselves). They should learn how to argue/prove correctness of algorithms and data structures in the contexts above.
5. Students should clearly understand the power of reductions -- not just to show problems are hard, but to show problems are easy, by using the solution of one problem to solve another.
6. Students should obtain some insight into the power of randomness in algorithmic thinking.
7. Students should practice translating algorithmic ideas into working code. It is hoped they will learn the importance of thinking before coding (choosing the right approach), and that issues such as memory requirements and running time can and should be reasoned about before implementation.
8. Students should learn that correctness, like computation time and memory, is just a "resource" that can be traded off with the others, by learning the notion of an approximation algorithm.
9. Students should learn the basic of heuristics and heuristic techniques, so that if asked in practice to solve an NP-hard problem (in the sense of coming up with a very good but not optimal solution), they have some idea of what approaches might give them reasonable answers.
10. Students should see some really cool, unusual, interesting algorithms and data structures, and be forced to work on some really hard, challenging problems, to challenge their thinking and demonstrate the power of theory.
There's probably more I could add, but those seem like ten clear objectives I have for the students who take my class. Perhaps in another post I can elaborate on how I try to see those objective are met.
Like Richard, I should end the post by asking the important open questions:
What have I left out? What should I leave out? What do you think?
Tuesday, January 12, 2010
New Harry Lewis Opinion at HuffPo
Harry Lewis has a new opinion piece up at Huffington Post. The title,
Larry Summers, Robert Rubin : Will The Harvard Shadow Elite Bankrupt The University And The Country?
gives some idea of where he's coming from...
Larry Summers, Robert Rubin : Will The Harvard Shadow Elite Bankrupt The University And The Country?
gives some idea of where he's coming from...
Saturday, January 09, 2010
Visiting Dartmouth for a Research Symposium
I spent the day at Dartmouth, as I was asked to be "keynote speaker" for their Computer Science Annual Research Symposium. Essentially, it's their own mini-conference for a day, with a mix of faculty and graduate student talks as well as posters, both giving graduate students a chance to present and letting everyone get a better idea of what everyone is working on. They're giving best student talk and best poster awards to motivate students.
They've done a very nice job in organizing it - they seem to have corralled most students and faculty into coming, and they have brought in huge quantities of food (a known motivator for student attendance). [Note to self: Dartmouth CS apparently gets its breakfast muffins from "Lou's". Those things are amazingly good.] The presentations are going well and I'm sure it's a useful experience for students. So I'm trying to learn from this how we might do something similar at Harvard.
We used to have something like this at Harvard -- we had an "Industrial Partners" day where we'd try to bring people from labs/companies in and do posters and presentations (including some by graduate students) in a similar fashion. At some point, it fell below critical mass, but we're perennially thinking of how to bring something like it back. You do have to get people to commit to it, and to find time for it -- notice Dartmouth has chosen to hold it on a Saturday, and at a time where the campus is otherwise pretty dead. Maybe that's the approach that would work for us. I've found it's hard to schedule anything on a regular M-F time slot with a group of faculty, even for a hour, never mind a whole day.
Another issue with scheduling a research symposium is that we, already, suffer from talk overload. We have our own colloquium; the various groups (theory, AI, systems) run their own seminars or lunch-talks; there's plenty of other talks around Harvard run by various departments or organizations; and there's a seemingly endless number of talks nearby (at MIT, Microsoft NE, and other places). The problem about having so many talks is you start to lose interest in organizing more talks, and arguably the graduate students benefit at least as much by presenting in their own group seminars. But visiting Dartmouth today has given me some further evidence that the good that can come out of a symposium day like this might make it worthwhile. Perhaps the key is to let the graduate students plan and run the day, so that they own it, and feel responsible for making it a success.
How many of you have a similar research symposium day, how does it work, and what do you think of it?
They've done a very nice job in organizing it - they seem to have corralled most students and faculty into coming, and they have brought in huge quantities of food (a known motivator for student attendance). [Note to self: Dartmouth CS apparently gets its breakfast muffins from "Lou's". Those things are amazingly good.] The presentations are going well and I'm sure it's a useful experience for students. So I'm trying to learn from this how we might do something similar at Harvard.
We used to have something like this at Harvard -- we had an "Industrial Partners" day where we'd try to bring people from labs/companies in and do posters and presentations (including some by graduate students) in a similar fashion. At some point, it fell below critical mass, but we're perennially thinking of how to bring something like it back. You do have to get people to commit to it, and to find time for it -- notice Dartmouth has chosen to hold it on a Saturday, and at a time where the campus is otherwise pretty dead. Maybe that's the approach that would work for us. I've found it's hard to schedule anything on a regular M-F time slot with a group of faculty, even for a hour, never mind a whole day.
Another issue with scheduling a research symposium is that we, already, suffer from talk overload. We have our own colloquium; the various groups (theory, AI, systems) run their own seminars or lunch-talks; there's plenty of other talks around Harvard run by various departments or organizations; and there's a seemingly endless number of talks nearby (at MIT, Microsoft NE, and other places). The problem about having so many talks is you start to lose interest in organizing more talks, and arguably the graduate students benefit at least as much by presenting in their own group seminars. But visiting Dartmouth today has given me some further evidence that the good that can come out of a symposium day like this might make it worthwhile. Perhaps the key is to let the graduate students plan and run the day, so that they own it, and feel responsible for making it a success.
How many of you have a similar research symposium day, how does it work, and what do you think of it?
Tuesday, January 05, 2010
New Paper: Information Asymmetries in Pay-Per-Bid Auctions
I'm happy to announce a new paper that answers, among other questions, how I spent a huge chunk of my winter holiday break. The paper is by me, John Byers, and the graduate student we're co-advising, Giorgos Zervas, and is entitled Information Asymmetries in Pay-Per-Bid Auctions : How Swoopo Makes Bank (arxiv link, pdf). As you might guess from the title, the paper is about pay-per-bid auctions, the current popular example of which is Swoopo, which you might want to examine if only for cultural awareness. (Besides the Swoopo site, you can read a bit about Swoopo from major news sites here and here.) The trick in pay-per-bid auctions is the seller doesn't make the big money on the final item price, but on the bids themselves, which have a cost. The paper was a lot of work, but it was also a lot of fun both to work on and write; hopefully some of you will find it nearly as fun to read. The full version right now is about 40 pages; a shorter version will be submitted to EC 2010 next week. Our abstract provides a good opening description:
Our starting point was looking at the assumptions of the model, which require remarkable symmetry: the players all know how many other players are in the auction, they all have the same value for the item, and they all have the same cost to make a bid. We argue that in practice none of these assumptions are viable, and in fact there are huge asymmetries (particularly asymmetries in information) that throw off the basic model. A fun example is that if some players pay less to bid than others, and the others don't know or realize that, the profit in a pay-per-bid auction grows. So auction sites can (potentially) make money by giving some people a cheaper price for bids! Analyzing these asymmetries, we find huge profit potential for pay-per-bid auctioneers that may explain Swoopo's profitability. We also consider the very interesting Swoop It Now feature, which lets users turn bids in a lost auction into a down payment for the auction item, and show how it can naturally lead to Swoopo auctions turning into games of chicken -- which also seems to benefit Swoopo's bottom line.
Innovative auction methods can be exploited to increase profits, with Shubik's famous "dollar auction" perhaps being the most widely known example. Recently, some mainstream e-commerce web sites have apparently achieved the same end on a much broader scale, by using "pay-per-bid" auctions to sell items, from video games to bars of gold. In these auctions, bidders incur a cost for placing each bid in addition to (or sometimes in lieu of) the winner's final purchase cost. Thus even when a winner's purchase cost is a small fraction of the item's intrinsic value, the auctioneer can still profit handsomely from the bid fees. Our work provides novel analyses for these auctions, based on both modeling and datasets derived from auctions at Swoopo.com, the leading pay-per-bid auction site. While previous modeling work predicts profit-free equilibria, we analyze the impact of information asymmetry broadly, as well as Swoopo features such as bidpacks and the Swoop it Now option specifically, to quantify the effects of imperfect information in these auctions. We find that even small asymmetries across players (cheaper bids, better estimates of other players' intent, different valuations of items, fully committed players willing to play "chicken") can increase the auction duration well beyond that predicted by previous work and thus skew the auctioneer's profit disproportionately. Finally, we discuss our findings in the context of a dataset of thousands of live auctions we observed on Swoopo, which enables us also to examine behavioral factors, such as the power of aggressive bidding. Ultimately, our findings show that even with fully rational players, if players overlook or are unaware any of these factors, the result is outsized profits for pay-per-bid auctioneers.Here's a bit more description. As a starting point, there have been a few working papers that present essentially the same basic equilibrium analysis of Swoopo auctions. A problem is that the analysis results in zero profit for Swoopo, and it's easy to check that, instead, Swoopo appears to be raking in the bucks. The working papers offer some possible solutions, but they seemed (to us) fairly unconvincing.
Our starting point was looking at the assumptions of the model, which require remarkable symmetry: the players all know how many other players are in the auction, they all have the same value for the item, and they all have the same cost to make a bid. We argue that in practice none of these assumptions are viable, and in fact there are huge asymmetries (particularly asymmetries in information) that throw off the basic model. A fun example is that if some players pay less to bid than others, and the others don't know or realize that, the profit in a pay-per-bid auction grows. So auction sites can (potentially) make money by giving some people a cheaper price for bids! Analyzing these asymmetries, we find huge profit potential for pay-per-bid auctioneers that may explain Swoopo's profitability. We also consider the very interesting Swoop It Now feature, which lets users turn bids in a lost auction into a down payment for the auction item, and show how it can naturally lead to Swoopo auctions turning into games of chicken -- which also seems to benefit Swoopo's bottom line.
Sunday, January 03, 2010
How Much Grading Should Professors Do?
One of the outcomes of the Harvard budget crisis is that the budget for Teaching Assistants has been brought into line. At Harvard, we've been ridiculously spoiled with TAs for many years now, with a TA for roughly every 12-15 students; last year, I was able to get 6 undergrad TAs for 80 students in my Algorithms and Data Structures class. This year, I'll have a more reasonable TA for every 18-20 students or so. Yes, I know that remains quite luxurious compared to many places; I'm not complaining. But it is a change I have to deal with.
One of the big responsibilities for my TAs is grading. I assign a fairly substantial load of homework in my undergrad class, and unfortunately the number of problems where you can just check the answer without reading through the student's work is small. (They often have to prove things.) And even checking answers takes a long time. Given the new TA/student ratio, it seems unfair (and, quite frankly, unworkable, assuming TAs stick to anything close to their supposed working hours) to have the TAs grade the same homeworks in the past. So, it seems, I'll have to change something. The natural options seem to be:
1) Reduce the assignments. Take what would in the past have been the hardest problem on each assignment and make it an ungraded "challenge problem", for instance.
2) Change the scope/style of the assignments. Less proof-type work, more numerical exercises where you can just check the final answer.
3) Introduce probabilistic grading. Only 5 of the 6 problems will be graded -- you just don't know which 5 in advance.
4) Allow people to work in pairs for assignments. Fewer writeups to grade.
5) Grade more myself.
The first four options all have fairly big negatives associated with them. (Actually, I don't have a problem with probabilistic grading, but I have no doubt it would cause bitter complaints from the students, even if I gave a lecture explaining why it was a reasonable approach. There would always be students coming up afterward to complain that they would have gotten a better grade if I just graded all of their problems, and I don't look forward to having to explain the policy to higher-ups. And working in pairs isn't necessarily a negative, but they can already talk about problems together, and they can work in pairs for programming assignments; I think they should practice writing up proofs themselves.)
The main downside to the final option is, of course, to me personally. I do, already, do some of the grading. It's very time-consuming. Even if the time per assignment is small, multiply by the number of students (I expect 60 this year) and we're talking a good number of hours.
So how much grading should a professor do? How much are others of you doing? Or does anyone have other creative suggestions for solutions before the semester starts?
One of the big responsibilities for my TAs is grading. I assign a fairly substantial load of homework in my undergrad class, and unfortunately the number of problems where you can just check the answer without reading through the student's work is small. (They often have to prove things.) And even checking answers takes a long time. Given the new TA/student ratio, it seems unfair (and, quite frankly, unworkable, assuming TAs stick to anything close to their supposed working hours) to have the TAs grade the same homeworks in the past. So, it seems, I'll have to change something. The natural options seem to be:
1) Reduce the assignments. Take what would in the past have been the hardest problem on each assignment and make it an ungraded "challenge problem", for instance.
2) Change the scope/style of the assignments. Less proof-type work, more numerical exercises where you can just check the final answer.
3) Introduce probabilistic grading. Only 5 of the 6 problems will be graded -- you just don't know which 5 in advance.
4) Allow people to work in pairs for assignments. Fewer writeups to grade.
5) Grade more myself.
The first four options all have fairly big negatives associated with them. (Actually, I don't have a problem with probabilistic grading, but I have no doubt it would cause bitter complaints from the students, even if I gave a lecture explaining why it was a reasonable approach. There would always be students coming up afterward to complain that they would have gotten a better grade if I just graded all of their problems, and I don't look forward to having to explain the policy to higher-ups. And working in pairs isn't necessarily a negative, but they can already talk about problems together, and they can work in pairs for programming assignments; I think they should practice writing up proofs themselves.)
The main downside to the final option is, of course, to me personally. I do, already, do some of the grading. It's very time-consuming. Even if the time per assignment is small, multiply by the number of students (I expect 60 this year) and we're talking a good number of hours.
So how much grading should a professor do? How much are others of you doing? Or does anyone have other creative suggestions for solutions before the semester starts?
Wednesday, December 30, 2009
New Year's Again
It's time for the annual New Year posting. Last year, I talked about the potential power of affirmations -- in the sense of thinking about concrete goals you hope to accomplish for the year. This year, I'll work in the same theme, but I'll be a bit more specific, and specifically for graduate students.
Now is a good time for graduate students to ask themselves some important questions:
1) If you're planning on graduating this coming semester (or the end of summer), what do you need to do to get there? Do you have a timeline -- with a few extra weeks of padding for unforeseen delays or writer's block? Are you on top of your job search? What can you do to make the thesis and job search go more smoothly? (Hint -- how can you make things easier on your advisor, faculty readers, letter-writers, etc.?)
It's a challenging and scary time -- but you can and will do it, and graduating will feel good. Very, very good.
2) If you're not graduating this year, are you ready to commit to graduating next year? Now is a great time to talk to your advisor and plan what needs to be done to get you out the door within 18 months. (Almost surely your advisor will be thrilled to see such initiative -- even if they don't think you're ready...)
There's an old saying that there's two types of students -- those who are 6 months from graduating and those who are 2 years+ from graduating. The point is that it's mindset -- when you start thinking you're ready to graduate, you'll start moving toward graduating. Are you ready to start thinking that way?
3) If you're early on in the process, what can you do to make this year a good one? Perhaps you can start a collaboration with someone somewhat outside your area -- generally a good experience -- through a class project this semester or by just talking to people about what they're up to. Figure out ways you can talk to people beside your advisor, like going to seminars or serving as a "grad student host" for visitors. Also, now is the time to be applying for summer internships.
4) Finally, if you've found yourself struggling with graduate school, and wondering if you've made the right choice, now is the time for some careful thinking. Think about what you want, possibly talk about it with friends and colleagues -- and then talk to your advisor. Maybe you and your advisor can come up with a plan to make things better. Or maybe you're better off leaving (with a useful Master's Degree), and now is the right time to look for jobs and finish off remaining projects before the end of the academic year. It can be much better to ponder this all now rather than wait until summer nears and realize your options are limited.
Whatever you're up to, I wish you all a happy, healthy, successful 2010.
Now is a good time for graduate students to ask themselves some important questions:
1) If you're planning on graduating this coming semester (or the end of summer), what do you need to do to get there? Do you have a timeline -- with a few extra weeks of padding for unforeseen delays or writer's block? Are you on top of your job search? What can you do to make the thesis and job search go more smoothly? (Hint -- how can you make things easier on your advisor, faculty readers, letter-writers, etc.?)
It's a challenging and scary time -- but you can and will do it, and graduating will feel good. Very, very good.
2) If you're not graduating this year, are you ready to commit to graduating next year? Now is a great time to talk to your advisor and plan what needs to be done to get you out the door within 18 months. (Almost surely your advisor will be thrilled to see such initiative -- even if they don't think you're ready...)
There's an old saying that there's two types of students -- those who are 6 months from graduating and those who are 2 years+ from graduating. The point is that it's mindset -- when you start thinking you're ready to graduate, you'll start moving toward graduating. Are you ready to start thinking that way?
3) If you're early on in the process, what can you do to make this year a good one? Perhaps you can start a collaboration with someone somewhat outside your area -- generally a good experience -- through a class project this semester or by just talking to people about what they're up to. Figure out ways you can talk to people beside your advisor, like going to seminars or serving as a "grad student host" for visitors. Also, now is the time to be applying for summer internships.
4) Finally, if you've found yourself struggling with graduate school, and wondering if you've made the right choice, now is the time for some careful thinking. Think about what you want, possibly talk about it with friends and colleagues -- and then talk to your advisor. Maybe you and your advisor can come up with a plan to make things better. Or maybe you're better off leaving (with a useful Master's Degree), and now is the right time to look for jobs and finish off remaining projects before the end of the academic year. It can be much better to ponder this all now rather than wait until summer nears and realize your options are limited.
Whatever you're up to, I wish you all a happy, healthy, successful 2010.
Wednesday, December 23, 2009
New Result : Tight Asymptotic Bounds for the Deletion Channel with Small Deletion Probabilities
Posting will be light over winter break, in part because so little is going on, but more because I'm busy working on papers for upcoming deadlines. I'll describe a fun little nugget, which is being submitted to ISIT, joint work with Adam Kalai and Madhu Sudan. (The starting point for the result was my giving my survey talk on deletion channels at MSRNE... always nice when something like that works out!) The goal was to get better bounds on the capacity of the deletion channel. (If you haven't been reading the blog long enough: In a binary deletion channel, n bits are sent, and the channel deletes each bit independently with probability p. So, for example, the message sent might be 00110011 and the received message could be 010011 if the 2nd and 4th bits were deleted.) It was known that for deletion probability p the capacity was at least 1-H(p). We show an essentially tight upper bound of 1-(1-o(1))H(p), where the o(1) term goes to 0 as p goes to 0. Here's the draft (a full two weeks before the submission deadline!).
In English, the binary deletion channel looks very much like a standard binary symmetric error channel when p is small. This is not the case when p is larger. (Here's a link to my survey on deletion channels and related channels for more info.)
Here's an attempt at describing the intuition. Let's first look back at the error channel. Suppose we had a code of N codewords each with n bits and a perfect decoder for at most pn errors. Then here's a funny way I could store data -- instead of storing n bits directly, I could store a codeword with pn errors that I introduce into it. To get back my data, I decode. Notice that when I decode, I automatically also determine the locations where the errors were introduced. This gives me N*{n choose pn} \approx N2^{nH(p)} possibilities, each of which I can use to represent a different data sequence. Since I'm only storing n bits, I better have N2^{nH(p)} <= 2^n, or else I've found a way to store more than n bits of data into n bits. So (log N)/n, or the rate, satisfies (log N)/n <= (1-H(p)). This is a different way of thinking about the Shannon upper bound on capacity. Of course, it's sweeping away details -- like what if you don't have a perfect decoder -- but it gives the right sort of insight into the bound. Now consider the deletion channel, and apply the same sort of reasoning. Suppose that we had a decoder for the deletion channel, and further, we had a method of determining which bits were deleted given the received string. Then we could use it to store data in the same way as above and obtain a similar (1-H(p)) upper bound on the rate. Now we have to worry about the details -- like what to do when you don't have a perfect decoder. But more importantly, we have to show that, most of the time with non-trivial probability, you can use the decoder to guess which bits were deleted. (This is where we use the fact that p is going to 0.) The details work out. Surprisingly, this doesn't seem to have been known before. The best (only) upper bound I know for this case previously was the work by Fertonani and Duman, mentioned in this blog post. Their upper bound as p goes to 0 was of the form 1 - cp for some constant c, so it was different in kind.
Slowly but surely, the mysteries of the deletion channel become, well, less mysterious.
In English, the binary deletion channel looks very much like a standard binary symmetric error channel when p is small. This is not the case when p is larger. (Here's a link to my survey on deletion channels and related channels for more info.)
Here's an attempt at describing the intuition. Let's first look back at the error channel. Suppose we had a code of N codewords each with n bits and a perfect decoder for at most pn errors. Then here's a funny way I could store data -- instead of storing n bits directly, I could store a codeword with pn errors that I introduce into it. To get back my data, I decode. Notice that when I decode, I automatically also determine the locations where the errors were introduced. This gives me N*{n choose pn} \approx N2^{nH(p)} possibilities, each of which I can use to represent a different data sequence. Since I'm only storing n bits, I better have N2^{nH(p)} <= 2^n, or else I've found a way to store more than n bits of data into n bits. So (log N)/n, or the rate, satisfies (log N)/n <= (1-H(p)). This is a different way of thinking about the Shannon upper bound on capacity. Of course, it's sweeping away details -- like what if you don't have a perfect decoder -- but it gives the right sort of insight into the bound. Now consider the deletion channel, and apply the same sort of reasoning. Suppose that we had a decoder for the deletion channel, and further, we had a method of determining which bits were deleted given the received string. Then we could use it to store data in the same way as above and obtain a similar (1-H(p)) upper bound on the rate. Now we have to worry about the details -- like what to do when you don't have a perfect decoder. But more importantly, we have to show that, most of the time with non-trivial probability, you can use the decoder to guess which bits were deleted. (This is where we use the fact that p is going to 0.) The details work out. Surprisingly, this doesn't seem to have been known before. The best (only) upper bound I know for this case previously was the work by Fertonani and Duman, mentioned in this blog post. Their upper bound as p goes to 0 was of the form 1 - cp for some constant c, so it was different in kind.
Slowly but surely, the mysteries of the deletion channel become, well, less mysterious.
Friday, December 18, 2009
Text-book Algorithms at SODA (Guest Post, Mikkel Thorup)
Mikkel Thorup sent in the following guest post:
Text-book algorithms at SODA
This is a pitch for promoting good text-book algorithms at SODA. Erdos promoted book proofs, but book algorithms are in some sense far more important in that they could end up being understood and used by every programmer with a degree in CS. This can yield a huge external impact, and I do think we do ourselves and the world a big favor taking this work seriously. Instead of taking papers on this theme (which would, incidentally, be a great idea), perhaps the area could serve as the basis for a lighter afternoon entertainment session, providing cool stuff that one could take home and show students.
To me the greatest text-book algorithms work well in both theory and practice. They have a cool non-obvious idea that will impress the students, yet, after first you get the idea, they are simple to understand and implement. Unfortunately, to get into a top conference, it is best if you also have 5-10 pages worth of complications. Typically the complications are not themselves that interesting, but they are helpful in making the paper look hard enough; otherwise some referees are bound to complain about lack of meat (fat?).
Note that by insisting on complications, we narrow the contributers to the small pond of theoreticians. Simple efficient algorithms are sought by every smart practitioner, and it no coincidence that many of the elegant algorithms theorists analyze are discovered outside theory. On the other hand, I do think theorists are the ones in the best position to develop great simple algorithms thanks to our fundamental understanding, and I think we should celebrate it when it
happens.
To be more clear, let me present a somewhat controversial example of what I consider a great text-book contribution which is buried in a paper [DHKP97] about very different issues. The example is for universal hashing (low collision probability) where the new scheme is simpler and much faster than the classic method.
Suppose we want universal hashing of w-bit keys to u-bit indices. The classic solution is to pick a prime p>2^w, and a random a in [p], and then use the hash function
h_a(x) = ((ax) mod p) mod 2^u --- math terminology.
The alternative from [DHKP97] is to let b be a random odd w-bit number and use
h_b(x) = ((bx) mod 2^w) div 2^(w-u) --- math terminology.
To prove that this is universal is a nice text book exercise using that odd numbers are relative prime to powers of two.
There may be no obvious advantage of one scheme over the other on an established theory model like the unit-cost RAM, but the difference is major in reality. Implementing the scheme from [DHKP97] is extremely simple with standard portable C-code. We exploit that C-multiplication (*) of unsigned w-bit numbers is done mod 2^w, and get
h_b(x) = (b*x) >> (w-u) --- C code.
By comparison, the implementation of the classic scheme is problematic. One issue is that the mod operation is very slow, and has been so for more than 30 years. Already when Carter and Wegman introduced universal hashing at STOC'77, they were aware of the issue.
They suggested using Mersenne primes (p=2^i-1) allowing us to bypass mod p with some faster bit-trick operations. Even using that, we still have the issue that the classic scheme requires us to compute ax exactly, and ax has more than 2w bits. Since w-bit multiplication is mod 2^w, we need 6 w-bit multiplications to compute ax in its full length, and that is even ignoring the issue of mod p. If 2w-bit multiplication is available, it suffices with two multiplications, but these are often more expensive than w-bit multiplication.
The impact of the scheme from [DHKP97] is big in that it unites theory and practice in what is probably the world's most common non-trivial inner loop. The classic prime based scheme is so slow that practitioners have come up with all kinds of alternatives that are not even remotely universal, e.g., some combination of shifts and xor, hence no entropy. The new scheme is faster than all these hacks, so now we can convince practitioners to use real universal hashing, often leading them to better more robust results.
Is the above theory? It is certainly involves a mathematical observation about the use of relative primality, and I like to think of algorithms as math with mathematically well-defined impact on computing. To get a mathematically well-defined measure, we can, for example, look at how many operations are needed in C, which has been used for efficient portable code since 1972. A theoretical irritant is that we have a whole array of measures, e.g., depending on how we count 2w-bit multiplication and mod-operations. However, the new scheme is clearly better: the variations only affect exactly how much it is better---some factor between 3 and 15.
It is a bit interesting to contrast the above situation with, say, the more robust world of polytime approximation with, say, a very well-defined difference between a worst-case factor 2 and 3. Translating to reality, if the polytime algorithm is superquadratic, it is typically too slow to finish on large scale problems. Moreover, one often gets much better results using simple heuristics with bad worst-case behavior.
For the hashing we are not just talking worst-case but all-cases (same instructions performed on all keys), and I have never tried a real computer on which the new scheme didn't gain at least a factor 4 in speed compared with the classic scheme tuned with Mersenne primes. On top of that, the new scheme is much simpler to implement. While this difference is very convincing for anyone experienced with efficient programming, it may be a bit hard to appreciate for "THEORY of Computing" conferences like STOC/FOCS. However, I see algorithms and SODA more as a "Theory of COMPUTING" with a scope closer to the reality of computing, hence with a bigger interest in text-book algorithms that unite theory and practice. Highlighting such simple, but incredibly useful, practical computing algorithms would both increase the impact of SODA (and arguably theory more generally) and provide a useful distinguishing characteristic for the conference.
[DHKP97] M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen.
A reliable randomized algorithm for the closest-pair problem.
J. Algorithms, 25:19-51, 1997.
Text-book algorithms at SODA
This is a pitch for promoting good text-book algorithms at SODA. Erdos promoted book proofs, but book algorithms are in some sense far more important in that they could end up being understood and used by every programmer with a degree in CS. This can yield a huge external impact, and I do think we do ourselves and the world a big favor taking this work seriously. Instead of taking papers on this theme (which would, incidentally, be a great idea), perhaps the area could serve as the basis for a lighter afternoon entertainment session, providing cool stuff that one could take home and show students.
To me the greatest text-book algorithms work well in both theory and practice. They have a cool non-obvious idea that will impress the students, yet, after first you get the idea, they are simple to understand and implement. Unfortunately, to get into a top conference, it is best if you also have 5-10 pages worth of complications. Typically the complications are not themselves that interesting, but they are helpful in making the paper look hard enough; otherwise some referees are bound to complain about lack of meat (fat?).
Note that by insisting on complications, we narrow the contributers to the small pond of theoreticians. Simple efficient algorithms are sought by every smart practitioner, and it no coincidence that many of the elegant algorithms theorists analyze are discovered outside theory. On the other hand, I do think theorists are the ones in the best position to develop great simple algorithms thanks to our fundamental understanding, and I think we should celebrate it when it
happens.
To be more clear, let me present a somewhat controversial example of what I consider a great text-book contribution which is buried in a paper [DHKP97] about very different issues. The example is for universal hashing (low collision probability) where the new scheme is simpler and much faster than the classic method.
Suppose we want universal hashing of w-bit keys to u-bit indices. The classic solution is to pick a prime p>2^w, and a random a in [p], and then use the hash function
h_a(x) = ((ax) mod p) mod 2^u --- math terminology.
The alternative from [DHKP97] is to let b be a random odd w-bit number and use
h_b(x) = ((bx) mod 2^w) div 2^(w-u) --- math terminology.
To prove that this is universal is a nice text book exercise using that odd numbers are relative prime to powers of two.
There may be no obvious advantage of one scheme over the other on an established theory model like the unit-cost RAM, but the difference is major in reality. Implementing the scheme from [DHKP97] is extremely simple with standard portable C-code. We exploit that C-multiplication (*) of unsigned w-bit numbers is done mod 2^w, and get
h_b(x) = (b*x) >> (w-u) --- C code.
By comparison, the implementation of the classic scheme is problematic. One issue is that the mod operation is very slow, and has been so for more than 30 years. Already when Carter and Wegman introduced universal hashing at STOC'77, they were aware of the issue.
They suggested using Mersenne primes (p=2^i-1) allowing us to bypass mod p with some faster bit-trick operations. Even using that, we still have the issue that the classic scheme requires us to compute ax exactly, and ax has more than 2w bits. Since w-bit multiplication is mod 2^w, we need 6 w-bit multiplications to compute ax in its full length, and that is even ignoring the issue of mod p. If 2w-bit multiplication is available, it suffices with two multiplications, but these are often more expensive than w-bit multiplication.
The impact of the scheme from [DHKP97] is big in that it unites theory and practice in what is probably the world's most common non-trivial inner loop. The classic prime based scheme is so slow that practitioners have come up with all kinds of alternatives that are not even remotely universal, e.g., some combination of shifts and xor, hence no entropy. The new scheme is faster than all these hacks, so now we can convince practitioners to use real universal hashing, often leading them to better more robust results.
Is the above theory? It is certainly involves a mathematical observation about the use of relative primality, and I like to think of algorithms as math with mathematically well-defined impact on computing. To get a mathematically well-defined measure, we can, for example, look at how many operations are needed in C, which has been used for efficient portable code since 1972. A theoretical irritant is that we have a whole array of measures, e.g., depending on how we count 2w-bit multiplication and mod-operations. However, the new scheme is clearly better: the variations only affect exactly how much it is better---some factor between 3 and 15.
It is a bit interesting to contrast the above situation with, say, the more robust world of polytime approximation with, say, a very well-defined difference between a worst-case factor 2 and 3. Translating to reality, if the polytime algorithm is superquadratic, it is typically too slow to finish on large scale problems. Moreover, one often gets much better results using simple heuristics with bad worst-case behavior.
For the hashing we are not just talking worst-case but all-cases (same instructions performed on all keys), and I have never tried a real computer on which the new scheme didn't gain at least a factor 4 in speed compared with the classic scheme tuned with Mersenne primes. On top of that, the new scheme is much simpler to implement. While this difference is very convincing for anyone experienced with efficient programming, it may be a bit hard to appreciate for "THEORY of Computing" conferences like STOC/FOCS. However, I see algorithms and SODA more as a "Theory of COMPUTING" with a scope closer to the reality of computing, hence with a bigger interest in text-book algorithms that unite theory and practice. Highlighting such simple, but incredibly useful, practical computing algorithms would both increase the impact of SODA (and arguably theory more generally) and provide a useful distinguishing characteristic for the conference.
[DHKP97] M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen.
A reliable randomized algorithm for the closest-pair problem.
J. Algorithms, 25:19-51, 1997.
Wednesday, December 16, 2009
Avoiding Travel
I'm spending the morning as part of the committee for a thesis defense over in Europe. I'm watching the talk over Skype; we're using a conference call for sound (and as a backup); I have copies of the slides on my laptop.
Is it the same as being there? No. But it's probably 90+% as good in terms of the experience of listening to the defense. It saves me a full day of plane travel (never mind other time overhead), it saves the institution multiple thousands of dollars in air fare and other travel expenses, and if you happen to feel that flying has negative externalities due to greenhouse gas emissions, then it's good for other reasons as well.
If the timing had worked out better, I might have made the trip, and arranged to give some talks to amortize the "travel cost" over more than the defense. But I'm glad to avoid the travel -- thank goodness for modern technology. And as much as I enjoyed the NSDI PC meeting Monday, if it hadn't been down the block at MIT, I would have enjoyed it much less. (Indeed, the location of the meeting was one of the incentives to accept the PC invitation.) I'm still waiting for the tech to get good enough so we can have an online PC meeting (w/video, sound, etc. to mimic the face-to-face discussions of a face-to-face meeting) that we don't have to travel to.
Is it the same as being there? No. But it's probably 90+% as good in terms of the experience of listening to the defense. It saves me a full day of plane travel (never mind other time overhead), it saves the institution multiple thousands of dollars in air fare and other travel expenses, and if you happen to feel that flying has negative externalities due to greenhouse gas emissions, then it's good for other reasons as well.
If the timing had worked out better, I might have made the trip, and arranged to give some talks to amortize the "travel cost" over more than the defense. But I'm glad to avoid the travel -- thank goodness for modern technology. And as much as I enjoyed the NSDI PC meeting Monday, if it hadn't been down the block at MIT, I would have enjoyed it much less. (Indeed, the location of the meeting was one of the incentives to accept the PC invitation.) I'm still waiting for the tech to get good enough so we can have an online PC meeting (w/video, sound, etc. to mimic the face-to-face discussions of a face-to-face meeting) that we don't have to travel to.
Monday, December 14, 2009
LiveBlogging NSDI PC Meeting
My post today is live-blogging the NSDI PC Meeting -- with a delay for security purposes, of course.
My take on the reviews (and from past experience) is that the NSDI PC is a very, very tough committee. People are looking for exciting and novel ideas, with clear and detailed experiments demonstrating real-world benefits (which usually means comparing against a real implementation from previous work). It's hard to get all that into one paper -- and to get everything so that the reviewers are all happy. And once in a while you can run into a reviewer like me, who expects your "good idea" to also have a suitable mathematical formulation when that makes sense. (If you're claiming to optimize something, I -- and others -- want a clear notion of what you're trying to optimize, and why your idea should help optimize it.)
So it's not surprising that, 4th paper in from the top, we've already hit our first paper where we're deferring our decision instead of accepting, and we're already getting some detailed discussions on whether a paper is good enough to accept. We'll have to speed up to make dinner....
As if to underscore that I did not have a great set of papers, I have just a few that I reviewed in our "DiscussFirst" pile, which takes us through lunch. Good thing I can keep busy with blog entries. And I have a review to write for another conference...
My submission appears (tentatively) accepted. Hooray! For this PC, we're not kicking people out of the room for conflicts -- people are just supposed to be keeping their mouths shut on papers where they have a conflict. For PC members with papers, however, you get kicked out of the room. So I've just spent a tense 15 minutes or so outside, but I'm happy to see the news once I'm back in. (More on this paper in another post....) Overall, I'd say (as expected) PC papers had no special treatment -- they were as harshly judged as all the other papers.
We're now having an interesting discussion about "experience" papers -- what do you learn after building/running a system after several years? A lot of people really think that having experience papers is a good idea, but there's some discussion of the bar -- what makes such papers interesting, and how interesting should they be? (Good anecdotes, but with quantifiable data to support the lessons.)
We're now about in the middle of the papers we're meant to discuss. Things here could go either way. Lots of technical discussion. As an aside, I can give my point of view on what are "hot topics". Data centers seems to be a big topic. There seemed to be a number of papers about scheduling/optimizing/choosing the right configuration in cloud computing systems -- how that could be done without making the programmer explicitly figuring out what configuration to use (but just give hints, or have the tools figure it out automatically). There's a significant amount of EE-focused papers -- essentially, trying to gains with some detailed, explicit look at the wireless signal, for example.
Headed to the end, more or less on schedule. Now we're assigning shepherds to all of the papers.
Sorry to say, I won't be revealing any information on specific papers -- everyone will find out when the "official" messages go out, or from their own connections on the PC...
I think the PC chairs have done a good job pushing us to keep on schedule; I think the discussions have been detailed and interesting. I think the committee is perhaps overly harsh (a target of 30 papers for about 175 submissions, or 17-18% acceptance; we ended up with 29). But I think we did a good job overall, and have earned our post-meeting dinner out.
My take on the reviews (and from past experience) is that the NSDI PC is a very, very tough committee. People are looking for exciting and novel ideas, with clear and detailed experiments demonstrating real-world benefits (which usually means comparing against a real implementation from previous work). It's hard to get all that into one paper -- and to get everything so that the reviewers are all happy. And once in a while you can run into a reviewer like me, who expects your "good idea" to also have a suitable mathematical formulation when that makes sense. (If you're claiming to optimize something, I -- and others -- want a clear notion of what you're trying to optimize, and why your idea should help optimize it.)
So it's not surprising that, 4th paper in from the top, we've already hit our first paper where we're deferring our decision instead of accepting, and we're already getting some detailed discussions on whether a paper is good enough to accept. We'll have to speed up to make dinner....
As if to underscore that I did not have a great set of papers, I have just a few that I reviewed in our "DiscussFirst" pile, which takes us through lunch. Good thing I can keep busy with blog entries. And I have a review to write for another conference...
My submission appears (tentatively) accepted. Hooray! For this PC, we're not kicking people out of the room for conflicts -- people are just supposed to be keeping their mouths shut on papers where they have a conflict. For PC members with papers, however, you get kicked out of the room. So I've just spent a tense 15 minutes or so outside, but I'm happy to see the news once I'm back in. (More on this paper in another post....) Overall, I'd say (as expected) PC papers had no special treatment -- they were as harshly judged as all the other papers.
We're now having an interesting discussion about "experience" papers -- what do you learn after building/running a system after several years? A lot of people really think that having experience papers is a good idea, but there's some discussion of the bar -- what makes such papers interesting, and how interesting should they be? (Good anecdotes, but with quantifiable data to support the lessons.)
We're now about in the middle of the papers we're meant to discuss. Things here could go either way. Lots of technical discussion. As an aside, I can give my point of view on what are "hot topics". Data centers seems to be a big topic. There seemed to be a number of papers about scheduling/optimizing/choosing the right configuration in cloud computing systems -- how that could be done without making the programmer explicitly figuring out what configuration to use (but just give hints, or have the tools figure it out automatically). There's a significant amount of EE-focused papers -- essentially, trying to gains with some detailed, explicit look at the wireless signal, for example.
Headed to the end, more or less on schedule. Now we're assigning shepherds to all of the papers.
Sorry to say, I won't be revealing any information on specific papers -- everyone will find out when the "official" messages go out, or from their own connections on the PC...
I think the PC chairs have done a good job pushing us to keep on schedule; I think the discussions have been detailed and interesting. I think the committee is perhaps overly harsh (a target of 30 papers for about 175 submissions, or 17-18% acceptance; we ended up with 29). But I think we did a good job overall, and have earned our post-meeting dinner out.
Friday, December 11, 2009
Harvard Governance
Harry Lewis (and Fred Abernathy) take a stand against the Harvard Corporation. Required reading for anyone associated with Harvard, or interested in its current predicaments.
Thursday, December 10, 2009
News Items
The people at Microsoft Research New England are excited to announce that Boaz Barak will be joining them. I imagine the situation is similar to their hiring of Madhu Sudan. They continue to build up a remarkable collection of researchers.
Harvard's Allston complex is officially suspended.
JeffE doesn't post so much these days, so you might have missed this great post with his favorite useless theorem. (I hope this starts a series of "Favorite Useless Theorems" -- please send him, or me, if you have examples of your own.)
Nela Rybowicz, staff senior editor for IEEE (and who I've dealt with for pretty much all of my Transactions on Information Theory papers), informed me that she'll soon be retiring. She'll be missed.
Harvard's Allston complex is officially suspended.
JeffE doesn't post so much these days, so you might have missed this great post with his favorite useless theorem. (I hope this starts a series of "Favorite Useless Theorems" -- please send him, or me, if you have examples of your own.)
Nela Rybowicz, staff senior editor for IEEE (and who I've dealt with for pretty much all of my Transactions on Information Theory papers), informed me that she'll soon be retiring. She'll be missed.
Wednesday, December 09, 2009
TSA Oops
You may have heard on the news that the TSA (temporarily) put up their Screening Management Standard Operating Procedure on the web. As pointed out on this blog (and elsewhere), they made a small error:
"So the decision to publish it on the Internet is probably a questionable one. On top of that, however, is where the real idiocy shines. They chose to publish a redacted version of the document, hiding all the super-important stuff from the public. But they apparently don’t understand how redaction works in the electronic document world. See, rather than actually removing the offending text from the document they just drew a black box on top of it. Turns out that PDF documents don’t really care about the black box like that and the actual content of the document is still in the file."
Oops. Apparently, somebody hasn't read Harry Lewis's book Blown to Bits; the start of Chapter 3 discusses several similar cases where somebody thought they had redacted something from a PDF file... but didn't.
"So the decision to publish it on the Internet is probably a questionable one. On top of that, however, is where the real idiocy shines. They chose to publish a redacted version of the document, hiding all the super-important stuff from the public. But they apparently don’t understand how redaction works in the electronic document world. See, rather than actually removing the offending text from the document they just drew a black box on top of it. Turns out that PDF documents don’t really care about the black box like that and the actual content of the document is still in the file."
Oops. Apparently, somebody hasn't read Harry Lewis's book Blown to Bits; the start of Chapter 3 discusses several similar cases where somebody thought they had redacted something from a PDF file... but didn't.
Subscribe to:
Posts (Atom)