Computer Science AP Test

Harry Lewis went to a meeting about the future of the Computer Science AP Test. He wrote a short report for our faculty, and gave permission for me to put it on the blog. There are a few Harvard localisms in the report, but I think the information is important for everyone to see.

Guest post by Harry Lewis:

Over the weekend I attended a meeting in Chicago about the future of the AP Computer Science test, along with about 70 other faculty and a few high school teachers.

The College Board announced last year that it was dropping the CS AB test after the spring 2009 administration (the more advanced version, with more on data structures and algorithms) for business reasons (only 4000 test takers). The A test isn't that popular either -- 18,000 I think. By way of comparison, 180,000 take Math, 80,000 take Physics B, and 75,000 take the Statistics exam, if I wrote down the numbers accurately.

The CS AB test is the only one for which Harvard gives credit for advanced standing purposes (and then only if you get a 5). I don't think it would be wise for a student who has taken only the CS A course to skip CS50. So as far as I can see, Harvard won't be offering credit for AP CS after this year.

The numbers of students studying AP CS are pretty bad. Only 12% of American high schools even offer a CS AP course (even the A).

There were rumors that some effort going on to line up industrial support to keep the exam alive. (The Italian-American community got their act together when the College Board cancelled the AP Italian exam, and managed to keep it going by pledging to pay the College Board, even though even fewer take it than the CS AB test.)

The economics of this are interesting. Most of the costs of administering the exams are in grading the free response (non-multiple-choice) questions. But a psychometrician gave an interesting presentation -- it seems that the FR questions contribute nothing to the validity or reliability of the test scores that was not already there in the answers to the multiple choice questions. (Which is not to say that teacher and student behavior might not change if they knew the exam were nothing but multiple choice questions. And the psychometrician cautioned that he hadn't calculated the nontrivial and perhaps different costs of developing the MC and FR questions themselves.) On the other hand, the College Board is probably basing its cancellation judgment on trend lines. CS seems not to be growing in high schools, AP or not. (Whereas Chinese and Japanese, also currently small tests, are.) (The College Board made the decision to drop the AB test and has no plan to reconsider it. It announced its decision without any consultation with the faculty groups involved in developing the exam, by the way.)

A great many people at this meeting don't like the A test, and after taking and grading a few questions, I can see why. It's a Java programming exam. Graders are trained not to take off for trivial syntax errors (confusing commas and semicolons in written answers). They do an incredibly good job developing grading rubrics and keeping the grading consistent between graders. But there are more questions about OO programming concepts than anything else, which doesn't seem right (on the exam we looked at, there were 18 questions on inheritances and whatnot, and 2 on "logic"). Several people said, "if you wonder why kids are turned off on CS in high schools, just look at the questions on the AP exam to see what image of the field is projected." Some proposed, half-seriously, that we ask the College Board to rename the existing course and exam "AP Computer Programming" (no dice, it has to be the name of an academic department in colleges and universities).

There is a movement afoot not to tweak the A exam, but to develop an entirely different kind of intro course to be the basis of the CS AP, something broader, emphasizing both the principles and the importance of the field. A couple of prior working groups drafted proposals. They are right on target IMHO, though maybe better goals for what our majors would understand at the end of 4 years than at the end of the first course. We spent Sunday discussing these. (The College Board is emphatic that there will be only one exam in CS, so this would substitute for the A exam, and we are not discussing a substitute for the AB exam in addition to keeping the A exam.)

These 2 proposals have no operational content at this point. The discussions we had were not premised on there being any programming, or on what programming language might be used (though there certainly seems to be a consensus that the first programming course should use a light-syntax language). And the discussants yesterday were divided on that question. So we are still in early stage development.

We didn't even talk about testing. The two boundary conditions are that the course has to be testable (though not necessarily multiple-choice testable), and has to draw people into the field (the NSF was represented by Jan Cuny, who was evangelical on the subject of drawing more people into the field, especially groups now underrepresented in the field, and has curricular development money to put where her mouth is). Obviously the easiest things to test are programming and math, so this is a nontrivial feasibility issue.

A critical question was whether colleges would give the imagined new AP course credit. I found that hard to answer. With no programming, or very little, it certainly couldn't place people into CS 51 or 61. It seems to be in the CS 1-QR48 space (though maybe not, if there is significant programming after all). Harvard doesn't give Advanced Standing credit for courses that no department would count toward their major, and you can't place out of your Gen Ed requirements on the basis of high school work anyway. In the end I decided there were too many ill-defined variables for me to claim that Harvard would give credit for this course, though I think it has huge potential.

This would take a minimum of 5 years to mature into textbooks, teacher training protocols, etc. Probably more.

There is, by the way, some worry that the College Board's decision will (a) lead to a general dumbing-down of high school CS, marginal as it now is, and (b) deprive us of a small but important part of the flow of new majors (though the number of students taking the AB test nationally is tiny, 40% of them become CS majors, and I'll bet a significant number of our CS majors are in that number).

