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.

SODA, and Parallel Sessions

The list of SODA accepted papers is up.

For both my own curiosity, and probably Claire Mathieu's, does anyone have any ideas or suggestions on how to schedule parallel sessions? It seems like a nasty problem, particularly since you have limited information on what conflicts are, other than very general categories for papers.

Big Numbers

In my algorithms class, at some point, I teach RSA and primality testing. For the corresponding assignment, I usually have students do a "numerical exercise" which involves, naturally, computing with some big numbers. They also have a later programming assignment where they have to use numbers that may not fit into a standard-programming-language-sized integer. Since this is not a programming class, and I do not prescribe a language for them to use, I essentially tell them it's part of the homework to figure this out.

Surprisingly, it seems to give a number of people significant grief every year. I know that for C and Java it's a pain -- the natural thing to do is to download and install a BigNumber library, which should be easy, but often some trouble arises. (And most students, even though they've had the intro programming courses, do not seem to have learned how to do useful things like download and run useful libraries.) There are other programming languages which handle big numbers essentially transparently -- ah, the days of programming in Lisp -- which are fine for the numerical exercise, but may not be as nice for the larger programming assignment.

My only real point here is that, in those lists of skills I would expect CS majors to have, I'd have to put "being able to do computations with very large numbers" somewhere on the list. Yes, you're unlikely to need it for your standard checkbook program, but it seems to me this issue arises in plenty of places. (It has for me -- and my graduate students -- several times.) And it's not so important that they know how to do this specific task off the top of their head, but more that when they're given a task like this, they are able to find the information they need and complete it in a timely fashion. For better or worse, that's something some of them get out of my class.

A Survey on Hash-Based Packet-Processing Algorithms

Sometime way back, Graham Comorde invited me to a DIMACS workshop on Algorithms for Next Generation Networks, where I talked the usual talk about hash tables, Bloom filters, and things. The organizers later had the wherewithal to undertake putting together a book or collected chapters on the topic, and asked us (us being, of course, me and my student Adam Kirsch) for a chapter related to the talk. Adam was just finishing his thesis, and was willing to take on modifying his thesis to form the basis for a survey chapter. I wrote up a section or two, and for good measure, we got George Varghese, who is the world expert -- and author of the book Network Algorithmics -- to join in as well. (In particular, we really wanted George's much more practical perspective on what works and what doesn't!) The result here is a hopefully pleasant light read on current goings-on in the area of hash-based network algorithms, attempting to blend and show the connections between theory and practice.

There's still time for feedback for the final version; please mail me if you have any constructive suggestions.

And Now, a Word from Our Sponsors (Part 2)

Continuing from last post, my trip to CA.

I visited Google and gave the CAM talk there also, where it also seemed to find a receptive crowd. (Some challenging questions arose as to whether cuckoo hashing is the right approach for hashing in software, as opposed to hardware.) Visiting Google is now like visiting a college campus, or maybe a small city. I was greeted at the parking lot by someone who directed me to valet parking. (The valet didn't seem to be there, though, so I parked myself.) I passed the volleyball courts, cafes and other places to eat, and that dinosaur on the way in; saw the gym, laundry room, doctor's office, massage area, and many many coffee-soft drink-snack bar areas; and ate at the amazing cafeteria. (The sushi line was too long, so I had to skip it. However, they did have an entire freezer full of It's It ice cream sandwiches, packaged specially with the Google logo. It's It alone is worth coming to they Bay Area for.)

I find myself without envy for the Google campus and its well-publicized perks. My limited impression was that it's too crowded and busy for me; it seems like it would be a hard place for me to concentrate get work done. I'd surely balloon up in size surrounded by open larders of food, even with the gym. I suppose I'm now just too old to enjoy the place properly, though I imagine it's fantastic for recent graduates!

The last stop on my tour was Yahoo! Research. It's always great to catch up with my "mentor" Andrei Broder, who these days always seems to be running at 110% or more. Their research group (like Google's) seems focused on Web-related algorithmics, machine learning, and this new subfield of computational advertising (I believe Andrei coined the term, in any case I like it). I talked with people about some compression-related problems, and perhaps something further will come of that.

