Monday, October 15, 2007

Broadening the Teaching of Theory

Offhand, I can think the following primary "types" of computer science classes:
  1. Classes specialized for graduate students in a subfield (e.g., theory, or usually the next level down, e.g. cryptography, pseudorandomness).
  2. Classes for graduate students in CS.
  3. Classes specialized for undergraduate CS majors.
  4. Classes for undergraduates primarily in other sciences.
  5. Classes for general, non-science undergraduates.
I think most CS professors naturally gravitate to teaches types 1 and 3 -- classes in their area of specialization. I think, as a community, there is generally at least some effort by theorists to broaden the scope of some at least classes to types 2 and 4. Certainly I try to encourage non-CS majors into my undergraduate algorithms class -- what scientist shouldn't be learning to think algorithmically? -- and to get non-theory graduate students to take my randomized algorithms and algorithms at the end of the wire courses. I suspect, though, as a community, we could be doing more. While personally theory seems less isolated within CS today to me than it did say a decade ago, there still seems to be plenty of bridges left to be built.

Perhaps more challenging is classes of type 5 -- classes for non-scientists. The question of how to design a science distribution requirement course for non-scientists is not specific to computer science, but in CS it perhaps especially challenging. Programming is often taken to be off-limits, since how much worthwhile programming can be taught to people who have never seen a computer program before? And theory seems to require too much math. Plus there is the age-old question of how to make it all relevant to non-scientists.

Harry Lewis co-designed a course, Bits, which I think is a great example of what's possible, and is the course I wish I could have designed, if I wasn't so busy teaching my regular classes. I enjoy this first paragraph from the course description:
This is a course about information for students who are not technically or mathematically oriented. It aims to explain the dramatic increase in the amount of information that is being communicated and stored, and the consequences for society of that increase in capacity.We are on the cusp of a revolution, potentially as consequential as the invention of printing or the replacement of animals by steam engines as the vehicles of transportation.The course aims to equip those who will determining policies, whether as legislators, corporate leaders, or ordinary citizens in their multiple roles, with an awareness of the choices that lie only a short time ahead of us.
I am also strongly biased in that Harry followed my advice, with much of the technical meat in the beginning of the course covering basic information theory, specifically compression and coding. (Note: I emphasize that Harry followed my advice, not that he took my advice. As far as I know, he always planned to structure the course this way, and it's just happenstance that his take on what was worthwhile matched mine. I'm pleased nonetheless.)