It will be interesting to see how this develops and there will be opportunities to be involved in the development.

Harry

Harry Lewis Tapes an Ad for Darcy Burner

Without trying to be overtly political, I thought I'd mention some "public service" performed by Harry Lewis. Apparently, Darcy Burner, a Harvard alum running for Congress, said in a debate, "I loved economics so much that I got a degree in it from Harvard." The Republican opponents are questioning her truthfulness, since her actual degree is in computer science. Back in the day (as I well know, as the requirements were the same as when I was an undergrad) for the computer science major you were supposed to take several classes in a related field of your choice. Mine was math. Economics was a popular choice, and was apparently Darcy's. This is (by Harvard policy) not noted on the transcript. There is no sign that she has ever attempted to mislead people about her degree; her resume says she has a computer science degree with a specialization in economics, which would be a completely accurate description in my opinion. You can search online for more info.

Harry Lewis publicly backed Darcy Burner's statement, and in fact is now featured in an ad explaining Darcy's academic qualifications. You can read the Crimson article here, and see Harry set the record straight here at Youtube, or here, and probably many other places. Thank you, Harry! No matter what party you favor, certainly everyone is entitled to the facts without the spin, and that is what Harry has provided.

Harry is naturally polite and reserved in his statements, but I'll be more clearly biased: any district should be thrilled to have a Congressperson with a computer science degree, and especially one with a degree from Harvard!

On the Ad Board (A Harvard-centric Post)

The Harvard Crimson had an editorial earlier this week on the Ad Board, the administrative board that implements the rules of the college for undergraduates, and which I served on for a year-and-a-half, ending last June. (I happen to read the Crimson semi-regularly as copies are left in the lounge areas of our building.)