As usual, I find myself wishing these trips could last longer. There's always too much to do and too many people to see on these visits, although that's what makes the trip interesting and fun.

And Now, a Word from Our Sponsors (Part 1)

I've just returned from a trip to Silicon Valley, where I visited Cisco, Google, and Yahoo -- all of whom have generously given me research money this year, and hence the CA visit. Besides thanking them in this blog, I thought I'd say a few things about the trip and what I saw on my brief stops at the various places. The purpose of these visits is mostly to see if I can get collaborations going, but I admit, some part of it is just giving face-time to the people and companies who have given me research money. They deserve some of my time, and I'd like to encourage them to keep providing funding!

The first stop on my trip was actually a visit to Microsoft Silicon Valley Research Lab (MSRSV). I still haven't figured out how to get research money from Microsoft, but MSRSV "started" when a lot of my colleagues at what had been DEC/Compaq/HP Systems Research Center moved en masse to Microsoft, so I have historical ties and recent collaborations with people there as well. Since my visit last year, MSRSV has moved into a very nice new building. Lots of open spaces and whiteboards everywhere. It seems wonderfully set up for group collaborations. (One very nice space for group-work, though, is a bit too close to a loud and frequently used coffee machine for my taste...) Besides catching up with everybody, Udi Wieder and others indulged me by talking about some of the many variations of trace reconstruction problems that are still open. Hopefully we'll get somewhere on some of them.

Cisco is a huge sprawling collection of buildings, and the visit there itself similarly felt chaotic. They asked me to give two talks, which caused me a bit of stress the week before the trip as I reworked some slides. I ended up talking about my work with Salil Vadhan on Why Simple Hash Functions Work (talk, paper, blog post), and gave a mini-survey covering my work with Adam Kirsch (and part with Udi Wieder) on how to use CAMs to improve cuckoo hashing (talk, various papers on my papers page). [Actually, I have a new survey article covering this stuff I'll put up shortly.] Cisco still seems very, very generally interested in hashing, and applications of hashing in network measurement and monitoring in particular. I had about 40-50 people show up for the first talk, and the second mini-survey talk was broadcast and recorded for Cisco -- about 50 people showed, and apparently more than that were also listening remotely. (Just like when I teach, and my class is taped...) They have a pretty elaborate setup for these recorded technical talks, with a room set up for guests like Steve Wozniak (who was there a couple of weeks ago) rather than me. Besides giving talks there were a lot of high-level discussions about things going on with Cisco where I might be able to collaborate usefully with them.

One thing I noticed at Cisco was a much larger number of women than usual at my talks. Perhaps EE is turning out more female graduates than CS recently, or it's somehow reflective of Cisco's hiring practices.

Visiting Cisco is always very exciting. They're a lot more short-term focused than research labs, but there is this wonderful sense that what you're talking about could become a part of the fundamental network architecture. They keep me away from details, but multiple-choice hash tables and Bloom filters seem to be standard tools in their arsenal now. I'm hoping some form of cuckoo hashing might be as well someday.

STOC 2009 Preliminary Page is Up

See here.

NSF Expeditions, Complexity

I'm glad to hear of the news that Sanjeev Arora's team at Princeton was one of the winners for the NSF Expeditions grants, working on the general theme of complexity. I think it shows that some of the public relations work our community has been doing, especially with the NSF, is paying off in concrete ways. I also think that more money for theory generally just has to be a good thing -- it's $10 million more for theory than there was before.

That being said, I'll express two concerns:

1) It's odd to see so much money for theory concentrated into such a small geographic area. I realize that was the nature of the Expeditions program, and I don't fault the proposal for it. It just strikes me as strange when the general budget for CS theory is so small to earmark such a large sum of money to this project. It feels like an over-concentration of resources in what's already a small community.

