Got a note from the ACM that SIGCOMM is being live Webcast the next few days. (I'm not in Toronto for it -- hello to everyone who is!)
A simple click and I'm listening to SIGCOMM talks. Fun.
The link is http://www.weyond.com/sigcomm/webcast/
Listen in as you can.
Tuesday, August 16, 2011
Monday, August 01, 2011
Fun Links, via Google+
One fun aspect of being on Google+ is occasionally a link comes along worth further notice.
The first, from David Karger, is a link to a report (by Democrats, says David) refuting a previous report (by Republicans) that had argued that the NSF was wasting a bunch of money on frivolous research. The link is here. Jon Kleinberg was one of the listed "frivolous" projects -- apparently studying pictures on social networks isn't considered important by those with an agenda -- and he has a brief response in the report.
The second is an editorial by S. Keshav, about the "hyper-critical attitude of paper reviewers", spurred by the fact that CCR had no technical articles, because all the submissions were rejected. I certainly have something to say on the issue (having, for example, recently had a conference rejection where 3 knowledgeable reviewers said the paper should be accepted, one unknowledgeable reviewer said the paper was too theoretically challenging for the systems audience, and apparently decided to take an uninformed stand at the PC meeting...). But rather than tell a long story here, I'll just point you to the editorial....
The first, from David Karger, is a link to a report (by Democrats, says David) refuting a previous report (by Republicans) that had argued that the NSF was wasting a bunch of money on frivolous research. The link is here. Jon Kleinberg was one of the listed "frivolous" projects -- apparently studying pictures on social networks isn't considered important by those with an agenda -- and he has a brief response in the report.
The second is an editorial by S. Keshav, about the "hyper-critical attitude of paper reviewers", spurred by the fact that CCR had no technical articles, because all the submissions were rejected. I certainly have something to say on the issue (having, for example, recently had a conference rejection where 3 knowledgeable reviewers said the paper should be accepted, one unknowledgeable reviewer said the paper was too theoretically challenging for the systems audience, and apparently decided to take an uninformed stand at the PC meeting...). But rather than tell a long story here, I'll just point you to the editorial....
Friday, July 22, 2011
Tact
Early in the week, I was excited to find out that, apparently, it was perfectly appropriate for us professors to call (at least, already graduated) students assholes, publicly, because if it's good enough for Larry Summers, it's good enough for me. (Or see here as well.) That seemed very cool to me.
But now it seems the Winklevosses are asking for redress from Drew Faust, so the question of whether I can go around openly insulting students' character without worrying about whether anyone at Harvard will care is, for now, at least somewhat open.
(Further commentary, including some people at Harvard pointing out the inappropriateness of it all, can be found at Shots in the Dark, in temporal order here, here, here.)
But now it seems the Winklevosses are asking for redress from Drew Faust, so the question of whether I can go around openly insulting students' character without worrying about whether anyone at Harvard will care is, for now, at least somewhat open.
(Further commentary, including some people at Harvard pointing out the inappropriateness of it all, can be found at Shots in the Dark, in temporal order here, here, here.)
Beyond Worst Case Analysis -- Preparing a Talk
A few months ago, Tim Roughgarden mailed me to say was putting together a little workshop on the theme of Beyond Worst Case Analysis, and would I like to be one of the plenary speakers? It sounded like an interesting topic, one I've certainly spoken off the cuff about on this blog from time to time. And I enjoy any reasonably good excuse to get out to the Bay Area. So I agreed.
The workshop announcement is here. As you might imagine, what Tim DID NOT tell me at the time was that the other speakers were Avrim Blum, Bernard Chazelle, Uri Feige, Richard Karp, Dan Spielman, and Shang-Hua Teng. That would have given me pause, to say the least. Now I get to spend the summer thinking about how I'm going to give a talk that could still be deemed interesting in the company of this group of scholars. No pressure, no pressure...
(Tim also failed to mention that he had actually taught a course on this whole subject. Which, I should say, looks like a great course -- I'd love to swipe his notes and teach it myself some time. Again, the bar here is higher than I had expected... let that be a lesson to everyone if Tim comes asking you for something...)
I will hopefully blog more on this topic as I prepare the talk, in order to get ideas and feedback from the community at large. I figure that's one way to improve my talk. Also, now that I've said I'm going to do that, hopefully it will get me working on the talk sooner rather than later. (It's amazing how fast the summer goes by, and you fail to get done all the wonderful things you had planned to do over the summer...)
But even now, you can help me out. What directions or issues do you see in the theme of Beyond Worst Case Analysis, and what would you like to see in a talk on the subject?
(And if you get a chance, come to the workshop!)
The workshop announcement is here. As you might imagine, what Tim DID NOT tell me at the time was that the other speakers were Avrim Blum, Bernard Chazelle, Uri Feige, Richard Karp, Dan Spielman, and Shang-Hua Teng. That would have given me pause, to say the least. Now I get to spend the summer thinking about how I'm going to give a talk that could still be deemed interesting in the company of this group of scholars. No pressure, no pressure...
(Tim also failed to mention that he had actually taught a course on this whole subject. Which, I should say, looks like a great course -- I'd love to swipe his notes and teach it myself some time. Again, the bar here is higher than I had expected... let that be a lesson to everyone if Tim comes asking you for something...)
I will hopefully blog more on this topic as I prepare the talk, in order to get ideas and feedback from the community at large. I figure that's one way to improve my talk. Also, now that I've said I'm going to do that, hopefully it will get me working on the talk sooner rather than later. (It's amazing how fast the summer goes by, and you fail to get done all the wonderful things you had planned to do over the summer...)
But even now, you can help me out. What directions or issues do you see in the theme of Beyond Worst Case Analysis, and what would you like to see in a talk on the subject?
(And if you get a chance, come to the workshop!)
Monday, July 18, 2011
Rabin's 80th Birthday Celebration
Big announcement: We'll be having an 80th birthday conference celebration for Michael Rabin at Harvard at the end of August. Lots of great talks by big-name CS people! (And I'll be there too.) The web site has all the relevant information -- schedule, directions, hotel, etc. KEY POINT: We need you to register in advance. (Otherwise we won't have a head-count for food, etc.) All of us at Harvard hope you'll be able to come. See you there!
Formal announcement below:
On August 29-30, 2011, there will be a conference in celebration of Michael Rabin's 80th birthday at the Harvard School of Engineering and Applied Sciences. The speakers include Yonatan Aumann, Michael Ben-Or, Richard Karp, Dick Lipton, Silvio Micali, Michael Mitzenmacher, David Parkes, Tal Rabin, Ron Rivest, Dana Scott, Madhu Sudan, Salil Vadhan, Moshe Vardi, and Avi Wigderson.
The conference is open to the public, but registration is required by August 25. For more information, see the conference website at https://www.events.harvard.
Formal announcement below:
On August 29-30, 2011, there will be a conference in celebration of Michael Rabin's 80th birthday at the Harvard School of Engineering and Applied Sciences. The speakers include Yonatan Aumann, Michael Ben-Or, Richard Karp, Dick Lipton, Silvio Micali, Michael Mitzenmacher, David Parkes, Tal Rabin, Ron Rivest, Dana Scott, Madhu Sudan, Salil Vadhan, Moshe Vardi, and Avi Wigderson.
The conference is open to the public, but registration is required by August 25. For more information, see the conference website at https://www.events.harvard.
Tuesday, July 12, 2011
SODA in Japan
I hadn't even noticed SODA was in Japan before submitting. I just figured wherever it was I'd be willing to go, as January in Boston is a fine time to be elsewhere. And if needed I can send a student instead...
My only past time in Japan was for ISIT back in 2003. I remember it was a maddeningly long flight (made somewhat bearable by distracting myself with whatever was the new Harry Potter book at the time), followed by a 2 hour long wait to get through customs, followed by a 2 hour train ride to Yokohama. I was not a happy camper when I got to the hotel. Which, once I got there, was absolutely amazing; a bath in the deep Japanese-style tub and some food and the grumpiness passed. And then it was a great conference; hanging out with an old friend and his colleague over breakfast we managed to produce a paper (which eventually ended up being this journal version -- my first and likely only paper that will appear in IEEE Design and Test.) One day we took off and did some great sightseeing, where I depended greatly on the lead of others, not having grokked how to get around with signs in a language I didn't understand at all.
So if I get a paper in I suppose I'll cope with the long flight and go. Of course with 600 or so submissions it's a roll of the dice; we'll see how it goes.
Best of luck to everyone working until the deadline....
My only past time in Japan was for ISIT back in 2003. I remember it was a maddeningly long flight (made somewhat bearable by distracting myself with whatever was the new Harry Potter book at the time), followed by a 2 hour long wait to get through customs, followed by a 2 hour train ride to Yokohama. I was not a happy camper when I got to the hotel. Which, once I got there, was absolutely amazing; a bath in the deep Japanese-style tub and some food and the grumpiness passed. And then it was a great conference; hanging out with an old friend and his colleague over breakfast we managed to produce a paper (which eventually ended up being this journal version -- my first and likely only paper that will appear in IEEE Design and Test.) One day we took off and did some great sightseeing, where I depended greatly on the lead of others, not having grokked how to get around with signs in a language I didn't understand at all.
So if I get a paper in I suppose I'll cope with the long flight and go. Of course with 600 or so submissions it's a roll of the dice; we'll see how it goes.
Best of luck to everyone working until the deadline....
Saturday, July 09, 2011
Using Google Scholar for More Than Your h-Index
The comments from the last post (thanks, David Andersen) spurred me to mention the following.
I do check Google Scholar for my own work fairly regularly. Not to keep continuously updated on my h-index (though, I suppose, that's a side benefit). But I've found it very useful to look at who is citing my work. For older areas of research where I'm (at least temporarily) inactive, it's useful to keep track on what's gone on since I've been paying close attention. For areas where I'm still doing research, it's helpful to know what's out there -- so I can cite it, I can see where the area is going, and I can know who is working in the area. Keeping up to date this way can also suggest new research problems or collaborations. Being able to access the citation graph so easily is, I think, very helpful.
I do the same thing using full-text search for myself on the arXiv, and I even Google myself on the Web. (I've found blog posts mentioning me or this blog that I wouldn't otherwise have known about that way.)
So no, I don't think it's egotistical to check yourself on Google scholar. I think it's just a good research practice to keep tabs on who is citing your work.
I do check Google Scholar for my own work fairly regularly. Not to keep continuously updated on my h-index (though, I suppose, that's a side benefit). But I've found it very useful to look at who is citing my work. For older areas of research where I'm (at least temporarily) inactive, it's useful to keep track on what's gone on since I've been paying close attention. For areas where I'm still doing research, it's helpful to know what's out there -- so I can cite it, I can see where the area is going, and I can know who is working in the area. Keeping up to date this way can also suggest new research problems or collaborations. Being able to access the citation graph so easily is, I think, very helpful.
I do the same thing using full-text search for myself on the arXiv, and I even Google myself on the Web. (I've found blog posts mentioning me or this blog that I wouldn't otherwise have known about that way.)
So no, I don't think it's egotistical to check yourself on Google scholar. I think it's just a good research practice to keep tabs on who is citing your work.
Friday, July 08, 2011
h-index != impact
Suresh and Daniel Lemire (in Google+ posts) have pointed to the following paragraph from this blog:
I'm not being naive. Citation counts certainly arise in promotion and tenure cases. They're a piece of information, and we look at them. But just as your GRE score won't get you into (one of the top-tier) graduate schools, your h-index is not going to get you tenure (or a grant, or an award, or...)
When you come up for promotion, we ask for letters. Some letters will mention your citation counts or your h-index as a way of providing evidence that you've done interesting and important work, and that's all well and good. Then, what we look for, is an explanation from the scientist as to why they think your work is interesting and important. Arguably, the best way to get your letter-writers to write a good case for why your work is interesting and important is to do work that you're excited and want to tell the world about. Because if you are excited and go tell the world, repeatedly and with energy, the word will get out, and get to the ears of those scientists who are going to write your letters.
Of course, even ignoring those employment-relate aspects, doing science you're excited about is just more fun.
I wonder if the author of this blog post is correct in the characterization of young people, as the idea is a bit foreign to me. In theory, of course, we have some great role models; I don't think Les Valiant, Jon Kleinberg, David Karger, Cynthia Dwork, and so on spend their time worrying about their h-index. They just want to do cool stuff (and, as far as I've known them, always have -- it's not a "now-that-they're senior" thing). But just in case, let's make sure the correlation/causation message gets out right:
cool work, excitement, and enthusiasm tends to yield high citation counts and maybe h-indexes
but
citations are not how we define or even measure cool work, excitement, and enthusiasm
The sad thing is that young people have now been terrified by the Impact and H factors, and I can’t give them much hope. When I published my first paper in 1967 (J. Chem. Soc. (now the RSC), Chemical Communications) I did it because I had a piece of science I was excited about and wanted to tell the world about. That ethos has gone. It’s now “I have to publish X first author-papers in Y journals with impact factors great than Z”.As a service to those young people, I'd like to make clear that, at least at my institution, the “I have to publish X first author-papers in Y journals with impact factors great than Z” approach is not actually suitable, and you should focus on the "I had a piece of science I was excited about and wanted to tell the world about" approach.
I'm not being naive. Citation counts certainly arise in promotion and tenure cases. They're a piece of information, and we look at them. But just as your GRE score won't get you into (one of the top-tier) graduate schools, your h-index is not going to get you tenure (or a grant, or an award, or...)
When you come up for promotion, we ask for letters. Some letters will mention your citation counts or your h-index as a way of providing evidence that you've done interesting and important work, and that's all well and good. Then, what we look for, is an explanation from the scientist as to why they think your work is interesting and important. Arguably, the best way to get your letter-writers to write a good case for why your work is interesting and important is to do work that you're excited and want to tell the world about. Because if you are excited and go tell the world, repeatedly and with energy, the word will get out, and get to the ears of those scientists who are going to write your letters.
Of course, even ignoring those employment-relate aspects, doing science you're excited about is just more fun.
I wonder if the author of this blog post is correct in the characterization of young people, as the idea is a bit foreign to me. In theory, of course, we have some great role models; I don't think Les Valiant, Jon Kleinberg, David Karger, Cynthia Dwork, and so on spend their time worrying about their h-index. They just want to do cool stuff (and, as far as I've known them, always have -- it's not a "now-that-they're senior" thing). But just in case, let's make sure the correlation/causation message gets out right:
cool work, excitement, and enthusiasm tends to yield high citation counts and maybe h-indexes
but
citations are not how we define or even measure cool work, excitement, and enthusiasm
Wednesday, July 06, 2011
Various Goings On
I've not been a Facebook user, but I was invited to join Google+, so I set up a picture and am waiting to see what it's all about. I'm afraid that for the most part I'm not so interested in a wall where people tell me what's going on with them, nor do I see the point in writing to groups of people I know to update them on my life this way, but perhaps over time I'll be converted to this way of socializing. Until then, I guess I'll keep writing blog posts if I feel I have something to say (which, admittedly, has been less often these days).
600+ abstracts submitted to SODA. I wonder what the over/under is on how many will actually be papers a week from now. I'm expecting about a 10% drop, but wouldn't even be surprised to see it go down to 500 or so. That suggests about a 25+% acceptance rate. I'm not sure what message there is to take out of that. But given that 500 seems to be the total of accepted papers for SODA, STOC, FOCS, ESA, ICALP, and maybe another conference or two after that (SPAA, PODC?), it seems like theory is (still) producing too many papers, or has too few venues to publish them in. Larger conferences, or perhaps a large clearing-house conference, anyone? (Would SODA be that much different if it accepted, say, 250 papers? Discuss.)
While I think svn is great for collaborations, I've really found the merging functionality has negligible utility. I'm a novice user, but it seems whenever there's a conflict, the fastest way to deal with it is still to pick a winner, diff for differences, and glue together by hand. I think the bottleneck is when there's a conflict, I want to work out differences with my colleague, and the whole point is that we're working at different times and places. So the benefit of working separately seamlessly gets lost.
I still think everyone should be reading Claire's blog, which covers a really nice mix of topics, many of which could potentially lead to interesting community discussions.
600+ abstracts submitted to SODA. I wonder what the over/under is on how many will actually be papers a week from now. I'm expecting about a 10% drop, but wouldn't even be surprised to see it go down to 500 or so. That suggests about a 25+% acceptance rate. I'm not sure what message there is to take out of that. But given that 500 seems to be the total of accepted papers for SODA, STOC, FOCS, ESA, ICALP, and maybe another conference or two after that (SPAA, PODC?), it seems like theory is (still) producing too many papers, or has too few venues to publish them in. Larger conferences, or perhaps a large clearing-house conference, anyone? (Would SODA be that much different if it accepted, say, 250 papers? Discuss.)
While I think svn is great for collaborations, I've really found the merging functionality has negligible utility. I'm a novice user, but it seems whenever there's a conflict, the fastest way to deal with it is still to pick a winner, diff for differences, and glue together by hand. I think the bottleneck is when there's a conflict, I want to work out differences with my colleague, and the whole point is that we're working at different times and places. So the benefit of working separately seamlessly gets lost.
I still think everyone should be reading Claire's blog, which covers a really nice mix of topics, many of which could potentially lead to interesting community discussions.
Friday, July 01, 2011
Odd SODA Rules, and Other Conference Paper Complaints
Suresh points out we have some strange new SODA submission rules this year:
Full submissions should begin with the title of the paper, each author's name, affiliation, and e-mail address, followed by a succinct statement of the problems considered, the main results, an explanation of their significance, and a comparison to past research, all of which should be easily understood by non-specialists. More technical developments follow as appropriate. Use 11-point or larger font in single column format, with one-inch or wider margins all around. The submission, excluding title page and bibliography, must not exceed 10 pages (authors should feel free to send submissions that are significantly shorter than 10 pages.) If 10 pages are insufficient to include a full proof of the results, then a complete full version of the paper (reiterating the material in the 10-page abstract) must be appended to the submission after the bibliography. The length of the appended paper is not limited, and it will be read at the discretion of the committee. A detailed proof in the appended complete version is not a substitute for establishing the main ideas of the validity of the result within the 10-page abstract.
This is totally bizarre. 11-point single column-format? Then an appended paper beyond the abstract?
I wish I was submitting a paper on my own. I'd just submit a standard opening abstract and my "10-page paper" would be, "Hey, I've just told you what I'm going to prove, why don't you go read my real paper, which is attached to this?" Because, really, I'm not clear on what the point of all this is.
Having recently finished an ICALP paper and having worked today on an ESA paper, I didn't think it was possible to choose a worse format that 10 or 12 pages in LNCS format, which gives you just enough space to say, "Here, I've done something interesting, but if you want any details, go read it on the arXiv." And I suppose this isn't really worse. [Really, can't we all just protest the bizarre LNCS format? Or fine, keep the format, but paper limits should be 20 pages.] It's just strange.
Most other conference I'm involved with outside of theory have the sensible approach that you submit something that looks pretty much like what your final paper is supposed to look like. You may only have a 5 page limit (double column, 10 point font, which I think is still well over 12 pages in LNCS format), but the reviewers sees what the paper will be. Some conference even give a page or two extra for the final version, so you can actually address reviewer comments. (Of course, those conferences also make a point of giving detailed reviewer comments, in some cases even having shepherds for the final papers.)
Theory conferences are messed up with this whole page limit/paper format thing. Someone should figure out a simpler, more coherent system. It seems like it would be hard to come up a system that was any more random and arbitrary.
Full submissions should begin with the title of the paper, each author's name, affiliation, and e-mail address, followed by a succinct statement of the problems considered, the main results, an explanation of their significance, and a comparison to past research, all of which should be easily understood by non-specialists. More technical developments follow as appropriate. Use 11-point or larger font in single column format, with one-inch or wider margins all around. The submission, excluding title page and bibliography, must not exceed 10 pages (authors should feel free to send submissions that are significantly shorter than 10 pages.) If 10 pages are insufficient to include a full proof of the results, then a complete full version of the paper (reiterating the material in the 10-page abstract) must be appended to the submission after the bibliography. The length of the appended paper is not limited, and it will be read at the discretion of the committee. A detailed proof in the appended complete version is not a substitute for establishing the main ideas of the validity of the result within the 10-page abstract.
This is totally bizarre. 11-point single column-format? Then an appended paper beyond the abstract?
I wish I was submitting a paper on my own. I'd just submit a standard opening abstract and my "10-page paper" would be, "Hey, I've just told you what I'm going to prove, why don't you go read my real paper, which is attached to this?" Because, really, I'm not clear on what the point of all this is.
Having recently finished an ICALP paper and having worked today on an ESA paper, I didn't think it was possible to choose a worse format that 10 or 12 pages in LNCS format, which gives you just enough space to say, "Here, I've done something interesting, but if you want any details, go read it on the arXiv." And I suppose this isn't really worse. [Really, can't we all just protest the bizarre LNCS format? Or fine, keep the format, but paper limits should be 20 pages.] It's just strange.
Most other conference I'm involved with outside of theory have the sensible approach that you submit something that looks pretty much like what your final paper is supposed to look like. You may only have a 5 page limit (double column, 10 point font, which I think is still well over 12 pages in LNCS format), but the reviewers sees what the paper will be. Some conference even give a page or two extra for the final version, so you can actually address reviewer comments. (Of course, those conferences also make a point of giving detailed reviewer comments, in some cases even having shepherds for the final papers.)
Theory conferences are messed up with this whole page limit/paper format thing. Someone should figure out a simpler, more coherent system. It seems like it would be hard to come up a system that was any more random and arbitrary.
Wednesday, June 29, 2011
UC Budget Woes
The new California budget call for $650 million in cuts to the UC systems -- I understand $500 million had already been planned, they added $150 million on top of that, and may add more later if the revenue numbers don't pan out.
I'll admit that as a long-time CA resident (that's where I grew up), and a UC Berkeley alum (for grad school), it pains me to hear this. I'm very sympathetic to statements such as this one quoted in this San Francisco Chronicle piece:
"Some students don't even call the increases "tuition" anymore, but tax increases. They say state lawmakers are deceptive in claiming to have passed the budget without raising taxes."
I grew up in a California where we really believed we were a shining vanguard for the rest of the nation -- and the UC system was a very big part of that. By the time I left California I, at least, didn't have that feeling about the state any more. And these cuts, of course, are painful to hear.
I don't mean to make it sound like the UCs are dead -- they have too many brilliant faculty to count, and will continue to attract many top students. But it seems to me they are being weakened, perhaps (and I hope not) even crippled longer term. I hope that this is just a historical blip, and California's greatness -- including vibrant, powerful, and more healthy UC and CSU systems -- will be on full display the rest of the century.
Addendum:
Michael Goodrich (who I've had the pleasure of working with lately) has suggested that all this points to (high) double-digit percentage increases in UC tuition coming up. He pointed me to several news bits from the UC news site on the cuts generally and tuition specifically, including this, this, and this, and pointed me to the UC Regents site, where you can find things like the minutes to their meetings.
I'll admit that as a long-time CA resident (that's where I grew up), and a UC Berkeley alum (for grad school), it pains me to hear this. I'm very sympathetic to statements such as this one quoted in this San Francisco Chronicle piece:
"Some students don't even call the increases "tuition" anymore, but tax increases. They say state lawmakers are deceptive in claiming to have passed the budget without raising taxes."
I grew up in a California where we really believed we were a shining vanguard for the rest of the nation -- and the UC system was a very big part of that. By the time I left California I, at least, didn't have that feeling about the state any more. And these cuts, of course, are painful to hear.
I don't mean to make it sound like the UCs are dead -- they have too many brilliant faculty to count, and will continue to attract many top students. But it seems to me they are being weakened, perhaps (and I hope not) even crippled longer term. I hope that this is just a historical blip, and California's greatness -- including vibrant, powerful, and more healthy UC and CSU systems -- will be on full display the rest of the century.
Addendum:
Michael Goodrich (who I've had the pleasure of working with lately) has suggested that all this points to (high) double-digit percentage increases in UC tuition coming up. He pointed me to several news bits from the UC news site on the cuts generally and tuition specifically, including this, this, and this, and pointed me to the UC Regents site, where you can find things like the minutes to their meetings.
Friday, June 24, 2011
Probability Assignments Using Set
I'm gearing up for teaching my graduate course on randomized algorithms and probabilistic analysis next semester. It's been a while since I've taught it, and I'm somewhat uncertain what to do with the course, precisely since I wrote the textbook
. Me lecturing from the textbook is boring, both for me and for them, but of course the textbook contains exactly what I think is important.
Somehow I'll have to have them read the textbook offline and try to do more online learning in class. I'm working through creating some programming exercises based on the game Set. (Amazon picture below.)
Set is a great card came (wikipedia entry, or the Set web site). As it says in Wikipedia, "The deck consists of 81 cards varying in four features: number (one, two, or three); symbol (diamond, squiggle, oval); shading (solid, striped, or open); and color (red, green, or purple)." You turn over 12 cards, and look for a set, which is three cards so that for each feature, EITHER all cards are the same in that feature, or they are different. So below is an example of a set. (different in each feature). If they cards were all green, it would still be a set -- they can be all the same in some features, and all the same in others, and still be a set.
The first player to find a set picks it up, and replacement cards are dealt in to get you back to 12 cards. The player with the most cards at the end of the game wins. My eldest had already seen the game in school, and after a few months, she and I now are pretty competitively matched. I'd put it up there with Mastermind as a good mental exercise game for kids.
So the reason I thought about Set for my class is that the game instructions say that the odds of not getting a set with 12 cards dealt out is 33 to 1. (When this happens, or you can't find one, you can deal another card out; with 15 cards, the claim is more than 2500:1.) But when you play the game, it seems you don't find a set much more often. While my daughters and I are probably missing some sets some of the time, it's also clear that conditional probability is coming into play here. At any point in the game, there aren't 12 random cards on the table. Most clearly, suppose I deal 12 cards, find a set, and replace the 3 cards. What's left isn't 12 random cards; it's 9 cards left after a set was removed, and 3 cards remaining from the deck.**
This seems like a nice way to introduce conditional probability in a concrete but perhaps subtle way. And it seems like there are plenty of other related questions one can ask as well. (What's the probability of not finding a set on the kth turn, given a set has been found in the first k-1 turns...) Feel free to suggest exercises. (Apparently the largest number of cards without a set is 20. I wonder if there's a short proof of that without just doing exhaustive search.)
At the very least, it will be a good excuse to get a couple of boxes of Set for the office.
Have to go. My daughter just asked to play a game of Set...
** Of course I'm not the first to have noticed this. Peter Norvig posted on it as well.
. Me lecturing from the textbook is boring, both for me and for them, but of course the textbook contains exactly what I think is important.Somehow I'll have to have them read the textbook offline and try to do more online learning in class. I'm working through creating some programming exercises based on the game Set. (Amazon picture below.)
Set is a great card came (wikipedia entry, or the Set web site). As it says in Wikipedia, "The deck consists of 81 cards varying in four features: number (one, two, or three); symbol (diamond, squiggle, oval); shading (solid, striped, or open); and color (red, green, or purple)." You turn over 12 cards, and look for a set, which is three cards so that for each feature, EITHER all cards are the same in that feature, or they are different. So below is an example of a set. (different in each feature). If they cards were all green, it would still be a set -- they can be all the same in some features, and all the same in others, and still be a set.
The first player to find a set picks it up, and replacement cards are dealt in to get you back to 12 cards. The player with the most cards at the end of the game wins. My eldest had already seen the game in school, and after a few months, she and I now are pretty competitively matched. I'd put it up there with Mastermind as a good mental exercise game for kids.
So the reason I thought about Set for my class is that the game instructions say that the odds of not getting a set with 12 cards dealt out is 33 to 1. (When this happens, or you can't find one, you can deal another card out; with 15 cards, the claim is more than 2500:1.) But when you play the game, it seems you don't find a set much more often. While my daughters and I are probably missing some sets some of the time, it's also clear that conditional probability is coming into play here. At any point in the game, there aren't 12 random cards on the table. Most clearly, suppose I deal 12 cards, find a set, and replace the 3 cards. What's left isn't 12 random cards; it's 9 cards left after a set was removed, and 3 cards remaining from the deck.**
This seems like a nice way to introduce conditional probability in a concrete but perhaps subtle way. And it seems like there are plenty of other related questions one can ask as well. (What's the probability of not finding a set on the kth turn, given a set has been found in the first k-1 turns...) Feel free to suggest exercises. (Apparently the largest number of cards without a set is 20. I wonder if there's a short proof of that without just doing exhaustive search.)
At the very least, it will be a good excuse to get a couple of boxes of Set for the office.
Have to go. My daughter just asked to play a game of Set...
** Of course I'm not the first to have noticed this. Peter Norvig posted on it as well.
Sunday, June 19, 2011
New Books Worth Looking At
New books are coming out all the time, but here are two big ones that stick out in my mind (perhaps because I've seen the authors recently). [Feel free to mention others worth noting in the comments.]
Recently available (I saw copies at FCRC) is The Design of Approximation Algorithms (Amazon link)
by Williamson and Shmoys. Here's a link to the book page. (All books have web pages now, don't you know.) An up-to-the-moment books on approximation algorithms by two well-known experts.
Coming soon is The Nature of Computation (Amazon link)
by Cristopher Moore and Stephen Mertens. Here's a link to the book page. About 1000 pages of introduction to computer science (with some statistical physics, and maybe some other physics, mixed in), with lots of problems. I've seen a preview of the text and it looks like an interesting read. (I'm curious if people will use it for courses -- if you have or are considering it, let me know.)
Recently available (I saw copies at FCRC) is The Design of Approximation Algorithms (Amazon link)
by Williamson and Shmoys. Here's a link to the book page. (All books have web pages now, don't you know.) An up-to-the-moment books on approximation algorithms by two well-known experts. Coming soon is The Nature of Computation (Amazon link)
by Cristopher Moore and Stephen Mertens. Here's a link to the book page. About 1000 pages of introduction to computer science (with some statistical physics, and maybe some other physics, mixed in), with lots of problems. I've seen a preview of the text and it looks like an interesting read. (I'm curious if people will use it for courses -- if you have or are considering it, let me know.) Friday, June 17, 2011
NSF Changing Broader Impacts
The NSF is changing its description of its merit criteria -- specifically, what the Broader Impacts criteria will be. The details are still being worked out, and comments are being collected until July 14. More information can be found on this NSF page.
The current draft text states:
Collectively, NSF projects should help to advance a broad set of important national goals, including:
It does seem, though, that this list isn't particularly theory-friendly. Cryptographers can point to national security; my algorithmic work can certainly point to academia-industry partnerships and economic competitiveness. But more complexity-related proposals, or algorithmic proposals with less clear immediate practical applications -- where do they fit in? Should it be a national goal to support more theoretical research with long-term and unclear payoffs? (I think so, particularly as that sort of research is generally relatively very cheap and has potential for huge benefits.) How would you place such research in the above Broader Impact context, or should a new bullet be added? What else would you add?
The current draft text states:
Collectively, NSF projects should help to advance a broad set of important national goals, including:
- Increased economic competitiveness of the United States.
- Development of a globally competitive STEM workforce.
- Increased participation of women, persons with disabilities, and underrepresented minorities in STEM.
- Increased partnerships between academia and industry.
- Improved pre-K–12 STEM education and teacher development.
- Improved undergraduate STEM education.
- Increased public scientific literacy and public engagement with science and technology.
- Increased national security.
- Enhanced infrastructure for research and education, including facilities, instrumentation, networks and partnerships.
It does seem, though, that this list isn't particularly theory-friendly. Cryptographers can point to national security; my algorithmic work can certainly point to academia-industry partnerships and economic competitiveness. But more complexity-related proposals, or algorithmic proposals with less clear immediate practical applications -- where do they fit in? Should it be a national goal to support more theoretical research with long-term and unclear payoffs? (I think so, particularly as that sort of research is generally relatively very cheap and has potential for huge benefits.) How would you place such research in the above Broader Impact context, or should a new bullet be added? What else would you add?
Thursday, June 16, 2011
Dr. Georgios Zervas
Congratulations to Georgios (alternatively, Giorgos), who defended his thesis today.* (There's still some paperwork to get in, but we drank the champagne afterward, so I'm calling it official.) He gave a great presentation covering some of our old work (on analyzing Swoopo, and efficient keyword value computation) plus some of our work-to-be on studying Groupon. (We've put an appetizer up on arxiv; now that this defense is done, we can finish preparing the main course this summer.) I hope to have the chance to swipe the slides and his jokes and give the talk myself sometime; however, if you'd like an interesting talk on data-driven e-commerce analysis, you should of course just invite him to present it instead.
Three cheers for Dr. Georgios Zervas.
*Giorgos is co-advised by me and John Byers.
Three cheers for Dr. Georgios Zervas.
*Giorgos is co-advised by me and John Byers.
Monday, June 13, 2011
NY Times on Computing
A couple of days ago there was a NY Times article on computing being cool (again), including a shout-out to Harvard's own CS 50 and of course the Social Network.
Matt Welsh has a take on it, but please also look for my comment (#7) if you read it. The issue seems worthy of further discussion -- yes, learning how to make something useful quickly is a really exciting aspect of computer science, but it's not what defines computer science as a field -- which may be taken up here later (or in comments at Matt's blog).
Matt Welsh has a take on it, but please also look for my comment (#7) if you read it. The issue seems worthy of further discussion -- yes, learning how to make something useful quickly is a really exciting aspect of computer science, but it's not what defines computer science as a field -- which may be taken up here later (or in comments at Matt's blog).
Sunday, June 12, 2011
2012 PCs
In an effort to return to normalcy, I find myself agreeing to serve on PCs again this year.
NSDI 2012 call for papers is up. Dina Katabi and Steve Gribble went with the old "The PC meeting will be in Boston" ploy -- very clever, made it hard to say no. They also politely asked that I avoid referring to them as stupid or misguided, and I'm expecting that to be an easy requirement to fulfill. Please send interesting papers, so I have something entertaining to read.
I will, finally, be on an ISIT PC, for ISIT 2012. No information up yet that I know of. But it will be held in Cambridge, MA, a little over a year from now. So it rates to be a HUGE conference. (ISIT is normally in the 700-800+ range, as I recall, so I wouldn't be surprised to see it hit 1000+ here.)
For balance, it might be nice to serve on a (CS) theory PC later in the year. (I was recently asked by one, but the timeline overlapped directly with ISIT, so I declined.) Or not -- I'm sure I'll have papers to push around here at Harvard.
NSDI 2012 call for papers is up. Dina Katabi and Steve Gribble went with the old "The PC meeting will be in Boston" ploy -- very clever, made it hard to say no. They also politely asked that I avoid referring to them as stupid or misguided, and I'm expecting that to be an easy requirement to fulfill. Please send interesting papers, so I have something entertaining to read.
I will, finally, be on an ISIT PC, for ISIT 2012. No information up yet that I know of. But it will be held in Cambridge, MA, a little over a year from now. So it rates to be a HUGE conference. (ISIT is normally in the 700-800+ range, as I recall, so I wouldn't be surprised to see it hit 1000+ here.)
For balance, it might be nice to serve on a (CS) theory PC later in the year. (I was recently asked by one, but the timeline overlapped directly with ISIT, so I declined.) Or not -- I'm sure I'll have papers to push around here at Harvard.
Wednesday, June 08, 2011
ITCS
I was asked to post the call for papers for the (renamed) Innovations in Theoretical Computer Science conference. (I'm glad they finally changed the name -- see previous posts here and here.)
This year the conference is moving out of China, where it was well-funded and the logistics were taken care of, to the US. I think this will be a defining year for the conference, as it tries to set out what it should be. The question I continue to have is how it should distinguish itself from and/or relate to FOCS/STOC/SODA. There seems to be a significant bloc in the theory community that is against making these well-established conferences any bigger; to me, this says that we don't need yet-another-conference with the same type of papers unless it's different somehow. So submit and help decide what the identity of ITCS will be.
This year the conference is moving out of China, where it was well-funded and the logistics were taken care of, to the US. I think this will be a defining year for the conference, as it tries to set out what it should be. The question I continue to have is how it should distinguish itself from and/or relate to FOCS/STOC/SODA. There seems to be a significant bloc in the theory community that is against making these well-established conferences any bigger; to me, this says that we don't need yet-another-conference with the same type of papers unless it's different somehow. So submit and help decide what the identity of ITCS will be.
Tuesday, June 07, 2011
FCRC Continued
I've been enjoying FCRC; of course, I like large conferences where lots of people show, as long as they're run well. Rooms have been pretty full at the talks, and lots of people around to talk to. I still don't understand why people object to the idea of making FOCS/STOC larger (and instead seem to prefer to create new conferences and workshops), but if that's the way the theory community wants it, I'd argue that more conference co-location is a good way to go.
I thought Les Valiant gave an excellent Turing lecture -- I'm sure it will be online soon. He provided a clear scientific challenge -- understanding how evolution could have accomplished so much in so little time (just several billion years) -- and made the case the computational complexity (and in particular learning theory) would be a necessary tool in developing an understanding to this problem. I thought especially he did an excellent job gearing the talk to a general computer science audience, limiting the technical discussion and giving a broad overview of the importance of complexity theory, particularly as it might apply in this setting.
Naturally, my favorite session so far has been the "randomized algorithms" session (1A) for STOC, including The Power of Simple Tabulation Hashing (Patrascu/Thorup), Tight Bounds for Randomized Load Balancing (Lenzen/Wattenhofer), and Social Networks Spread Rumors in Sublogarithmic Time (Doerr/Fouz/Friedrich). The first paper shows that tabulation hashing, while only being 3-wise independent, can provide strong theoretical bounds (and excellent practical performance) for most of the natural application of hashing. The second paper looks at parallel load balancing strategies, and shows that many of the lower bounds proven years ago can be beaten by loosening assumptions that led to the lower bounds in quite natural ways. The third paper considered randomized rumor spreading in social network graphs, including the surprising result that taking care not to (randomly) send a message to the same neighbor in consecutive rounds changes the asymptotic behavior (to just barely sublogarithmic) in this setting. All three of the talks were well-presented, making getting up for an 8:30 session worthwhile.
I'd have to say that the STOC poster session -- done for the first time -- seemed to be a successful experiment. There were plenty of people around talking to the poster presenters, so much so that that it didn't seem to wrap up until more like 11 instead of the scheduled 10:30. Hopefully students who presented will comment on how they liked the experience -- either on this blog, or, more directly, with e-mail to the organizers -- and let them know if they found it valuable. I think getting students to present their work in this way will encourage and benefit them greatly and thereby strengthen the field.
I thought Les Valiant gave an excellent Turing lecture -- I'm sure it will be online soon. He provided a clear scientific challenge -- understanding how evolution could have accomplished so much in so little time (just several billion years) -- and made the case the computational complexity (and in particular learning theory) would be a necessary tool in developing an understanding to this problem. I thought especially he did an excellent job gearing the talk to a general computer science audience, limiting the technical discussion and giving a broad overview of the importance of complexity theory, particularly as it might apply in this setting.
Naturally, my favorite session so far has been the "randomized algorithms" session (1A) for STOC, including The Power of Simple Tabulation Hashing (Patrascu/Thorup), Tight Bounds for Randomized Load Balancing (Lenzen/Wattenhofer), and Social Networks Spread Rumors in Sublogarithmic Time (Doerr/Fouz/Friedrich). The first paper shows that tabulation hashing, while only being 3-wise independent, can provide strong theoretical bounds (and excellent practical performance) for most of the natural application of hashing. The second paper looks at parallel load balancing strategies, and shows that many of the lower bounds proven years ago can be beaten by loosening assumptions that led to the lower bounds in quite natural ways. The third paper considered randomized rumor spreading in social network graphs, including the surprising result that taking care not to (randomly) send a message to the same neighbor in consecutive rounds changes the asymptotic behavior (to just barely sublogarithmic) in this setting. All three of the talks were well-presented, making getting up for an 8:30 session worthwhile.
I'd have to say that the STOC poster session -- done for the first time -- seemed to be a successful experiment. There were plenty of people around talking to the poster presenters, so much so that that it didn't seem to wrap up until more like 11 instead of the scheduled 10:30. Hopefully students who presented will comment on how they liked the experience -- either on this blog, or, more directly, with e-mail to the organizers -- and let them know if they found it valuable. I think getting students to present their work in this way will encourage and benefit them greatly and thereby strengthen the field.
Monday, June 06, 2011
Harvard CS Hires (2011 Edition)
At FCRC, I'm getting asked a lot about hiring. Our hiring season still isn't quite yet finished, but I'm going to go ahead and announce three new faculty who will be joining Harvard. (At least, that's what they've told me!)
On the theory side, Jelani Nelson will be joining us, though in a delayed fashion, as he'll be postdoc-ing first. I know this was reported in a comment on Lance's blog some time ago (before he formally accepted our offer, in fact), so I'm glad to be able to confirm it's correct.
Ryan Adams, who works in machine learning and computational statistics, will also be joining us, and we're thrilled to have hired someone in this increasingly key (and highly competitive) area. Ryan was a student of David MacKay, for whom I've previously expressed worship (most recently here).
On the systems side, Eddie Kohler, well known for his work on the Click router as well as many other systems projects, will be joining us. Non-systems people may know him as the writer of HotCRP, the best conference management software available today. (Yes, I've said it!)
More seriously, we're very excited that all three of these outstanding researchers will be coming to Harvard, allowing us to broaden the department's scope and capabilities significantly. While I'd like to take all the credit (and am totally fine with anyone who wants to give it to me), the real credit goes to David Parkes, who led the search committee this year, and of course all the rest of the highly overworked search committee members.
On the theory side, Jelani Nelson will be joining us, though in a delayed fashion, as he'll be postdoc-ing first. I know this was reported in a comment on Lance's blog some time ago (before he formally accepted our offer, in fact), so I'm glad to be able to confirm it's correct.
Ryan Adams, who works in machine learning and computational statistics, will also be joining us, and we're thrilled to have hired someone in this increasingly key (and highly competitive) area. Ryan was a student of David MacKay, for whom I've previously expressed worship (most recently here).
On the systems side, Eddie Kohler, well known for his work on the Click router as well as many other systems projects, will be joining us. Non-systems people may know him as the writer of HotCRP, the best conference management software available today. (Yes, I've said it!)
More seriously, we're very excited that all three of these outstanding researchers will be coming to Harvard, allowing us to broaden the department's scope and capabilities significantly. While I'd like to take all the credit (and am totally fine with anyone who wants to give it to me), the real credit goes to David Parkes, who led the search committee this year, and of course all the rest of the highly overworked search committee members.
Subscribe to:
Posts (Atom)