The piece was just so over-the-top negative, and blatantly factually wrong (it's hard to find a stated fact in the text that is actually correct), that it makes this season's political ads look good by comparison. So I took it upon myself to respond.

I suppose only my Harvard readers might care about this, but here's the editorial, and the text of my response is below. We'll see next week if the Crimson publishes it.

UPDATE: The Crimson did print my letter here. (It changed a few things, making it shorter and a bit more generic, but the spirit is there.) Also, since it seems from the comments that many people are simply uninformed, let me point to the Student Guide for the Ad Board; I'd encourage people with questions (or complaints) to read that first, as it gives a lot of detail about how the Ad Board works.

--------------

Bad Board, No; Bad Editorial, Yes

To the Crimson editorial staff:

Having finished a year-and-a-half of service as a faculty member of the Ad Board last June, I was shocked by the opinion “Bad Board” that appeared in the Crimson on October 22. First, it was simply riddled with factual errors. For example, contrary to your statement that resident deans are “outranked” by the faculty, in fact there are only two or three faculty members on the Ad Board at any time, and over a dozen resident deans; we all get equal votes. Even if we didn’t take the resident deans seriously as you suggest (and we do), they could simply outvote us. As another example, contrary to your statement, in disciplinary cases students are always allowed to present their side of the story, both in written form and by attending an Ad Board meeting, where students can make a statement and, if they choose, respond to questions. I could go on, but there are so many additional factual errors that it would take a letter much longer than the original editorial to go through them all.

Second, your editorial fundamentally misunderstands the Ad Board’s setup and purpose. You complain that students cannot hire an attorney for an Ad Board hearing. That is because the Ad Board is not a legal institution, like a court or the police, but an academic institution, to administrate the rules of the college. The Ad Board’s purpose is fundamentally education, not punishment. As you quote, the Ad Board is “primarily concerned for the educational and personal growth of undergraduates, both as individuals and as members of the Harvard community.” Sometimes, when a rule is broken, a punishment must be given, but we view that as a learning process for the student. Attorneys should not be a part of that learning process, much in the same way you can’t hire a lawyer to complain about or negotiate for a better grade in my class. (Please don’t try.)

Finally, your article includes what I would call errors not of fact but of spirit. You say “rulings are clear before it [the Ad Board] convenes”. That’s a surprise to me, as I regularly spent multiple hours in these meetings each week listening to and deliberating cases. Punishments are not, as you say, “one-size-fits-all”; we discuss the appropriate response for each case, based on the rules of the Faculty and the needs of the individual student. We take seriously both these rules and these needs, with the goal of best serving both the students that come before us and the larger Harvard community.

I understand that, as you say, going before the Ad Board is intimidating and terrifying for a student. They are generally there because there is an accusation that they have broken a rule of the College, and there may be consequences. I know of no system we could possibly set up where that wouldn’t be intimidating and terrifying. But students should know going in that the Ad Board will listen to them, fairly, and that no punishment is given lightly.

Michael Mitzenmacher '91

Professor of Computer Science

Harvard School of Engineering and Applied Sciences

PC Members Submitting Papers

I'm currently going through papers for NSDI, and the PC chairs had to send out a post saying how the papers where they are co-authors would be specially handled. NSDI not only allows PC members to submit papers, but the chairs as well!

In the theory community, we generally don't do this. PC members can't submit papers, apparently to avoid any conflict of interest. This is, from what I've seen, unusual, even for CS, which is already unusual in the competitiveness and importance of conferences. Most networking conferences, for instance, allow PC members to submit.

Does conflict of interest really exist in these situations? I don't think so; generally, from what I've seen, it gets handled, and handled appropriately. People on the PC realize it's a competitive process, and understand when their papers aren't accepted. Often when PC members can contribute papers the process is double-blind, so nobody "knows" the PC-authored papers. While I understand allowing PC-authored papers is a risk, I don't think it's much of one. As a comparison point, theory conferences almost never use double-blind reviewing, and I think just the name of a "prestige author" on the paper has a significant effect on the odds of acceptance.

What's the upside? The biggest is that it makes it easier to have larger PCs. I have 20 papers to read for NSDI. I can't remember the last time I had less than 40 papers to review as a PC member for a significant theory conference.

Less Busy October

After a few days of trial, the two sides in the case I'm acting as an expert witness on agreed to settle, before any of the experts reached the witness stand. So all of a sudden I'm less busy than I had expected. Maybe I'll have time to whittle down that never-empty to-do list. Or blog. Or maybe a new case will serendipitously come along.

Undoubtedly the people happiest with the settlement are the jury. They were going to have to sit through several weeks of trial, and while I'm sure they were all eager and thrilled to fulfill their civic duty, I'm sure they all have their own to-do lists to deal with.

Busy October (and November, and...)

I'm expecting a "blog slowdown" over the next few weeks, as life is busy.

I'm on the NSDI program committee, and we recently got our review assignments. There's an unfortunate overlap between this reviewing cycle and the STOC deadline/paper assignments but I'm hoping that won't be too problematic. (I got asked to be on NSDI before being asked to do STOC. And Jennifer Rexford asked, and as I'm a fan of Jennifer Rexford's work, it pushed me to say yes.) In other PC news, I was asked to be on the SIGCOMM 2009 committee, and again, just couldn't find a way to say no. I'll be finding it easier to turn down PCs the rest of the year...

A case I'm serving as an expert witness on is now in trial. That will take up significant time over the next few weeks. On the positive side, the trial is here in Boston, so I'm not traveling somewhere for it.

I'm scheduled to be at an IPAM workshop in a few weeks, and still have to prepare the talk.

Those NSF deadlines are looming large.

A few papers are in various stages in the journal process (either getting ready for submission, or revising based on reviewer comments). I'd like to get those off the stack.

Overall, it's all good and fun. Well, maybe not the NSF proposal(s), those are always hard to describe as fun. But it is busy. So I think blog posting will be more sporadic than usual.

Guest posters are always welcome....

STOC 2009, Web site + prereg of papers

The STOC 2009 submission page is now up, here. [ https://secure.iacr.org/websubrev/stoc2009/submit/].

While papers are due November 17, you must submit an abstract by November 10. Please pass the word.

For those of you with an interest in such things, we're using Shai Halevi's conference software. I was going to go with easychair, but the one major complaint (that I'm very sympathetic to) was that they didn't allow as a default the use of scorecards for offline reviewing. (They said they could do something for us, but we'd have to pay for it.) Shai also very generously offered to help me out with everything, so we all owe him thanks. (But especially me.)

If you notice anything not working right with the site, please let me know right away.

Protecting Privacy

Just a note that the National Academies Press has released its report (well, at 376 pages, it's really a book) Protecting Individual Privacy in the Struggle Against Terrorists: A Framework for Program Assessment, which is free to read online. You may have seen a news article on it somewhere or another. It's theory-relevant since Cynthia Dwork was on the committee that wrote it -- I'm guessing she played a very significant role in Appendix H: Data Mining and Information Fusion and/or Appendix L: The Science and Technology of Privacy Protection in particular. It's now on my to-read stack.

Blindness

I went to a talk which was about a type of industrial software. At some point the speaker puts up a list about what typical corporate-research/programmer staff in this area do all day. The list was clearly meant to be a little humorous (inasmuch as people discussing such things can be). The last bullet was:

Find time to find a girlfriend.

Now, I'm not claiming to be most sensitive Neanderthal in the cave, but I am the father of three daughters, and this raised my hackles. The small number of women in the audience didn't seem to notice or mind, but maybe they did, or maybe one would the next time he gave the talk. As a field, this is exactly the type of throwaway comment that we have to, repeat, have to avoid.

I mentioned it to the speaker afterward, and to his credit, he was not defensive, and said he'd remove it or change "girlfriend" to the gender-neutral "significant other". (I'd vote for removal. Why even go with the stereotype computer scientists can't find love?)

Latest PhD Comics

I occasionally read PhD comics. This last one explains why our enrollments will be going up again; the one previous just made me laugh. (Excuse me now, I have to go sit back and enjoy as the rest of the world crumbles.)

The Stupidest NSF Review I've Had, Ever

It's come out before on this blog that I have a love/hate relationship with the NSF. I love that they give out money for research -- especially for mine! However, I am not always the biggest fan of their structure, processes, priorities, etc. (And I surely acknowledge that some of this is not "their" fault -- as a government agency, they've got government rules to follow.)

Still, the last reviews for a grant we didn't get contained just the stupidest comment, I really have to share it, because it just frightens me. I'm used to reviews I don't agree with -- the typical excuse not to fund a theory grant being, "The proposal doesn't explain how it will solve the proposed problems," while if I already knew how to solve the proposed problem, I'd have written the paper already -- but again, this goes beyond that. If this was just an excuse to not fund the proposal -- because the NSF for some reason never says "We only have money for the top 10% this year, and I'm afraid there are some better proposals," but instead has to have a reason -- that's fine, but I hope it's not a real reason.

This was a CDI proposal (so apologies to my co-authors, who do not necessarily share my opinions). The primary theme was mechanism design, but we focused on network formation and ad auctions as examples. One reviewer wrote:

[ad placement] is a very active research area for corporate research labs at places such as Yahoo and Google. Given the vast resources that are being invested at these corporate labs (that have hired top economists and computer scientists) and that have direct access to logs documenting advertiser and user behavior, it is unclear how much of a contribution an academic team can make here.

One review might be forgivable. The panel summary listed the following as a weakness:

- There were also questions regarding how this will
compete with much larger-scale multidisciplinary
efforts (CS-economics) of similar kind in
industry (Google, Yahoo!, MS, etc.).

Let's ignore that the PIs all have relationships with industry, that ad auctions was just an example (of pretty wide interest right now), and that (I had thought) working on problems of interest to industry is, generally, a good thing.

With this kind of thinking, there's no way a couple of graduate students from Stanford (or, more academically, a future well-known Cornell professor) should have been working on a silly thing like "search engine algorithms", since Altavista was already out there leading the way. (That's my #1 big example, fill in your own.)

Is "industry will do it better than you could" really a good reason not to pursue (or fund) a research topic? How many research areas would that really preclude? I'd assume we should also stop funding research in operating systems, compilers, and even computer security based on that comment, but oddly, I don't see a rush to cancel programs in those areas. Seriously, anonymous reviewer, if you actually meant that, congratulations, you've truly scared me about the future of NSF-sponsored research.

As an addendum, some comments from Harvard colleagues:

1. Where does the reviewer think the people who are going to go work for Google/Yahoo/Microsoft will be coming from?
2. This was the kind of thinking that led Harvard (a CS powerhouse post-WW II) to decide to drop computer science decades ago. IBM was doing it, no need to have a department doing research in the area. It took a while to recover from that decision....
3. That kind of comment is common for chip/architecture research. "Isn't Intel doing that already? How can you possibly contribute?" [I have increased empathy for architecture people.]

Conference heads-ups

Following the trend, a reminder that the FOCS 2008 hotel/pre-registration deadline is October 3.

On the STOC 2009 side, some announcements:
1) Submission date is Nov 17, BUT abstracts will be due Nov 10 -- following the same sort of procedure used for SODA. Spread the word, more info on the Web site shortly.
2) Accept/reject decisions should be out February 6, in response to those who have asked me. (It seems like every other conference in the rough vicinity will have paper deadlines the following week!)
3) The day before the conference is shaping up to be an event, about which I'll hopefully have more news for shortly.
4) It's looking like EasyChair will be the submission/review system. The risks of self-hosting just seems too severe at this point...