The course is an interesting mix of science, technology, and policy. The lectures are now apparently freely available online now that the course is over for those who want to see it. Someday, perhaps I'll get to design a course like this. I'd be curious to hear from others what other examples there are for CS-based courses with non-trivial technical content meant for non-science majors. (Jon Kleinberg's course new course comes to mind, but it really seems to be type 4, built for scientists, including mathematically oriented economists and sociologists.)

Tuesday, October 09, 2007

The simplest insertion/deletion channel

The simplest binary insertion/deletion channel that I can think of is the following: with probability p, each bit independently results in two copies of itself. This is a special case of a subclass of channels that I have dubbed sticky channels, which are like sticky keyboards: each symbol can result in a random number of copies of that symbol.

Sticky channels have the nice property that contiguous blocks of (resp 1s) at the input correspond to contiguous blocks of 0s (resp 1s) at the output. This property makes sticky channels easier than more general insertion/deletion channels.

I've just had a paper on sticky channels accepted to Transactions on Information Theory; here's a link to a preprint. The main result is that for that simplest channel above, I can numerically obtain very tight bounds on the channel capacity. But of course I'd still like to know -- is there a simple formula that gives the capacity as a function of p? And is there are simple and efficient coding scheme that nearly reaches the capacity?

Friday, October 05, 2007

The Importance of Recommendation Letters

If there is one piece of career-gamesmanship advice I would give to anyone, especially undergraduates eventually looking to get into graduate school or beginning PhDs who will be eventually looking for jobs, it would be to think carefully well in advance about where you plan to get letters of recommendation from.

For graduate school, your letters are probably the most important deciding factor for whether you'll get accepted or not. For job searches, good letters won't really get you the job, but you'll need great letters to even get your foot in the door for an interview.

Yes, great work will trump everything (if you do really great work, you'll get the great letters). But I've seen numerous students do less well than they should have because they didn't think well enough in advance about this part of the game.

For undergraduates thinking about graduate school, have you formed a close working relationship with one or more faculty members? (This can be done by doing research with them, writing a thesis with them as an advisor, being a teaching assistant for them, etc.) Lots of students will have exceptional grades and test scores; we want to know about you as an individual, and your capacity for research. Letters are the best way for us to get this information. Particularly if you go to a smaller school or a school with a smaller CS department, you may want to try to find a way to do a summer internship with a "bigger name" person -- a letter from such a person will likely make the difference between getting in and not for many places.

For graduate students thinking about jobs, who besides your advisor is going to write you a letter? We expect your advisor to say that you're wonderful; we want to hear from less biased sources. (Many students fall into the trap of working almost exclusively with their advisor -- good in the short-term, not in the long-term.) What other faculty have you worked at your institution? Have you worked with anyone from another institution? Have you thought about doing a summer internship -- which can be worthwhile just to get a good letter! It's important to work with multiple people, not just your advisor, so we can see multiple letters explaining and confirming why you and your work are so outstanding.

I thought about this after a discussion on the complexity blog about graduate school detoured slightly into the subject of letters for jobs (in particular, check Paul Beame's insightful comment #41).

By the time you get to tenure, letters are still important, but ostensibly you have less control about where the letters come from. The same general advice seems to apply, though -- great work trumps all, but working with or having some shared experience with many colleagues, including more senior ones, can be key to career advancement.

Tuesday, October 02, 2007

Set Your Own Price for Music

Tangentially related to my previous post on why Harvard should be free (but you pay later through donations), via the Machinist I've learned that Radiohead (some "music group" -- I'm old and out of touch...) is putting their new album online and letting people choose what to pay to download the album here. (More information for actual music fans is available from the Machinist in a follow-up.) This sounds like an interesting experiment, and I'm very curious to see how it works out for them.

Somehow it made me think, will the pick and play model of iTunes ever make it to universities? Imagine selecting your own collection of courses for your undergraduate or graduate degree, without being limited to your actual physical university; you could take say Kleinberg's Structure of Information Networks, Roughgarden's Introduction to Algorithmic Game Theory, Demaine's Geometric Folding Algorithms, and so on... of course, an appropriate payment mechanism would have to be designed, but the possibilities are exciting and frightening at the same time...

Monday, October 01, 2007

Cyber-Enabled Discovery and Innovation Call

The CDI call was finally published last Friday at http://www.nsf.gov/pubs/2007/nsf07603/nsf07603.htm. There is related information here. The time scale for moving on CDI is rather short; letters of intent are required, with a first due date of November 30. But CDI looks to be the ITR of next few years, so lets get lots of theory-related proposals in...

Thursday, September 27, 2007

Allerton Conference, Part III

I very much enjoyed the Allerton Conference again this year.

The highlight for me was the sessions on Networking Games and Algorithms. Bruce Hajek has been organizing excellent networking sessions for years, and I think this year the focus on network games really paid off and led to some very compelling sessions. I arrived to hear Ramesh Johari, Vijay Vazirani, Tim Roughgarden, and David Kempe all give great talks back-to-back. I'm expecting they'll have a similar set of sessions next year, hopefully expanded!

A small disappointment was that there seemed to be fewer talks on coding theory this year. Plenty on network coding, but very little on standard coding theory. (This may have to do with Ralf Koetter recently leaving UIUC; in any case, many people I usually see there, like Muriel Medard, Ralf Koetter, Michelle Effros, Alexander Vardy, and so on didn't seem to be there.) A top coding theorist who was there independently confirmed this impression; hopefully, things will be back to normal next year. This year, I'm glad the network games sessions kept me so busy.

Wednesday, September 26, 2007

Allerton Conference, Part II

At Allerton, I'll be talking about some follow-on work to some previous work my graduate student Adam and I did on cuckoo-like (or better said cuckoo-light) hashing schemes. In that work, we focused on schemes that allowed only one additional move per insert, and used a CAM to store the rare element that couldn't be placed. Besides simplicity, an advantage of such an approach is that we can analyze many basic one-move schemes.

In our new paper, we look at a different approach; here we use the CAM as a queue, so the CAM holds elements that are being moved but have not reached a resting place. Using the CAM as a queue is somewhat more complicated in terms of an implementation, but it allows one to essentially implement a full cuckoo hashing scheme. The queue is used to de-amortize the amortized performance of cuckoo hashing. That is, on average inserting an item in the queue take a constant number of moves, but in the worst case it can take Omega(log n) moves (where n is the number of items being stored). If we allow the queue a constant number of moves per insert, then the queue can simply buffer the insertions that take too long. The result is even better space utilization (naturally, since more moves are used per insert). The paper and talk slides are available.

Sadly, this ended up being essentially an experimental paper. The problem is that there are too many open questions in the setting of cuckoo hashing. For example, in the practical implementations I know of, for cuckoo hashing with d > 2 choices of locations for an element, when an element has to be kicked out, one chooses the element randomly. The analyses I know of are based on doing a breadth-first-search to find an element to kick out, which isn't really practical (certainly not in hardware). As a result, I believe it's still open to prove things like constant average moves/worst-case logarithmic moves for standard cuckoo hashing when d > 2. To really do an analysis of the queueing process, we'd need even more detailed information about the distribution of the number of moves required per inserted element. Lots of good open questions left here...

Monday, September 24, 2007

Allerton Conference, Part I

This week I'll be headed to the 45th Annual Allerton Conference on Communication, Control, and Computing. For those who aren't familiar with it, the Allerton conference is held every year at an out-of-the-way spot nearby the University of Illinois at Urbana-Champaign. (Yes, that's purposely redundant.) The focus is on what CS people think of as EE theory, but as I so often claim, that line is really quite blurry. Lots of information theory and control theory, but there are also sessions on network coding, networking games and algorithms, learning theory, distributed computing, scheduling and queueing, and so on. The organizers are actually very keen on getting CS people to come; offhand I notice that Tim Roughgarden, Vijay Vazirani, Andrew McGregor, and I'm sure several other "CS people" will have papers there. The conference is always extremely well organized, thanks to the fact that it's in the same place every year, and organized by the same people. (I personally have always found the UIUC staff that run the conference extremely helpful. They do an outstanding job.)

One of the interesting things about Allerton is that it's a mixed of invited and submitted papers. The understanding is that if you're invited to give a paper, you're supposed to go and give the talk, not a student. So there are a lot of big-name people giving talks at the conference. Also, invited papers have a lot more leeway. Sometimes, a talk will mostly be a survey, or a discussion of preliminary work on a problem. Some of the best talks I've seen there have been these kinds! Attendance the past few years has been over 300, so it's a nice-sized conference.

I've heard some complaints about Allerton. First, UIUC is out of the way, and the Allerton site is about 20-30 minutes from the main town. If you don't know the place, it's easy to get bored post-conference. Usually the various UIUC hosts have some sort of dinner, and the town is actually a nice small college town. So if you get to know the place and the people, it's not really a problem. (Also, it means the conference is a great place to start a new collaboration, after the talks.) Second, generally there are 6 parallel sessions going on. Many people don't enjoy that. I usually find I'm interested in 2 (coding something and network something) at the same time and have to hop around. Third, I've heard CS people say they don't know which talks they should go listen to -- who are the really good speakers and what are the interesting topics. CS and EE people don't really know each other as well as they should, and there is some cost in getting to know a slightly different area and group of researchers. Fourth, the quality of papers is mixed. Some blame this on the "invited papers", but I think it's just true anywhere, especially for large conferences. Fifth, they don't have a published proceedings in the way that other conferences do. I think that's changing from what I've heard, and these days people just post papers on arxiv or their web page anyway.

The biggest complaint that I would agree with is the conference has grown beyond its location. Some rooms are small and easily get too noisy, making it hard to hear the speaker. The conference has just proven too successful!

I really enjoy the Allerton conference. It's a different set of people than I usually see, but work I'm very interested in. It was at Allerton that I first heard about the coding problem for deletion channels, which I've since worked on quite a lot. I've had multiple collaborations come out of the Allerton conference. I'd really encourage people who don't know about it to take a look.

In the other posts this week, I'll talk about what I'm presenting there, and about interesting things I see at the conference.

Friday, September 21, 2007

Opinion Poll: Star Simpson, Airport Scare

I don't usually cover "current events" in this blog, but I decided this one was suitable, being both local and technical. By now I'd imagine almost everyone has heard of MIT student Star Simpson's near-fatal fashion faux pas at Logan Airport. For background and two opposing views on the subject, see the Machinist blog entry and this other random blog entry.

I imagine the crowd reading this blog is more "technical" than the average, so I'm curious what you all think. Is Star out of touch with reality, are the police in a state of extreme over-paranoia, or both?

Thursday, September 20, 2007

What Do Professors Do? Part II

Following up on my last post... in one respect I know I'm spending more time on administrative issues recently. Last semester I started serving as a faculty member on the Harvard "Ad Board" -- literally, the Administrative Board. This is the committee that handles the "application and enforcement of undergraduate academic regulations and standards of social conduct". If you're in trouble for bad grades, cheating, plagiarizing, fighting, alcohol abuse, or anything else that's mentioned in the Harvard rules, your case gets brought to the Ad Board. We also handle several more positive and pleasant administrative duties, of course, but the bulk of the actual work involves the cases of students experiencing serious academic problems or accused of violating university rules.

This is a remarkably time-intensive committee. We meet weekly, and it's not at all unusual for the meetings to last 2-3 hours. Plus there's prep time involved in reading the cases before the meeting. There are only a few faculty members on the committee at a time. Most of the committee is made up of administrators and the "resident deans" -- people who live at the Harvard dorms (or "houses" in Harvard-speak) and are responsible for the care of students.

Several of the resident deans have asked me what I did to get stuck on the committee. I generally answer that I didn't realize it was a punishment! (In fact, then-Dean of Students Dick Gross asked me to serve. As he and Harry Lewis were my senior thesis advisors as an undergraduate, I found it hard to say no. I've found this sort of thing is a problem about going back as a professor where you were an undergraduate; people are more familiar with your name and stick you on committees.)

It is indeed a very challenging committee. I've learned some important things, including all about the infrastructure for helping Harvard students with problems and how I can help lead students to this infrastructure. One perhaps obvious lesson is that most often students get into academic trouble -- in particular, with plagiarism -- because they leave assignments until the night before and then take shortcuts to get them in. I've always been quite strict with undergraduates about homework deadlines -- I think overall students need better time management skills and try to do too much -- but I admit I've softened up since being on the committee. Contrary to many students' belief, I don't want my class to spur a breakdown. But remind your students over and over -- the night before is no time to start a theory problem set (or any other assignment)!

Monday, September 17, 2007

What Do Professors Do?

A number of times I've had undergraduates ask me, essentially, "What else do you do?", which sometimes is an honest interest in what else my job entails and sometimes appears to be a concern that when I'm not teaching them, I'm just sitting around my office thinking up new ways to torture them via problem sets or soaking up tuition money.

At a high level, I know what else I do: research, write papers, give talks, go to conferences, manage and work with graduate students, advise undergraduates, seek funding, sit on department and university and theory-community committees, review papers and grant proposals, act as editor for a few journals, serve on program committees, write letters of recommendation, deal with standard administrative paperwork, and... well, I'm sure there are a few other things as well that I've forgotten. Let's count blogging as part of my job, too. And I consult on the side. Come to think of it, it's a wonder I have time to teach. (That probably explains the students' question. They're wondering if I have 40 working hours a week, why isn't this class better?) Of course, I'm know I'm not unusual; all this seems like standard faculty stuff.

What I've been realizing lately I don't have a good handle on is how much time I spend on these various activities. It has seemed to me that in the last few years -- since getting tenure -- a lot more of my time is going to administrative duties than to research-style activities. If true, that fact along with my poor time-management skills seems like a recipe for disaster. So this semester, I'm going to try a little experiment, and try to track my time in a spreadsheet somewhere, to start getting a better handle on what's going on. And figure out what activities to cut.

Of course, I'm curious -- what are others experiencing? How much time do you think you spend on various activities, and is there a pre-post tenure change? What's the biggest impediment to research time?

Thursday, September 13, 2007

How to Handle Bugs in Others' Papers?

Some colleagues and I are working on extending a certain known result. There's a journal paper with a proof of the result that seemed like it would allow a reasonably straightforward extension. Except that, now as we go through it carefully to figure out how to prove our extension, we have found what seem to be at least one and possibly two fatal bugs in the argument. The result is almost certainly true -- there's an earlier paper with a much more complicated proof that seems much less amenable to our extension -- but it seems unlikely that the approach taken for the simpler proof works without some very major changes.

How best to handle such a situation? The authors are good researchers, not hacks. It may be that they already know there's a problem, although we haven't seen any sort of retraction or explanatory note anywhere. At some point, I imagine we send a polite note to them, explaining what we found, although for now we'd like to try to fix the argument (and prove our extension!) ourselves. It seemed like it must be a common enough situation -- in the past I've found major and even unfixable bugs in papers -- that people might have an opinion on how to best handle the problem.

Monday, September 10, 2007

The Hiring Problem and Lake Wobegon Strategies

Continuing the "and now a word from our sponsors" riff, I'll describe a paper (to appear at SODA) that's joint with several people at Yahoo! Research, and started on a visit there.

We're looking at a situation similar to the well-known "secretary problem". For those unaware of the secretary problem, it goes like this: you need to hire a new secretary. There are n applicants, and you will interview them in a random order. The result of each interview is the relative rank of the applicant against those you have already interviewed. ("This applicant was the 3rd best so far.") After each interview, you have to decide whether to hire that applicant before the next interview; once you pass on an applicant, they're gone. Your goal is to maximize the probability that you hire the best of the n applicants. What's your optimal strategy? (I won't give away the answer for those who haven't seen the problem; it's easily found online.)

In our setting, we are considering growth strategies for a small startup company. Each applicant has a quality score, which we take to be uniform on [0,1], that we learn in the course of the interview. Unlike the secretary problem setting, we want more than one employee, although there is not a fixed number of employees we are aiming for. We simply want to grow, balancing the tradeoff between the speed of growth and the quality of new employees.

In the paper, we consider the strategies where we choose to hire an applicant only if their quality score is above the average of the current employees. (We study both the mean average and the median average.) We call these strategies Lake Wobegon strategies, after the fictional town of Lake Wobegon, where

all the women are strong, all the men are good looking, and all the children are above average.
Here, everyone we hire is above average (at least when we hire them). Google claims to use this strategy.

I should hasten to emphasize that (despite the Google claim) we feel that the hiring problem is about hiring employees just as much as the secretary problem is about hiring a secretary: very little. Rather, it's an abstraction, leading to problems about random processes and decision-making in the context of incomplete information. I've given the talk about this work a few times, and some people get hung up on setting it up as an optimization problem and determining the optimal strategy. You could, I suppose, but you'd have to be precise about the tradeoff about growth speed vs. quality, and the abstraction is already removed quite a bit from reality. I personally think it's simply interesting to consider how growth processes like this work under Lake Wobegon strategies; does anyone know of any related examples in nature?

If you're a puzzle person, then you might consider the following: suppose we start with a single person, of quality 1/2, and then interview until we hire n people. Which strategy will lead to higher average quality -- hiring above the median, or hiring above the mean? (Or are they asymptotically the same?)

The hiring problem leads to a great deal of curious mathematical fun : lognormal distributions, the Berry-Esseen inequality, the difference between hiring above the median and hiring above the mean (yes, they're very different!), and potentially lots of open problems and further variations to look at. Hopefully, the problem will become at least a fraction as popular as the secretary problem has.

I'm not sure why people at Yahoo were interested in this. In this case, I think they too got caught up in the mathematics of the problem. I'm glad that in the research labs, people still just follow their curiosity from time to time, even if the immediate application isn't obvious.

Sunday, September 09, 2007

Thursday, September 06, 2007

Negative Dependence

I lost sleep last night trying to prove a collection of random variables were negatively associated.

Negative dependence is one of those nice tricks that hardly ever gets used because it usually ends up being harder than it should be. While there are many flavors of negative dependence, the most natural is probably "negative assocation". The intuition is simple -- given a collection of random variables, if when one goes up that means the others should go down, then they are negatively associated. More formally, given any monotone non-decreasing function f of a subset of the variables, and a monotone non-decreasing function g of another disjoint subset of the variables, if f goes up, g should go down. Proving this holds formally is often more difficult than one would expect.

Why should we care? Well, it turns out that if a collection of random variables are negatively associated, then even though they are dependent, you can just apply your standard Chernoff bounds to them, without a care. Chernoff bounds (and other tail probability bounds) pop up in many arguments, but they can be very difficult to deal with when the random variables are dependent. Usually, you have to switch to a martingale argument, since standard Chernoff bounds apply only to independent random variables. If you can get negative dependence, it's much cleaner.

The best introduction to negative dependence is probably this surveyish article by Dubhashi and Ranjan. The focus is on how balls and bins problems are a natural example of negative dependence -- if a ball lands in one bin, it can't be in any other! Naturally, this explains my interest.

For example, the following problem came up for me some years ago in this paper. Suppose we thrown n points uniformly at random on the boundary of the unit circle. We want bounds on the number of arcs of length larger than say c/n for some constant c. If arc lengths were independent, we could just apply a Chernoff bound, easy enough. But of course they're dependent -- the sum of the arc lengths is 1! Intuitively, though, if one arc gets longer, then the others must get shorter, so there should be negative dependence. We proved what we needed to get the Chernoff bound, but it wasn't pretty. (I've since seen that a stronger version of this result is given as an exercise on negative association in the very nice-looking draft monograph by Dubhashi and Panconesi; to tell the truth, I'd like to see it worked out, as it seems to me that the conditioning is a bit subtle, but then again, geometry confuses me.)

In fact, in that paper we actually wanted a similar result in the following setting. Suppose one throws n points uniformly at random into a fixed region (say, for example, the unit square, or to avoid boundary issues, the 2-d unit torus). We want bounds on the number of Voronoi cells of size larger than say c/n for some constant c. If Voronoi cell sizes were independent, we could just apply a Chernoff bound, easy enough. But of course they're dependent! Intuitively, though, if one cell gets bigger, then the others must get smaller, so there should be negative dependence. Or maybe that isn't the case. Now I can't remember if I ever found an example that led me to believe it wasn't the case... Anyhow, we couldn't prove negative dependence easily, so we ended up using an uglier martingale argument that sufficed.

I was surprised at the time that I couldn't find any reference to type of this problem in the geometric literature. If negative dependence of Voronoi regions in random settings is still open (and true!), I'd be happy to ponder it with anyone who has a better sense of geometry than I do. In general, the area of negative dependence seems like a promising area for additional results.

Monday, September 03, 2007

The Argument for a Tuition-Free Harvard Education

After being subjected to the uncompelling arguments of those who think my videotaped lectures should be freely available, I thought I'd present my own wacky idea, backed up by an actual argument: that Harvard should stop charging tuition for undergraduates.

Strangely, this idea (which hit me back in '99, when I came back to Harvard, and which at least one Dean told me was unrealistic) does not seem so wacky today. Harvard has devoted significant new resources to financial aid over the last decade, so college is essentially free for families earning less than $60,000, as outlined here and here.

While some would view this in the mystical light of commitment to the educational mission, social good, etc., I'll be a bit more cynical and actually try to back up why this has been a good idea with an economic argument. More financial aid is just good business. Harvard's cost was limiting its access to the talent pool of graduating seniors; moreover, the resulting debt was at least a potential and probably real barrier to the future success of many graduates. Since Harvard's greatest asset (after its remarkably talented, and modest, faculty, and maybe also its endowment) is its reputation, losing top students because of cost or limiting their success through debt simply cannot be Harvard's optimal strategy. Increasing financial aid just makes good sense, especially given Harvard's resources -- it can take the short-term cost for the long-term good. (The fact that all this coincides with altruism is certainly fortunate, as naturally pretty much all the faculty really do have a mystical commitment to the educational mission, social good, etc.)

This argument, however, doesn't justify making Harvard free for all accepted, as I have proposed. In fact, one might think the other way -- that the rich should be soaked for as much as they can to help pay for the not-rich. My cynical but rational argument for a free Harvard undergraduate education for all is that, if tuition was free, but Harvard then encouraged people to donate what they thought their education was worth -- say, perhaps, a small percentage of their annual income for life -- in the long run, they'd more than make up the tuition loss with increased funding of the endowment (thanks to the power law that is the wealth distribution). This is not a tax, but it is based on the idea that your college education is related to your future earnings, and giving back a percentage of those earnings is an arguably fair way to pay for that education.

Harvard might not even have to wait for the long-term to get the benefit. Indeed, imagine Harvard's next fund-raising campaign beginning with the announcement that after the campaign, as long as their goals were met, Harvard would be free for all undergraduates! What PR! What kind of donations would that bring in immediately!

Longer term, I would suspect the benefit would be even more. The pay-what-you-think-is-fair approach has been tried in some restaurants (see the SAME cafe, or the One World Cafe), and many museums have no fee but "suggested donations" at least part of the time, so this approach is not entirely unprecedented. In Harvard's case, I think the mix of guilt, altruism, and competition would push wealthy alumni (and wealthy parents of students) to give much more. (So you see, I am soaking the rich -- I just think you should wait to soak people until after they are rich, and inspire them to give generously, rather than bill them for a tuition payment.)

There are all sorts of possible side-benefits. It could work out that by moving from a system of tuition to voluntary donations, there would be an immediate jump because the donations, as opposed to tuition, could be made with pre-tax instead of post-tax money. (Note: I am not a tax attorney...) Students not laden with debt may prove more entrepreneurial (which besides helping the economy might lead to bigger donations down the line), or perhaps might take on more public-service oriented employment.

I can see why this might not have been tried elsewhere -- there's a lot of up-front cost while waiting for future payoff. Even for Harvard, perhaps the risk of too many free-riders is too large, although I doubt it. Harvard could also label the plan an experiment, suggesting that after some time tuition would have to be re-instituted if donations didn't keep pace with projections, to limit the risk. Perhaps the biggest negative is if Harvard tried this unilaterally, it would be seen as an unfriendly neighbor to all the other colleges. Still, I can't help but wish this idea would be given a try. Perhaps it could change the way we talk about funding education in this country, moving increased resources to our education system. I'd like to see Harvard lead the way in this regard.

Friday, August 31, 2007

New Results in Trace Reconstruction

I've already talked a lot in this blog about deletion channels. Trace reconstruction involves a similar problem. We start with an original binary string X = X1,X2,...,Xn. A trace consists of a string Y1,Y2,...,Ym obtained from the original string by passing it through a deletion channel, where each bit is independently deleted with probability p. The trace reconstruction problem basically asks how many independent traces do you need to see to reconstruct the original string X with high probability. Unlike the coding setting, where X might be chosen from a codebook of our own design, in this setting two natural models to study are when X is uniform over binary strings (so the high probability is over the choice of X and the traces), and in the worst case (where the high probability is just over the traces). Variations of the problem include operations other than deletions (including, say, insertions and errors). As an example application, a set of sensors might be monitoring a sequence of events. Each individual sensor is weak and might miss a given event, in which case the question is how many sensors are needed to reconstruct the event sequence perfectly, with high probability.

Trace reconstruction has some history in the information theory community, and the first CS-style paper I saw on it was by Batu, Kannan, Khanna, and McGregor in SODA 2004. The main result of this paper dealt with random input X and considered p values that were O(1/log n). It seems to me much more natural for p to be constant, and it has remained an open problem to determine an efficient algorithm for constant p.

I mentioned this problem last time I visited Microsoft, and it seemed to resonate with some of the people there. Thomas Holenstein, Rina Panigrahy, Udi Wieder and I have a submission with several results, including an algorithm that for random X and sufficiently small constant probability p requires only a polynomial number of traces and polynomial time (with high probability).

The SODA 2004 uses a majority voting technique -- the bits are determined sequentially, with each string voting on the next bit. A key idea in our new algorithm is a "smart voting" technique. We only let traces vote if there is good reason (based on the already determined bits) to think that the trace has a good prediction for the subsequent bit. That is, only well-informed strings are allowed to vote. Feel free to make your own political analogies. My intuition is that this smart voting technique is a closer analogue to the full belief propagation (or Bayesian analysis) that we want to do than just majority voting. Because of this, I hope this "smart voting" technique is a general approach that will find other applications.

I don't yet have an analysis of a belief-propagation-based algorithm. Also, currently we can't analyze a maximum-likelihood algorithm, that finds the most likely original string X. I also don't know how to implement maximum-likelihood efficiently in this setting. So there's still plenty of open questions in this area.

Wednesday, August 29, 2007

How Mathematicians View Computer Science?

Luca Trevisan points to an article in the AMS by Neal Koblitz on modern cryptography that I think everyone in theoretical computer science (TCS) should read, as it exposes how at least some mathematicians view the culture in TCS. In summary, it's very negative. While I think the article is flawed on many levels, I'd argue that we ought to consider it as constructive criticism, and think about what, if anything, we might learn from it.

For example, one statement I found fairly misguided is the following:
Math departments usually believe the
Conjecture. For the development of mathematics it is better for someone to publish one excellent paper in n years than n nearly worthless papers in one year.
In certain other fields of science - including, unfortunately, computer science and cryptography - the analogous conjecture, while most likely true, is not widely believed.
I accept the constructive criticism that in computer science we perhaps publish too quickly, and too many incremental things. On the other hand, this conjecture has little to nothing to do with reality. For every Wiles, who spent essentially a decade on what is a very important result, there are probably 100 mathematicians who spent a decade on the problem getting essentially nowhere and publishing what in retrospect are worthless papers. And the implication that TCS is producing only a stream of worthless papers is fundamentally incorrect. The question is really whether the culture should be that a person works only on big problems with the goal of having a very small number of big results (say, 1) over their lifetime, or that a person helps the community make progress through smaller and quicker increments (as well as the occasional larger contribution). Given the important tie between TCS and real-world applications, there's a clear reason why the community has developed with a larger focus on small/quick progress, although as a community we are also supportive of people who want to work the other way as well. The phrasing of the conjecture is clever, but I actually think TCS progresses much better with the culture it has than the one Koblitz favors. (Just like sometimes fast local heuristics are much better than slow exact algorithms.)

Rather than just start a tirade against Koblitz, however, I think we'd be best off dissecting the article and understanding what aspects of the TCS culture has led to his opinions and, in many cases, misperceptions. We may find some things worth changing, either to improve our culture, or at least to present ourselves differently to other sciences.

Tuesday, August 28, 2007

And Now, a Word From Our Sponsors...

I've just returned from a week in the Bay Area, primarily to visit my "corporate sponsors"; Cisco and Yahoo have both provided research money this year, and I felt I owed them a visit before classes start. I also visited Microsoft Silicon Valley; even though I still haven't figured out how to get research money out of Microsoft, I've "consulted" there from time to time, and recently co-wrote a paper with several people there after my last visit.

The main purpose of the visit was to talk to people and try to come up with new things to work on. Corporate money seems to synchronize with annual budgets. If you want another check next year, you need to convince them that funding you is still worthwhile. (That's not unusual; I understand if I ever get a DoD-based grant, it will be similar.) I should point out that all research money I've gotten from Cisco and Yahoo is given as a gift -- no requirements (and much less in overhead taken by Harvard!). It's just that it's nice to get these gifts annually, like a research anniversary present, and that means maintaining the relationship.

I like to think that getting corporate money is a simple winning proposition. I get access to interesting problems; I get to work with talented people; and I get research money for doing what I would be doing anyway. But perhaps I'm deluding myself? Perhaps I'd be working on other grander problems if my agenda wasn't influenced by the vision of others? In my own personal case, I really doubt it, and it feels like a pure jackpot to me, but it's something every researcher probably has to think about.

I'd certainly advise that people interested in "practical algorithms" and "algorithm engineering" should seek collaborations with (and funding from!) such industrial sources. In my experience, it takes some work. (But then again, so does writing NSF grants.) Usually the funding comes after a successful collaboration, not before, or there has to be a clear champion in the organization who can make the case that your work is related to something going on at the company. Building such relationships takes time, and doesn't happen overnight. But it's very worthwhile.

To provide evidence, I'll spend some upcoming posts discussing problems I've recently collaborated on with people at Cisco, Microsoft, and Yahoo.

Friday, August 24, 2007

Advertising: Anyone Can Take My Randomized Algorithm Class

Next semester, I'm teaching my class on randomized algorithms and probabilistic analysis, based on the Mitzenmacher/Upfal book. Harvard, like many universities, has an "Extension School", and I offer my courses through the distance education program. Basically, my lectures get taped and put online, I put the assignments online, and you or anyone who pays the Extension fee can take the course. While I'm sure my teaching performance on video is reminiscent of say an early Mel Gibson or perhaps a Moe Howard, I personally still don't think distance education is as good as "being there" by any means (at least, not yet...). But it offers an opportunity that people may not otherwise have.

The course is taught at the level of an introductory graduate class, meant for non-theorists as well as theorists. These days, who doesn't need to know randomized algorithms and probabilistic analysis? If you know someone, for example in industry, who might like to take such a course, here's the link to the bare-bones syllabus.

Wednesday, August 22, 2007

Another Deletion Code Open Problem

In a binary symmetric error channel, n bits are sent, and the channel flips each bit independently with probability p. So, for example, the message sent might be 00110011 and the received message could be 01100011 if the 2nd and 4th bits were flipped. Now suppose the same message is sent through k independent channels, and the receiver sees all of results. (Here k should be thought of as a small constant.) The capacity of this channel can be computed; essentially, in this channel, each bit gets maps to a number in the range [0,k], corresponding to the number of 1's in the appropriate position. (Since all errors are independent, exactly which channels flip a specific bit doesn't matter, just the number of flips matter.) As a specific example, when k = 2, we can think in the following nice way -- if we see two 1's (resp 0's) in bit position i, we think the original bit was 1 (resp 0), and now we have an error with probability p^2. With probability 2p(1-p), we see a 1 and a 0 in the ith position -- this corresponds to an "erasure", since the bit is now equally likely to be a 1 and a 0. So we have a channel that gives errors with probability p^2 and erasures with probability 2p(1-p); we can find the capacity (and codes for) such a channel.

In a binary deletion channel, n bits are sent, and the channel deletes each bit independently with probability p. So, for example, the message sent might be 00110011 and the received message could be 010011 if the 2nd and 4th bits were deleted. Now suppose the same message is sent through k independent binary deletion channels, and the receiver sees all of results. Can we say anything useful here? The problem is automatically more challenging since we only have bounds and don't even know the capacity of the standard deletion channel (when k is 1). This is yet another simply stated question from the theory of coding for deletion channels in need of an idea.

Monday, August 20, 2007

FOCS Registration Open

Registration has opened for FOCS 2007, which will take place in Providence on October 20-23.

Please go to http://focs2007.org/

Note that the early registration deadline is September 20, and the deadline for reserving a room at the hotel at the conference rate is also September 20. (The hotel's regular rate is much higher.)

The Knuth Prize lecture will be given by Nancy Lynch on October 21.

A program of tutorials takes place on October 20, the Saturday before the regular conference program begins. The tutorial talks are as follows:

Terrence Tao : Combinatorial Number Theory
Dan Boneh : Recent Developments in Cryptography
Daniel Spielman : Theory and Applications of Graph Spectra

Abstracts for the tutorials should be available soon.

Thursday, August 16, 2007

HotTheory Workshop?

This year marked the 11th HotOS workshop. From the call for papers:
We request submissions of position papers that propose new directions of research, advocate nontraditional approaches to old (or new) ideas, or generate insightful discussion... As a venue for exploring new ideas, HotOS encourages contributions influenced by other fields such as hardware design, networking, economics, social organizations, biological systems, and the impact of compiler developments on systems and vice versa. We particularly look for position papers containing highly original ideas.
Submissions were just due for the sixth HotNets workshop. Here is the HotNets mission statement:
The Workshop on Hot Topics in Networks (HotNets) was created in 2002 to discuss early-stage, creative networking research and to debate positions that reflect on the research direction and needs of the broad networking community. Architecture, high-level design work, and positions that may shape long-term research direction are especially welcome. HotNets is structured to work in synergy with conferences such as SIGCOMM by providing a venue in which innovative work may receive feedback to help it mature into conference papers or otherwise have a long-term impact on the community. To fulfill these goals HotNets calls for short position papers that argue a thoughtful point-of-view rather than full-length conference papers, and maintains a broad and diverse scope.
Does theory need a Hot Workshop? A workshop specifically designed for somewhat wacky or not-fully-baked ideas that may turn into long-range research directions?

Wednesday, August 15, 2007

Some Theory-Related SIGCOMM Papers

SIGCOMM (the major networking conference) will be taking place shortly. Although I won't be attending, I thought I'd mention some of the papers that involve theory in a non-trivial way. This list is not meant to be exhaustive, so I apologize for (and welcome comments on) anything I might have missed.

The networking community, I've found, is very amenable to theory. I think there's a real understanding in the community that obtaining systematic improvements in something as wild and large as modern networks requires a solid, fundamental grasp of what's going on. This means good models, and good algorithms and data structures. This doesn't mean that SIGCOMM is full of theory papers; they generally want to see some sort of implementation to see that whatever idea is presented actually works. But many papers have a non-trivial theoretical component, and the SIGCOMM conference is certainly a good place to look for important problems where theoretical insight would be welcome. (The same is true for the larger networking conference, INFOCOM, but that conference is so large it's harder to get a handle on. Also, SIGCOMM aims to be a bit more visionary, or "out there", which I think means there's more opportunity for theory to get involved.)

DTN Routing as a Resource Allocation Problem: DTN's are Disruption Tolerant Networks -- in this paper, focusing on mobile nodes that are only connected intermittently. In one section, the paper sets up an appropriate graph model for the problem, and proves lower bounds for various situations. For example, any algorithm that doesn't know the schedule of node meetings is Omega(n)-competitive compared to an offline adversary when n packets are to be delivered. The paper then moves on to heuristic approaches and an experimental evaluation.

Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies: The paper considers the problem of how to generate realistic Internet graphs, where here the relevant graph is a router graph with nodes labeled to give the corresponding AS (Autonomous System) network.

An Axiomatic Basis for Communication: Pretty much like it sounds. Trying to set up a basic logic for network protocols, covering issues like naming, binding, forwarding, etc.

Embracing Wireless Interference: Analog Network Coding: Normally, we think of networking coding as XORing packets, or taking random combinations of packet data over some finite field. In wireless, you may be sending signals, not bits. What do you do then? This paper looks at the problem of effective algorithms for this problem.

Again, these examples aren't exhaustive; many other papers have Lemmas and Theorems in there. In fact, I'd wager that having words like "Lemma" and "Theorem" in the paper is positively correlated with acceptance to SIGCOMM. Maybe someone on the PC will confirm or straighten me out. In any case, I'll be giving all the SIGCOMM papers a closer look....

Tuesday, August 14, 2007

Blog Comment Feed

One thing I've been enjoying is that as people seem to discover this blog, they comment on the older posts. I appreciate these comments and I hope the newcomers stick around!

Suresh asked me to enable the comment feed, which would allow people to easily see these newly arrived comments. They appear to be enabled, but while there is a link for the standard blog feed at the bottom of the page is a link for the blog feed, there is no link for the comments. I spent some time playing with the template to no avail. (I'm happy to take advice from anyone who could get the link to show up.)

However, you can just enter the URL directly to your reader. Apparently, the URL you need to get the comments is:

http://mybiasedcoin.blogspot.com/feeds/comments/default

and the regular feed for the blog is

http://mybiasedcoin.blogspot.com/feeds/posts/default

Monday, August 13, 2007

Teaching Heuristics in an Algorithms Class

In my undergraduate class, I devote one class (and one programming assignment) to heuristic search methods. I focus on hill climbing, since it is most clearly connected to other things covered previously (greedy algorithms, the simplex algorithm), but I also discuss other well-known methods, including the Metropolis algorithm, simulated annealing, tabu search, go with the winners, genetic algorithms, and, of course, BubbleSearch.

Generally, algorithms textbooks hardly mention heuristics. At best, heuristics enter the picture when discussing approximation algorithms, as though the fact that we can prove that the greedy local search algorithm for max-cut achieves a cut of at least 1/2 the edges is the important thing. I wish the standard textbooks would devote a solid chapter on heuristic techniques; in real life, most students are probably more likely to have to implement a heuristic for some NP-hard problem than to have to implement a minimum spanning tree algorithm.

The theory purists will undoubtedly suggest that heuristics don't belong in an algorithms class, because generally we can't prove formal statements about them. Obviously, I disagree. Heuristics are closely tied to other class concepts -- like greedy algorithms and approximations. Perhaps most importantly, a successful heuristic approach depends on sound modeling and building an understanding of a problem, which are exactly the important skills we should be teaching in undergraduate algorithms. Finally, we need to give students some basic, realistic algorithmic tools for handling NP-hard problems in practice. (2-approximations do not suffice.) So while I acknowledge that students may be exposed further to these and other heuristic approaches in for example an AI class, I think it's important to clearly connect it to what they're learning in algorithms.

Friday, August 10, 2007

BubbleSearch

I became more interested in (and knowledgeable about) heuristic methods when I was working on a related project at the nearby Mistubishi Electric Research Laboratory (MERL) some years ago. The project on Human-Guided Search studied the benefits of having a human dynamically interact with heuristic optimization algorithms, and along the way we did some work just on the heuristics themselves.

Here's a simple heuristic that can be taught, I think, quite easily and productively to undergraduates. Many hard problems -- including most scheduling, packing, and coloring problems -- have natural greedy heuristics, whereby the items are ordered according to some criterion (work, size, degree), and "placed" one at a time according to that ordering. For example, many standard bin packing algorithms such as first fit decreasing and best fit decreasing fit this type. Given time, a natural way to extend such greedy heuristics is to try additional orderings. While we can't hope to consider all orderings, we could certainly try more than one. Of course, intuition tells us we should prefer orderings close to the greedy ordering.

There are a variety of ways one could do this. A historically popular way is to sequentially choose an item uniformly at random from the top k of the greedy ordering, place it, and remove it from the list. One has to choose the parameter k. A negative feature of this approach is that there are many orderings that will never even be considered under this approach.

We suggest what we call BubbleSearch, which makes use of the Kendall-tau distance. More clearly, the Kendall-tau distance between an ordering A and the greedy ordering B is the number of transpositions of adjacent items you would have to make to get from A to B, which corresponds to the number of swaps you would make using BubbleSort if the sorted order was just the greedy ordering. (Hence the name.)

You could just go through all the permutations of items in order by Kendall-tau distance from the sorted order. Most small perturbations of the greedy ordering, however, give very similar results, leading to little or no improvement. A better way for most problems is a variation of the top k approach. To create a new ordering A, we start with a base ordering B (the greedy ordering). We pick the first item of A as follows: choose the first item of B with probability p, and if it isn't selected, choose the next item of B with probability p, and so on down the list (starting at the beginning again if necessary). Once an item is selected, it become the first element of A, and is removed from B. We continue choosing subsequent items for A the same way with the remaining list from B, starting from the beginning of the remaining list. The probability of obtaining an ordering A is then proportional to (1-p)^d(A,B). Here p is the algorithm parameter, determining how close to the base ordering you are likely to be. To me, this approach is much more intuitive than the top-k approach, and in our experiments appeared to do at least marginally better.

A further improvement is to change the base ordering to be the best ordering you have seen so far. Once you've beaten the greedy ordering, there's no reason to keep it as the base.

A motivation for simple heuristics like BubbleSearch is exactly their simplicity. They are easy to code and rely on essentially no problem-dependent knowledge. If coding time matters, something like BubbleSearch is the way to go.

Randomized extensions to greedy algorithms also give rise to interesting theoretical questions, related to work on "priority algorithms". I don't know of any results bounding the performance of random-top-k, BubbleSearch, or similar randomized greedy variations.

Wednesday, August 08, 2007

Death of a Research Laboratory

Most of you probably don't know about Mitsubishi Electric Research Laboratories (MERL), a small lab nestled in Kendall Square (very close to MIT, and a pleasant walk from Harvard). While they did basic research there, it was definitely more application/development oriented, and it specialized more in areas like UI, graphics, speech, etc. Information theorists would know it as the home of Jonathan Yedidia, a big name in coding and belief propagation, but CS theorists might not ever have heard of it.

I've done some consulting work there over the years. I knew the lab director, Joe Marks, from my time as a Harvard undergrad, and he hooked me up. It was a very nice place -- very theory-friendly in its application-oriented way. Joe clearly had the mindset that the goal of the lab was to generate new ideas, and that would drive new products.

So I was disappointed to hear several months ago that Joe had been removed as lab leader. (Don't feel too bad for Joe -- he's now at Disney, and is chairing SIGGRAPH this week. A talent like him will continue to be successful...) And even more disappointed (but not surprised) to read in Xconomy that MERL was being "re-organized", essentially phasing out the basic research component, and many people were leaving.

I've lived vicariously through this before -- I left Digital Systems Research Center before it disappeared (after Digital was bought by Compaq was bought by HP), but knew several people who went through the process. It's very disturbing to see again how hard it is for companies to make research labs work.

What makes research labs successful? Can they really last long-term in any non-monopoly environment? Let me make a bold prediction. I personally am not planning on retiring until at least age 65. Pick any research division that's around today. (Microsoft, Yahoo, Google, AT&T, Bell Labs, IBM, any of them...) I'd bet on pretty much any of them that their research wing will be gone before I hit 60. (I'm still under 40. OK, maybe I should just bet they'll be dramatically reduced or transformed into Advanced Development for a number of years somewhere along the way...) This is something people who go to research labs should know going in. Odds are likely you'll have to change jobs somewhere along the way -- not because of your own talents, but because of company-level problems. This might make such jobs seem risky, but let's not exaggerate -- when the company has problems, the talent moves to a new company.

I'd love to hear thoughts on what makes good research labs, why I'm wrong about research labs dying out, how people who have experienced such moves feel about them, or anything else on the topic.

Update : Jonathan Yedidia says in the comments that the reports of MERL's death have been highly exaggerated.

Tuesday, August 07, 2007

Further items from the DIMACS workshop

Peter Winzer argued for using (variants of) Valiant's randomized load balancing (route to a random intermediate spot, and go from there to the end destination) as an actual network architecture, over shortest-path and virtual private network methods. And I do mean argued. A heated discussion broke out among various real networking people as to whether this was realistic. The cost of potentially doubling the transport time (speed-of-light time) for say cross-country transmissions was argued to be unacceptable, even if the payoff was essentially zeroing queueing delays and making a simpler, cheaper (less equipment) network. (Perhaps it could be used for smaller networks, or only to/from the center, to avoid doubling cross-country trips.) It was very entertaining and instructive; one of the classis theoretical ideas, an argument about how it could be used and what its benefit could be, and a counterargument based on practical experience, leaving a somewhat vague end result -- you probably can't tell how useful it is until you build it out...

Cristian Estan gave an excellent talk giving an overview of data plane algorithms -- hardware router algorithms for longest matching prefix, string/regexp matching, packet classification/deep packet inspection, etc.

Ho and Sprintson gave their survey on network coding, covering the background, the integrality gap of network coding for undirected networks (Agarwal and Charikar), finding network codes through integer programming for undirected networks, bounds on the number of encoding nodes needed for various graphs, robust network coding in the face of edge failures, practical implementations, and more.

DIMACS slides

My DIMACS slides are now available on my Talks page.

Monday, August 06, 2007

Network Coding, Open Problems

I'm spending a couple of days at the DIMACS Tutorial on Algorithms for Next Generation Networks. Tracey Ho and Alex Sprintson and giving a talk on Network Coding, and since in the past I've promised a post on open questions in network coding, I'm interviewing them. I apologize that the questions might be vague; the problem with a new area is that it's still a little unclear what the right open problems are, and we all use different lingo. But here are a few...
  1. For 3 source-receiver pairs and unicast, in an undirected network, with arbitrary coding, is there an advantage from coding over routing?(I think the reference paper is Li and Li, Network Coding: The Case of Multiple Unicast Sessions)?
  2. General multiple unicast in directed networks: is there an algorithm that, given a network, computes the capacity? For acyclic networks, there's an implicit characterization, but not an explicit characterization; for cyclic networks, there's not even that.
  3. What is the complexity of finding the optimal (in terms of capacity) non-linear code for various network coding problems? Specific problems include determining the truth/falsehood of the following statements:
    1. Given an instance of the general network coding
      problem in a directed graph G and a real number
      r, there is a polynomial-time algorithm which
      computes a solution achieving rate r if one exists,
      and otherwise reports that this is impossible.
    2. Given an instance of the k-pairs communication
      problem in an undirected graph G and a real number
      r, it is recursively undecidable to determine
      whether the network coding rate is less than r.
  4. For multicast networks, what is the minimum number of nodes that need to do encoding to make network encoding work? That is, can we minimize the coding complexity in terms of the number of nodes doing coding (or some other reasonable metric).
  5. There must be open questions in the recent work by Koetter/Kschischang on coding for errors/erasures in random network coding. For example, they seem to give general (network-oblivious) bounds. Are there ways to improve their bounds by using knowledge of the network topology?
  6. Is there an algorithm to find the minimum cost subnetwork that guarantees delivery using network coding subject to certain classes of adversarial (or non-adversarial) link failures.
  7. A good place to look for CS-style open problems is probably also the Adler/Harvey/Jain/Kleinberg/Lehman paper On the Capacity of Information Networks, which has a nice section on open problems at the end.
Maybe I'll have more after the talk...

Friday, August 03, 2007

Book Reviews

For those of you who haven't succumbed to buying the
Mitzenmacher/Upfal textbook on Probability and Computing,
there are two very positive reviews that will appear in the next SIGACT newsletter. Here are the reviews, excerpted from the SIGACT book reviews page Bill Gasarch maintains.

Favorite tech policy/news blogs

I'm sure there are plenty of places to get such information, but for basic tech news (like what's up with Google and the FCC, voting machines, and the iPhone), I'm enjoying the Machinist blog, out of Salon.com. The longer weekly columns are interesting too; I'm already looking forward to getting a Zonbu.

For straight tech policy, my favorite for quite some time has been Ed Felten's Freedom to Tinker. The past week he's been commenting on the California e-voting reports, which gives further evidence to what most of us already know (or would have guessed) : current voting machines are fundamentally insecure. I prefer to think this is due to incompetence and ignorance rather than malicious intent on anyone's part, but what do I know. My only complaint is that he doesn't post enough!

Tuesday, July 31, 2007

The Reviewers' Pledges

The state of journal reviewing in CS and EE journals is generally pretty dismal. It often takes an unforgivably long time to get reviews back, and often reviews offer less in the way the feedback and constructive criticism than one might hope.

Here I'll focus on aspects related to timing. (I'm unconvinced that reviews that take longer to get back are any better in terms of feedback. Often, just the opposite -- the reviewer realizes the paper has been on their desk too long and just writes a quick paragraph to be done with it.) Let me suggest a set of basic pledges -- rules that everyone should follow. Feel free to suggest your own additions....
  1. When asked to review a paper, I will respond as quickly as possible, even if the answer is no.
  2. I will review at least 1 journal paper for every journal paper I submit. (This does not mean "I will give my graduate students 1 paper to review for every journal paper I submit." Though graduate students should also do reviewing...)
  3. I will skim through a paper I plan to review within one month of receiving it, so that if it is a clear reject for any reason, or there is an important question that needs to be raised, I can promptly write a short note to the editor (and thereby hopefully avoid a more detailed review).
  4. I pledge to review papers within six months of receiving them. I acknowledge that six months is an upper bound, not a target deadline.
  5. I accept that there is reviewing karma, and I should not be surprised if editors pass my papers on to slow reviewers if I am a slow reviewer.

Monday, July 30, 2007

A Book on the Energy Crisis

This post is dedicated to a researcher most CS people might not know about (although most information theorists probably do), David MacKay. I encourage you to go take a look at his web page.

David and I got to know of each other's work because we were both working on Low Density Parity Check codes around the same time. Since then, he's written one of the great textbooks on information theory. He's one of the key people behind the Dasher project, which provides text entry methods for the handicapped based on information theoretic principles. (Really. It's amazing what a well-thought out system based on arithmetic coding and a clever UI can do.)

And now he's finishing up a book on sustainable energy. The book is for laypeople, showing how to think in rough quantitative terms about how much energy is available, how much is being used, and what it all means. No matter what you think about the energy crisis, the book serves as an interesting example of how to try to encourage people to think quantitatively about policy-related issues. He's made a draft freely available. I encourage you to have a look.

Thursday, July 26, 2007

SODA vs. FOCS/STOC, full data

Over at the geomblog, Suresh and Piotr have taken my initial data-gathering on citations counts for the theory conferences to the extreme. They point out issues in gathering data (e.g., how does one handle summing conference/journal versions; sometimes the journal version has a different title!), consider the impact of short/long SODA papers, and call for help checking their results. Excellent work!

The implications, whatever they are, remain a point of future discussion.

Wednesday, July 25, 2007

Why Simple Hash Functions Work Well, Part II

In my last post, I described a problem that's bothered me for some time: why do simple hash functions work so well -- that is, as well as the analysis for truly random hash functions? The natural answer is that there is some sort of randomness in the data interacting with the randomness in how the hash function is chosen that combines to give these results. In our paper, Salil Vadhan and I try to give a solid foundation for this approach.

To prove things about this interaction, we need models. For hash functions, we naturally look primarily at 2-universal (or pairwise independent, or sometimes 4-wise independent) hash functions. Such families are well-studied in theory and have practical implementations.

To model the data, we assume that it comes from a block source. This means that each new data item, conditioned on the values of the previous items, still has some entropy to it. In other words, each new piece of data is at least somewhat unpredictable. It can depend on the previous data in essentially arbitrary ways; for example, it might be possible to narrow the possibilities for the next data item to a small range based on the past, or the distribution of what the next item will be could be highly skewed. But as long as there is still enough unpredictability, we are fine. This seems like a perfectly reasonable model for network or streaming data to me, although as far as I know the block source model has not been used in this context previously.

Once we have the model in place, in some sense, we're done. The Leftover Hash Lemma of Impagliazzo, Levin, and Luby essentially says that, if there's enough entropy in your block stream, you get a near-uniform output over the entire stream when using even just a 2-universal hash function. Our paper improves on and specializes this flavor of result for the setting we're looking at -- hashing items into tables -- and examines the implications for many applications.

Finally, I feel I have a clear and clean justification for why truly random analysis is suitable even if only simple hash functions will be used. I expect there's still more that one can do to improve this framework, and it raises a number of interesting open questions that lie at the intersection of algorithms, information theory, and networking. For more details, I refer you to the paper.

I'll leave off with an interesting open question. In the "power of two choices" (or Balanced Allocations) scenario, a sequence of n items is hashed into a table with n bins. Each item is hashed twice, with 2 different hash functions (more generally, hashed d times, with d different hash functions), with each hash giving a possible location for the item. The item is actually placed in the least loaded of the 2 choices (breaking ties arbitrarily). Now on a lookup one has to check 2 places for the item, but the load distribution is much more even. Specifically, the maximum number of items in a bucket with d choices is only log log n/log d + O(1), instead of (1 +o(1)) log n/ log log n one gets from one choice. (You might check out this somewhat outdated survey if you're not familiar with the problem.)

As far as I know, we don't have a worst-case analysis (that is, as opposed to our paper, with no assumptions on the input data) for say pairwise-independent or even k-wise independent (for some constant k) hash functions, for some constant number of hash functions d. This has been open for some time.

Monday, July 23, 2007

Why Simple Hash Functions Work Well

On my publications page there is a recently finished new paper I'm quite excited about. Part of that excitement is because it's (finally!) my first paper with my remarkable colleague Salil Vadhan. The rest is because I think it answers a question that's been bothering me for nearly a decade.

A fair bit of my research has been on hashing, and often I end up doing simulations or experiments to check or demonstrate my results. For many analyses of hashing processes -- including Bloom filters or the power of two choices, we (or at least I) assume the hash function is truly random -- that is, each element is independently mapped to a uniform location by the hash function. This greatly helps in the analysis. Such an assumption is downright painful to strict theorists (like Salil, who has questioned me about this for years), who rightly point out that hash functions being used are not anything close to truly random, and in fact truly random functions would be far too expensive in terms of space to even write down in practice.

Of course theorists have developed ways to deal with this -- with the seminal work being Carter and Wegman's introduction of universal hashing. The key idea is that you choose a hash function at random from a small family of hash functions that are easy to compute and require little space to express, and this choice guarantees some random property, even it is is not as strong as choosing a truly random hash function. For example, the basic universal hash function families guarantee that for any elements x and y in the universe, if you choose a hash function uniformly from the family, then the probability that x and y land in the same bucket is 1/#of buckets. That is, the collision probability of any specific pair is what it should be. Once you consider 3 elements at the same time, however, the probability that all 3 land in the same bucket need not be (1/# of buckets)^2, as it would be for a truly random hash function.

The most used variation is probably k-wise independent hash families, which have the property that when a hash function is chosen from that family, any collection of k elements are independently and uniformly distributed.

A negative with using these weakened hash families is that usually, naturally, you get weaker results from the analysis than you would using truly random hash functions. A fine example of this is the recent work by Pagh, Pagh, and Ruzic on Linear Probing with Constant Independence. With truly random hash functions, linear probing takes expected search time O(1/(1-alpha)) where alpha is the load on the hash tale. They show that using pairwise (2-wise) independence linear probing can take time O(log n) on average -- it no longer depends on the load. Using 5-wise independence they get expected time polynomial in 1/(1-alpha). That's a great result, although there's still a gap from truly random.

The real problem though, is the following: pretty much whenever you do an experiment on real data, even if you use a weak hash function (like a pairwise independent hash function, or even just some bits from MD5), you get results that match the truly random analysis. I've found this time and time again in my experiments, and it's been noted by other for decades. That's part of the reason why when I do analysis, I don't mind doing the truly random analysis. However, it leaves a nagging question. What's going on?

The obvious answer is that there is also randomness in the data. For example, if your data items were chosen uniformly from the universe, then all you would need from your hash function is that it partitioned the universe (roughly) equally into buckets. Such a broad assumption allows us to return to the truly random analysis. Unfortunately, it's also amazingly unrealistic. Data is more complicated than that. If theorists don't like the idea of assuming truly random hash functions, you can imagine practitioners don't like the idea of assuming truly random data!

For years I've wanted an explanation, especially when I get a paper review back that questions the truly random analysis on these grounds. Now I think I have one. Using the framework of randomness extraction, we can analyze the "combination" of the randomness from choosing the hash function and the randomness in the data. It turns out that even with just pairwise independent hash functions, you only need a small amount of randomness in your data, and the results will appear uniform. The resulting general framework applies to all of the above applications -- Bloom filters, multiple-choice hashing, linear probing -- and many others.

In the next post, I'll give a few more details.


Friday, July 20, 2007

Citation Counts for Tenure

The discussion on citation counts reminded me of the related question of how much of a role this sort of data should play in tenure decisions.

In the world of extremes, one could imagine tenure decisions being based solely on letters without really looking at citation data. A motivation for this approach would be that letters give you a richer picture of how a person is viewed by their peers in the research community, what their work has been about, and what the potential impact of this work will be in the future. On the other hand, the system can be gamed, by making sure positively inclined people get chosen to write letters. (The person up for tenure might not exactly be able to game the system themselves, but certainly a friendly department chair could...) I have to admit, the letter-based approach feels rather "old-boy network" to me, which leaves me a bit uncomfortable.

As another extreme, one could imagine tenure decisions being based solely on numerical data gathered from Google scholar or other sources. A motivation for this approach would be that the numbers supposedly give you an unbiased picture of the impact of a researcher's work, allowing comparisons with other comparable researchers. The data could also be used to gauge the derivative -- how one's work is changing and growing in impact over time. On the other hand, the system can be gamed, by developing groups who purposefully cite each other whenever possible or by working on projects that give better numbers without really giving high impact. I have to admit, I like the numbers, and in some respects I trust them more than letters, but I still don't entirely trust them, either.

My limited experience with promotion decisions is that it makes sense to gather both types of data and make sure they are consistent. When they are not consistent, then the departmental arguments can begin. When asked to write letters, I know I look at the citation data, and would include it in the letter if I felt it was appropriate.

Tuesday, July 17, 2007

The Old SODA vs. FOCS/STOC Debate

With the SODA deadline just past, and FOCS coming up nearby at Brown, I got to thinking about bringing up the old SODA vs. FOCS/STOC debate. For those new to the subject, FOCS (Symposium on Foundations of Computer Science) and STOC (Symposium on the Theory of Computing) are generally considered the top two conferences each year in theoretical computer science. SODA (Symposium on Discrete Algorithms) is considered by many (including myself) to be better suited for algorithmic results, and many have argued that the big two theory conferences should really be the big three.

Now, being a quantitative sort of person, I decided the best way to bring something new to the discussion would be to gather some data. So I picked a non-random year -- 2000 -- and decided to look at the citation counts on Google Scholar for all of the papers from the conferences and compare. I figured 2000 was far enough back that we'd get meaningful citation counts for comparison. Yes, I know, citations counts are not the end-all and be-all and all-that, but that's an argument for a different day (or for the comment section). In aggregate, they must tell us something important.

You can imagine my surprise when I looked at the numbers and found SODA completely dominated. Here's a little chart:


Papers Median Cites Max.Cites Total Cites
FOCS 66 38 318 3551
STOC 85 21 459 3393
SODA 122 14 187 2578

FOCS seems to have had an absurdly good year, but the data speaks volumes. At least as of 2000, the best results went overwhelmingly to FOCS and STOC. Overall, I found the results of this experiment rather disappointing for SODA.

It would be nice to check to see what the current trend is, but it was annoyingly time-consuming to do this by hand, and I didn't feel like writing a script. (There seem to be many exceptional cases; if you try to do an exact match on the title, you'll often not find the paper because the title has changed somewhere along the line or a typo or something. But with a regular query you often have to do some searching to find the paper. Perhaps someone more talented will be inspired to write a script?)

I learned something interesting and useful by gathering this data. As a community, should we be paying more attention to numbers like these, so we can make our conferences better? For example, I can't recall anyone ever trying to systematically answer whether a PC made good decisions or not after the fact, but apparently we now have the data available to try to answer such questions in an empirical fashion. (We might check if rejected papers were later accepted and highly cited, for example.) What possible lessons can we learn using these citation tools?

Monday, July 16, 2007

A Favorite Open Problem : Codes for a Poisson-repeat Channel

A (binary) Poisson-repeat channel works as follows: the sender sends a sequence of n bits, and the channel independently replaces each bit with a number of copies (or repeats) that has a discrete Poisson distribution with mean 1. That is, for each bit, the probability that it is replaced by k copies is e^{-1}/k!. Here k can be 0, in which case the bit is deleted. The receiver gets the resulting string after replacements. I'd like to find an efficient code for this channel that has a non-trivial constant rate. Any rate over 0.01 , for example, would be just fine. Of course, I'd like the bound on the rate to be provable, rather than just experimental, and I really would like the code to be practical, not just polynomial-time encodable/decodable.

What's the motivation? It turns out that the Poisson-repeat channel is closely tied to the deletion channel, where each bit is independently deleted with probability p. A code for the Poisson-repeat channel would immediately yield a good code for the deletion channel for values of p is close to 1; we showed the reduction in this paper.

Codes for insertion/deletion channels are hard; very little is known. Because a code for this specific channel would yield codes for a larger family of channels, I think it's an appropriate and intriguing target.

Friday, July 13, 2007

FIND Meeting

While at ISIT, I missed a FIND (Future Internet Directions) meeting. (You may have to register -- give your name -- to get access.) FIND is, as it says on their overview page, "a major new long-term initiative of the NSF NeTS research program. FIND invites the research community to consider what the requirements should be for a global network of 15 years from now, and how we could build such a network if we are not constrained by the current Internet -- if we could design it from scratch."

The page on the meeting is interesting in itself if you want to see what's going on with the FIND program (and maybe get ideas for future proposals). What is also interesting to me is this requirement of the program that PIs are supposed to get together at meetings roughly three times a year as part of the grant. This has not historically been how the NSF operates, though I hear it's common for DoD funding. I doubt the approach will necessarily spread to theory; it seems to me that it makes sense for FIND because it's such a highly targeted initiative, while theory grants cover a much more diffuse range of activities. But it may be that in the future we can expect more money being funneled into similar targeted initiatives -- with similar requirements.

Tuesday, July 10, 2007

How Much Does a Graduate Student Cost When Teaching?

Continuing my last question, what other support for graduate students (on the Ph.D. track) do you have? The main two I can think of are the following:
  1. Does the department provide funding for incoming graduate students for some period? For example, do all first years get funded by the department automatically? Are there requirements for this funding (such as they have to teach one semester)?
  2. What department support to students get if they take on a Teaching Assistant role during the semester? Does it cover tuition/stipend for the semester? If not, what fraction?
And there's still time to answer the previous question -- what's the annual cost of a graduate student (tuition+stipend+overhead).

Sunday, July 08, 2007

How Much Does a Graduate Student Cost?

What's a graduate student cost these days? That is, as a line item on an NSF grant, for a 12-month graduate student, tuition+stipend+overhead, what's a graduate student cost? (Please feel free to answer anonymously, as I'm sure this is the sort of information people are interested in but don't want to reveal by institution. And use whatever additional qualifiers are necessary. For consistency, let's say a 3rd year student.)

This question was motivated by a change made this last week in Harvard's policy regarding how graduate students were charged to grants. Previously, Harvard would pay the student the stipend and tuition money directly, and then pull tuition back out of the paycheck. With this setup, Harvard charged overhead on tuition, since it was treated the same as the student stipend. Apparently, a new federal guideline just came out prohibiting this sort of thing; tuition will now be pulled out of the grant directly, free of overhead.

I was quite pleased to hear this. I had been complaining about this practice for a number of years; as far as I know, overhead on tuition is not standard for most schools. It made Harvard graduate students non-trivially more expensive. This change makes graduate students funded by NSF grants much cheaper for me. Moreover, it also just seems to me to be the right way to do it.

Now that the change is happening, though, I'm somewhat concerned. All of a sudden the School of Engineering and Applied Sciences is probably out millions in overhead that it had already budgeted. Somewhere down the line, I'm sure I'll be paying for that out of my grants somehow.

Saturday, July 07, 2007

SODA deadline

Can someone tell the SODA-powers-that-be that it's really annoying to have a paper deadline on July 5th or 6th? (That's what it's been the last four years...) July 4th is a major US holiday, which if done properly involves a late night with fireworks.

I realize it's pointless to complain, but that's one reason why I started a blog -- so I could complain publicly. And I realize there are all sorts of arguments that it shouldn't matter what day they pick. But, of course, in practice, it does.

Friday, July 06, 2007

Thursday, July 05, 2007

More on Cyber-Enabled Discovery and Innovation

SIGACT chair Richard Ladner asked me to continue spreading the word about the Cyber-Enabled Discovery and Innovation (CDI) initiative from the NSF. In particular, he asked me to point to Sanjeev Arora's article in the last SIGACT News (which seem to require an ACM password) and an article in the last Notices of the American Mathematical Society.

You might wonder why this is something that I (and many others) are pushing so hard. I think it's because we've seen the writing on the wall. When you look at the available theory funding available from the Computing and Communication Foundations Division (and the Theoretical Foundations Cluster within), it's pretty small. This is odd and frustrating, as theory seems to be thriving quite healthily, and to continue building on our successes, we need adequate funding.

The good news is that theoretical research often does well with these cross-cutting programs. When the SIGACT committee looked at the numbers, we found that back in the days of ITR, theorists were getting substantially more (something like 2 times) as much funding from ITR grants as from Theoretical Foundations grants! We've also had a lot of success with Cybertrust. These other pools of money are funding a lot of theory research, because we've been diligent in applying.

Long-term, this is something that we as a community need to try to fix. The baseline funding for theory needs improvement, and we have to keep letting the NSF know why. But for the foreseeable future, we have to take advantage of these kinds of funding opportunities as they arise. And the best way to take advantage of the CDI opportunity is for lots of theorists to send in lots of great grants.

Monday, July 02, 2007

CCC and CDI in the CRA

Great stuff in the May Computing Research News. First, a Computing Community Consortium (CCC) piece by Bernat and Lazowska that everyone should read. Look at the prominent discussion of theory and the new CDI initiative!

1. Algorithms as a lens on the sciences: Beginning in the mid-1990s, several individual theorists became concerned about the field, where it was going, and how it was funded. There was considerable dissension, with the claims that the field was too inward-looking and too hung up on mathematical elegance as opposed to relevance. Events overtook discussion as theory became highly relevant to web-based applications, protocols, and other areas. Simultaneously, theory funding was dwindling so SIGACT set up a committee to look at these issues. It concluded that new directions that connected theory to other intellectually challenging areas would take funding pressure off the core (since folks have more sources to go to, leaving the core for folks who were uninterested in application areas). A workshop series on network computation led to NSF’s SING program, but SING had no money of its own and actually resulted in a decrease in theory funding. The SIGACT committee went back to work and developed the idea of algorithms as a lens on science. This idea went forward as a White Paper to appropriate folks within NSF. Eventually, after working its way through the internal NSF budget process, it resulted in a large new FY08 request—Cyber-Enabled Discovery and Innovation (a foundation-wide program beginning at $52 million in FY08 and intended to grow to $250 million in FY12).

This is an example of an idea begun by a few individuals, nurtured within a professional guild, supported by a federal agency, and turned into a major funded program—but not without a few bumps.

As part of that SIGACT committee, I think this is a good rough description of what we've been doing. Now that there's money going into the CDI program, theory people need to be sure to apply to get their share. Start thinking now, and there will be more on CDI in this blog coming up.

Also in the May issue is the Taulbee Survey. As far as I know, the primary use of the survey is for faculty to look up how much they should be paid. But there's other interesting data too!
The total Ph.D. production between July 2005 and June 2006 of 1,499 represents a phenomenal 26% increase.
And another nugget:

Actual Bachelor’s degree production in departments reporting this year was only 3.1% lower than the projection from last year’s reporting departments. From this year’s estimates, it would appear that another 16% decline is looming. If this holds true, it would represent a drop of more than 40% over a three-year period.

The news is much better when looking at new Bachelor’s degree students. For the first time in four years, the number of new undergraduate majors is slightly higher than the corresponding number last year.
I'm hoping they're right and that the number of new majors will start going up again...