The solution to this, of course, is to get more money for the general CS theory program. And I'm sure a significant chunk of the Expeditions money will go to open DIMACS-style collaborations like workshops and other events, minimizing this concern.

2) I know it's just the nature of theory, but reading over the blurbs about the various funded Expeditions proposals, I can't help but notice that while the others seem to have some sort of statement of clear goals to take things in new directions ("hope to create a new field of computational sustainability", "It aims to create an "open" alternative to mobile ubiquitous computing and communication that can spur innovations, which will have a dramatic impact on the choices users will have in the way their data and information is computed, stored and communicated", "The project aims to develop tools and theories for molecular programming--such as programming languages and compilers--that will enable systematic design and implementation of technological and biotechnological applications that require information processing and decision-making to be embedded within and carried out by chemical processes."), the complexity grant will "hope to better understand the boundary between the tractable and the intractable" and "attack some of the deepest and hardest problems in computer science". Doesn't that sound, I don't know, just like business as usual? My concern is that it's probably important to the theory community long-term for this Expedition to have some major concrete success attributed to it at the end of the day. I have no doubt that good things will come out of this, just based on the people, who already do good work -- but will the output be the sort of things that in retrospect justify this investment?

Book by FemaleScienceProfessor

I'm an occasional reader of the blog FemaleScienceProfessor. Often the blog is just about being a science professor, which is interesting, and I can relate to. And sometimes the blog is specifically about being a female science professor, which is also interesting, even if I relate to it less.

Well, FSP has re-worked past blog entries into an on-line book available at lulu.com. I haven't yet bought and downloaded it yet, but from the Table of Contents, it appears to be a particularly worthwhile book for graduate students thinking about a life in academia, and for new faculty. The bulk of the book seems gender-neutral, if that's a concern. I thought I'd give it a free plug.

SIGCOMM 2008, Part 3

Here are a few more papers from SIGCOMM which should be of particular interest to a more theoretical audience. (Generally, SIGCOMM papers are interesting -- but again, I'm focusing here on papers that I think might be of special interest to theory people. It strikes me that I should, at some point, similarly summarize papers from a major theory conference -- like STOC 2009 -- that would be of special interest to networking people. Of course, SIGCOMM makes that easier, posting abstracts and all the papers online...)

There's a paper on analyzing BitTorrent in the game-theoretic incentive-style analysis sense. It will require a more careful reading from me, as I'm not a full-fledged game-theory/CS type researcher, but it sure looks interesting on the first perusal. I'm naturally biased to the idea that if all this current effort on game theory that is going on in computer science (and particularly in theory) is to have payoff, real-world protocols must be considered and analyzed. So in that sense, this should be a really interesting paper.

While it doesn't appear particularly theoretical (it looks like what I like to joke is a standard networking paper -- lots of pictures and tables, no equations...) this paper on spamming botnets from Microsoft includes Rina Panigrahy (well known for his work in both theory and practice) as one of the co-authors. (I figure Rina had something to do with where I saw the words "entropy reduction", but that's just a guess...)

SIGCOMM 2008, Part 2

The Accountable Internet Protocol (AIP) paper asks the question: what if we re-architectured the Internet to start with self-certifying addresses, so that there was a layer of accountability -- you'd know where packets are coming from. This paper clearly fits square in the mold of the NSF FIND program. They suggest what a self-certifying architecture would look like, how routing would work with such an architecture, consider potential attacks on the proposed architecture, and discuss whether technology trends would make such an architecture feasible. Certainly interesting, although I admit to high-level unsubstantiated concerns about the specific address architecture they propose. (I suppose as a "kid" I saw too many key-exchange-style protocol papers where a subtle flaw was exposed by a subsequent paper...)