Enrollments Up

The last two years, we've seen a huge increase in enrollments in our introductory computer science course. Last year it was about double the size it was the previous year; this year, it looks like it's gone up another 50%. Yes, the intro course has about tripled in the last two years.

Part of that might be that we have a new instructor, who is apparently young, dynamic, bringing a more modern perspective, and all those things that inspire students to take introductory courses. Another explanation is that Harvard last year introduced minors (called secondary fields), so now by taking 4 classes you can get a minor in computer science. A more timely explanation is that the financial meltdown is encouraging students to look at computer science and applied math this year (instead of the more commonly popular major of economics).

The gain is starting to translate into other courses. The intro theory course (automata/complexity) is up over 50% from last year.

Needless to say we're excited by this change, although still processing what it means and how to deal with it longer term. Obviously, we're hoping this will help us make the case for more hires...

Allerton : Moves on Deletions and Insertions

To wrap up, the other paper I presented at Allerton (pdf, talk slides), joint with Adam Kirsch, continues our work in analyzing the power of moving objects around in multi-level hash tables. The gold standard here, at least in theory, is cuckoo hashing, which achieves very high loads but can require a large number of moves when inserting an item. That might not be practical for many applications (especially in network router hardware). In previous work, we had considered the gains obtainable from moving at most 1 item on an insertion. In this work, we add the power to move items on a deletion as well. (Lookups we keep fast and don't do any extra work.)
[The discussion below is, admittedly, probably more for those at least familiar with our previous work...]

Moving an item after another item is deleted is difficult -- generally, you'd want to move some other item deeper in your Multi-Level Hash table into the now empty space higher up in your hash table, but how can you find what item to move? Actually, we'd had ideas on how to do this back when we were working on the insertion paper. But we didn't include it then, for several reasons. First, our ideas required additional space (as explained below). Second, we couldn't analyze them, and one of the points we were aiming for in that paper was to analyze schemes. Third, we didn't have space -- not in the hardware, but in the actual paper. Blame page limits (yes, even for the journal version).

Another recent INFOCOM paper that offered an idea of how to handle moves on deletions inspired me to have us write down our approach -- because I feel our approach is clearly better than that proposed by this other INFOCOM paper, as we discuss in our paper. Even if we can't prove what we'd like, we can still show it works well through simulation.

Our (obvious) idea is just to keep a hint at each hash table cell, if there was a collision there, of where the collided item was placed, so you can find it later on a delete. Hints take space, but not too much. If multiple collisions occur, you have to choose which possible hint to keep; we found most recent collision worked best. Moves on deletes work reasonably well, but the real gains naturally occur from combining moves on insertions and deletes. This gives pretty good performance -- you can get space utilizations more in line with (though of course still not as good as) cuckoo hashing, albeit with more hash functions -- but again, using just 1 move per insert/delete. More details in the paper.

Allerton : The Day Here

I like the Allerton conference.

Part of it is I come most every year. So by now, I know my way around, which is a nice aspect of a conference being held at the same place every year. Got the early flight in, rented my car in about five minutes at the tiny but functional Willard airport in Urbana-Champaign, and had my badge about a half hour later. After a talk and catching up with some people I went to lunch at the Brown Bag, the crowded spot for people who don't like the conference lunch. Back to listen to more talks, and give my talks. After talks, more catching up with people, while they set up the open bar and snacks. (JeffE, forget beer at the business meetings, take a day -- or just an afternoon -- off and join us!) Then dinner with a very old friend (Steve Lumetta) and his family.

Saw interesting talks by Ramesh Johari, Balaji Prabhakar, Jean Walrand, Adam Wierman, and others. I talk with people about hashing, Bloom filters, deletion channels, sticky channels, floating codes, all manner of things. It's fun being at a conference where the usually disparate seeming parts of my research don't seem quite so disparate.

Sadly, a quick trip this year. I fly back early tomorrow.

Allerton : Floating Codes

A couple of decades or so ago, Ron Rivest and Adi Shamir wrote a fun paper on write-once memory. Think of a punch card -- you can turn a 0 into a 1, but you can't turn it back again.
Optical disks were a potential application. Suppose you have a k-bit value that is going to be written t times. How many write-once bits (or "wits") will you need to store it through the t changes?

Fast-forward a few decades, and similar models are coming back into vogue, because of flash memory. My understanding is flash memory uses floating cells; roughly, cells are organized into larger blocks of n cells, and each cell can hold a number of electrons from 0 to q-1. It's easy to add electrons to cells, but not to remove them; to do that, you have to reset the whole block back to 0's first, which is both expensive and wears out the memory, which has a limited lifetime of resets. Suppose you want to store k ell-ary variable values in a block. How many rewrites before you need to reset? Note that a "code" in this setting consists of two things: a mapping from cell states (the state of the entire block) to variable states, and a transition function giving how cell states change when variables change. For more of an introduction, see this paper by Jiang, Bohossian, and Bruck.

In our paper (pdf,talk slides) for Allerton, we introduce (as far as I know) the question of considering floating codes in the "average case"-- the previous work was considering the worst-case number of rewrites before a reset. Given the lifetimes available to flash memory, and the potential to model system behavior before productions, we think analysis of average case performance makes sense here. For our notion of "average case", we assume that the variable values follow a Markov chain, and the goal is to maximize the long-term average time between resets. Given a code, the Markov chain on the variable states induces a Markov chain on the cell states. So the question becomes how to design a code to maximize time between resets on this Markov chain.

Following in the footsteps of the JBB paper, we find some initial interesting results, and leave a lot of open questions -- including the complexity of computing optimal codes for general versions of the problem. I think is yet another potentially interesting coding area where CS ideas should be able to play a strong role. And while I'm not (yet) an expert on the practical implications of these theoretical coding models, the connection to flash memory seems promising.

MSRNEOS

I spent most of the day over at the Microsoft Research New England Opening Symposium over at MIT. It was a very nice event. Part of the fun was that it was well attended -- I got to catch up with some people I haven't seen for a while. But they also had a very nice collection of speakers.

There was a panel discussion on interdisciplinary research (a theme of the new lab), and a natural question was how such research should be encouraged. Nobody on the panel seemed to make what I thought was an obvious point: one way to encourage such research is to make sure people across the sciences are well trained in mathematics and (theoretical) computer science. Interdisciplinary research depends on finding a common language, which historically has been mathematics, but these days more and more involves algorithms, complexity, and programming.

Luckily, to make the point for me, Erik Demaine next gave a talk entitled "(Theoretical) Computer Science is Everywhere", whipping through examples in arts, business, society, games, other sciences, and so on. It was a really inspiring talk, one that should be given to incoming freshman in the field, or better yet, to high school students who don't know what computer science is about. The talk was taped and hopefully I'll have a link to it soon. Afterwards, as several of us were talking about it, there were some minor issues raised. I myself brought up my common concern that perhaps more theorists should take a more direct role in promoting the practice of CS theory, including in other fields. My colleague Greg Morrisett questioned whether Erik couldn't have replaced "Theoretical Computer Science" with "Applied Math" and given pretty much the same talk. I think it's an interesting point, although I do think TCS's emphasis on complexity and algorithmic thinking does give it a distinct perspective.

Another talk I enjoyed (more than I thought I would from the title) was "Understanding Socio-Technical Phenomena in a Web2.0 Era" by danah boyd, who will be starting at MSR NE this January. She is an ethnographer who studies how adolescents interface with technology. So, to summarize, the talk was about why kids (at least in the US) spend all their time on MySpace and Facebook, and what it all means. It was very well presented (similar in style to Lawrence Lessig, who gives fantastic talks), and perhaps my interest stems from now having three kids; getting a perspective on how adolescents use online spaces to interact and communicate (as well as rebel and establish their own identitites) was quite enlightening.

So while they've been around for most of the summer, it's nice to have an official welcome for the new neighbors!

UPDATE: Link for talks.

This Week, Allerton

The 46th Annual Allerton Conference is this week. The program (not as easily accessible as it should be) is here. I'll be going, but sadly, it will just be a 1-day drop-in to give my talks. Travel is a bit of a luxury, with the new baby and all.

I wasn't sure if I was going to go to Allerton this year. While I enjoy the conference, I have had growing concerns that because many talks/papers are invited and their proceedings aren't widely distributed that the papers I present there aren't as noticed as they would be otherwise. They've alleviated that concern somewhat by having the papers now available on the IEEE online system. At least I know if anyone tries to find the paper, the official copy will be available somewhere (besides my home page). Hopefully the old Allerton proceedings will go online at some point too.

The other motivation for going to Allerton this year was that it forced me to get some things done. Between the faculty search last spring and the offspring this summer, it's been a bit difficult to complete some of my research tasks. There's nothing like promising to have a paper in on a certain date - a non-artificial deadline -- to get things to some sort of stable state.

I'll hopefully have posts up later this week about the new papers.

Small Steps...

Every once in a while, I see a blog entry or comment with the lament that the CS publishing model is just wrong. The common statement is that the conference-oriented publishing approach leads to incremental, trivial papers, solving problems that are easy instead of the "real" problem.

I'd like to offer a contrasting opinion, one I've stated before, but may be new to some. (And since the criticisms above are repeated cyclically, I don't see why I can't repeat my response.)

Having worked some in the area of heuristic algorithms, I've gained a healthy respect for the fundamental approaches of repeated refinement, parallelization of efforts to explore a search space, and the occasional bit of random wandering. Greedy-style heuristics don't get to good answers by big jumps, but a multitude of small steps. Parallelization, leveraging the power of crowds, greatly speeds up such heuristics, and frequent communication between the agents working in parallel helps move everything along. And most good heuristic algorithms require a bit of a random (or explicit!) push to keep moving through the space of possibilities, to find new parts of the search space to yield better solutions than the already plumbed over areas.

The CS conference publication model shares these features. Yes, there are many more small steps than big jumps. Yes, there are times where less fruitful and interesting directions are explored. But the community as a whole moves rapidly, churning through ideas and, I think, rapidly focusing on promising ones. Also, new ideas and directions arise with, I think, remarkable frequency. Looking at any single conference, you might think over 90% of it is junk -- or, at least, no so important in the grand scheme of things. And you'd probably be right.** But that doesn't a priori mean the conference publishing system is broken, and any argument that it is based on such reasoning doesn't even start to convince me.

This doesn't mean that we are excused from having taste and opinions as to what constitutes good work. Indeed, without this, we'd lack an evaluation function to lead us in the right directions. And I'm not saying the the contrasting "mathematics" style of publishing only fuller, complete papers is necessarily worse -- I don't think I've seen evidence one way or another. (I might admit to having a personal preference.) But if you want to argue the point, you need to do more than just look at individual papers in individual conferences, and focus on the whole.


[** A favorite quip from grad school that I still remember was when a systems friend told me "95% of theory papers are crap!", and I simply responded, "So that means we're 4% better than systems." Good times.]

Communications of the ACM, Theory Bias?

Anyone else noticing a pleasantly refreshing pro-theory bias at the "new" Communications of the ACM? One news article on spectral graph theory extensively quotes Fan Chung Graham, Milena Mihail, and Jon Kleinberg. Another on privacy extensively quotes Cynthia Dwork and Frank McSherry. One of the presented research papers is on Distributed Selection by Fabian Kuhn, Thomas Locher, and Roger Wattenhofer (from SPAA 2007), with a perspective given by Hagit Attiya. Finally, there's a puzzle column by Peter Winkler.

I admit, I'm no longer just automatically throwing it away. The entire magazine seems more interesting since the editorial refreshening. But deserving nods to the work of theory community will certainly help hold my attention.