I notice they used a Bloom filter in the paper without even giving a citation. Have Bloom filters now become so successfully widespread in the networking community that no citation is needed? What a nice thought! (Or maybe the authors just ran out of space for the citation.)

Another SIGCOMM paper continues on the path set out by for example Feigenbaum, Papadimitriou, Sami, and Shenker, on using game theory to study the behavior of BGP. They propose a more realistic model (where, for example, Autonomous Systems can be paid for attracting traffic) which, naturally, leads to more negative results in terms of the truth-telling behavior of ASes. (Why is reality so often disappointing this way?)

SIGCOMM 2008, Part 1

About a year ago, I took a look at some SIGCOMM 2007 papers. I won't be attending SIGCOMM this week, unfortunately, so in the interest of self-education, I thought I'd look at some of the papers this year. (The site currently has the papers up. Wow, what a neat idea...)

Before getting into papers, I thought I'd mention that Don Towsley is being given the ACM SIGCOMM award. This is a great choice, and well deserved. And relevant to this site's audience, Don is, in my mind, primarily a theorist. Not a FOCS/STOC theorist to be sure, but a theorist nonetheless. As the award announcement states:

Towsley, who is Distinguished Professor of Computer Science, has made innovative and pioneering contributions in developing foundational modeling and analysis techniques that have enabled a better understanding of some of the most important aspects of today's computer networks, network protocols and networked applications.

Modeling, analysis, understanding... that's what theory is all about. It's people like Don that made networking an open and understanding place for people like me. Thanks! And hooray for Don!

Now for papers. As before, I'll give brief synopses (at the level of the posted abstracts :) ), as I'm just looking at these papers on the fly. The network coding crowd has attacked again with the MIXIT system, which seems to throw together a bunch of ideas in a clever fashion to improve performance on wireless mesh networks. Recall that the basic working definition of network coding is that intermediate nodes do more than store and forward, they can process the packets as they come through (creating encoded packet variations). Here, the basic unit is not taken to be a packet, but a symbol (a small collection of bits), with symbols being packed into a packet. This allows nodes can "take apart" packets; if a whole packet doesn't come in error-free, the node can take symbols that appear to be right with high enough probability (based on information from the physical layer), and re-package (via linear combinations, a la "standard" network coding) and send on only those symbols. Because erroneous symbols might get through, an end-to-end error-correcting rateless code is also used. All of this appears to improve throughput.

The paper seems interesting -- another proof-of-concept paper for network coding in wireless systems, which is where I suspect network coding will be able to make the most inroads over the next few years. I can't tell yet how practical this really seems (without a more detailed reading), but the idea of taking apart packets and sending only the good pieces in combination with multiple coding techniques seems quite nice.

As an aside, the pdf for this paper seems to contain a picture or something that crashes my poor Mac around the 8th or 9th page. Help!

Security Issues in Cambridge

Harvard is getting new ID cards next year, thanks to an ambitious student who apparently figured out how to forge IDs (including a duplicate ID for University President Drew Faust). Because, really, how could using unencrypted ID numbers on the card, and giving access to undergraduate computer user assistants access to all ID numbers, ever lead to a problem? (The student also apparently made fake state driver licenses as well. Who says Harvard students don't learn useful real-world talents?)

Of course, Harvard isn't the only institution in Cambridge where students can obtain skills in the security area. Some MIT students, working under the famous Ron Rivest (the R of RSA!), figured out several flaws with the new ticket system for the Boston subway system, including ways to rewrite tickets so that they have lots of money available on them. So, naturally, the subway system sued to keep them from talking about the flaws at a security conference.

In both cases, the systems seem easily breakable (well, at the least the Harvard IDs were easy, not sure about the subway) with a card writer that can be obtained for a couple hundred bucks.

Of course, I'm not surprised, based on previous experience.

I wonder when organizations that want secure cards will realize that perhaps they ought to ask the students to try to break the system before they deploy it, rather than wait for them to break it after.