The new California budget call for $650 million in cuts to the UC systems -- I understand $500 million had already been planned, they added $150 million on top of that, and may add more later if the revenue numbers don't pan out.
I'll admit that as a long-time CA resident (that's where I grew up), and a UC Berkeley alum (for grad school), it pains me to hear this. I'm very sympathetic to statements such as this one quoted in this San Francisco Chronicle piece:
"Some students don't even call the increases "tuition" anymore, but tax increases. They say state lawmakers are deceptive in claiming to have passed the budget without raising taxes."
I grew up in a California where we really believed we were a shining vanguard for the rest of the nation -- and the UC system was a very big part of that. By the time I left California I, at least, didn't have that feeling about the state any more. And these cuts, of course, are painful to hear.
I don't mean to make it sound like the UCs are dead -- they have too many brilliant faculty to count, and will continue to attract many top students. But it seems to me they are being weakened, perhaps (and I hope not) even crippled longer term. I hope that this is just a historical blip, and California's greatness -- including vibrant, powerful, and more healthy UC and CSU systems -- will be on full display the rest of the century.
Addendum:
Michael Goodrich (who I've had the pleasure of working with lately) has suggested that all this points to (high) double-digit percentage increases in UC tuition coming up. He pointed me to several news bits from the UC news site on the cuts generally and tuition specifically, including this, this, and this, and pointed me to the UC Regents site, where you can find things like the minutes to their meetings.
Wednesday, June 29, 2011
Friday, June 24, 2011
Probability Assignments Using Set
I'm gearing up for teaching my graduate course on randomized algorithms and probabilistic analysis next semester. It's been a while since I've taught it, and I'm somewhat uncertain what to do with the course, precisely since I wrote the textbook
. Me lecturing from the textbook is boring, both for me and for them, but of course the textbook contains exactly what I think is important.
Somehow I'll have to have them read the textbook offline and try to do more online learning in class. I'm working through creating some programming exercises based on the game Set. (Amazon picture below.)
Set is a great card came (wikipedia entry, or the Set web site). As it says in Wikipedia, "The deck consists of 81 cards varying in four features: number (one, two, or three); symbol (diamond, squiggle, oval); shading (solid, striped, or open); and color (red, green, or purple)." You turn over 12 cards, and look for a set, which is three cards so that for each feature, EITHER all cards are the same in that feature, or they are different. So below is an example of a set. (different in each feature). If they cards were all green, it would still be a set -- they can be all the same in some features, and all the same in others, and still be a set.
The first player to find a set picks it up, and replacement cards are dealt in to get you back to 12 cards. The player with the most cards at the end of the game wins. My eldest had already seen the game in school, and after a few months, she and I now are pretty competitively matched. I'd put it up there with Mastermind as a good mental exercise game for kids.
So the reason I thought about Set for my class is that the game instructions say that the odds of not getting a set with 12 cards dealt out is 33 to 1. (When this happens, or you can't find one, you can deal another card out; with 15 cards, the claim is more than 2500:1.) But when you play the game, it seems you don't find a set much more often. While my daughters and I are probably missing some sets some of the time, it's also clear that conditional probability is coming into play here. At any point in the game, there aren't 12 random cards on the table. Most clearly, suppose I deal 12 cards, find a set, and replace the 3 cards. What's left isn't 12 random cards; it's 9 cards left after a set was removed, and 3 cards remaining from the deck.**
This seems like a nice way to introduce conditional probability in a concrete but perhaps subtle way. And it seems like there are plenty of other related questions one can ask as well. (What's the probability of not finding a set on the kth turn, given a set has been found in the first k-1 turns...) Feel free to suggest exercises. (Apparently the largest number of cards without a set is 20. I wonder if there's a short proof of that without just doing exhaustive search.)
At the very least, it will be a good excuse to get a couple of boxes of Set for the office.
Have to go. My daughter just asked to play a game of Set...
** Of course I'm not the first to have noticed this. Peter Norvig posted on it as well.
. Me lecturing from the textbook is boring, both for me and for them, but of course the textbook contains exactly what I think is important.Somehow I'll have to have them read the textbook offline and try to do more online learning in class. I'm working through creating some programming exercises based on the game Set. (Amazon picture below.)
Set is a great card came (wikipedia entry, or the Set web site). As it says in Wikipedia, "The deck consists of 81 cards varying in four features: number (one, two, or three); symbol (diamond, squiggle, oval); shading (solid, striped, or open); and color (red, green, or purple)." You turn over 12 cards, and look for a set, which is three cards so that for each feature, EITHER all cards are the same in that feature, or they are different. So below is an example of a set. (different in each feature). If they cards were all green, it would still be a set -- they can be all the same in some features, and all the same in others, and still be a set.
The first player to find a set picks it up, and replacement cards are dealt in to get you back to 12 cards. The player with the most cards at the end of the game wins. My eldest had already seen the game in school, and after a few months, she and I now are pretty competitively matched. I'd put it up there with Mastermind as a good mental exercise game for kids.
So the reason I thought about Set for my class is that the game instructions say that the odds of not getting a set with 12 cards dealt out is 33 to 1. (When this happens, or you can't find one, you can deal another card out; with 15 cards, the claim is more than 2500:1.) But when you play the game, it seems you don't find a set much more often. While my daughters and I are probably missing some sets some of the time, it's also clear that conditional probability is coming into play here. At any point in the game, there aren't 12 random cards on the table. Most clearly, suppose I deal 12 cards, find a set, and replace the 3 cards. What's left isn't 12 random cards; it's 9 cards left after a set was removed, and 3 cards remaining from the deck.**
This seems like a nice way to introduce conditional probability in a concrete but perhaps subtle way. And it seems like there are plenty of other related questions one can ask as well. (What's the probability of not finding a set on the kth turn, given a set has been found in the first k-1 turns...) Feel free to suggest exercises. (Apparently the largest number of cards without a set is 20. I wonder if there's a short proof of that without just doing exhaustive search.)
At the very least, it will be a good excuse to get a couple of boxes of Set for the office.
Have to go. My daughter just asked to play a game of Set...
** Of course I'm not the first to have noticed this. Peter Norvig posted on it as well.
Sunday, June 19, 2011
New Books Worth Looking At
New books are coming out all the time, but here are two big ones that stick out in my mind (perhaps because I've seen the authors recently). [Feel free to mention others worth noting in the comments.]
Recently available (I saw copies at FCRC) is The Design of Approximation Algorithms (Amazon link)
by Williamson and Shmoys. Here's a link to the book page. (All books have web pages now, don't you know.) An up-to-the-moment books on approximation algorithms by two well-known experts.
Coming soon is The Nature of Computation (Amazon link)
by Cristopher Moore and Stephen Mertens. Here's a link to the book page. About 1000 pages of introduction to computer science (with some statistical physics, and maybe some other physics, mixed in), with lots of problems. I've seen a preview of the text and it looks like an interesting read. (I'm curious if people will use it for courses -- if you have or are considering it, let me know.)
Recently available (I saw copies at FCRC) is The Design of Approximation Algorithms (Amazon link)
by Williamson and Shmoys. Here's a link to the book page. (All books have web pages now, don't you know.) An up-to-the-moment books on approximation algorithms by two well-known experts. Coming soon is The Nature of Computation (Amazon link)
by Cristopher Moore and Stephen Mertens. Here's a link to the book page. About 1000 pages of introduction to computer science (with some statistical physics, and maybe some other physics, mixed in), with lots of problems. I've seen a preview of the text and it looks like an interesting read. (I'm curious if people will use it for courses -- if you have or are considering it, let me know.) Friday, June 17, 2011
NSF Changing Broader Impacts
The NSF is changing its description of its merit criteria -- specifically, what the Broader Impacts criteria will be. The details are still being worked out, and comments are being collected until July 14. More information can be found on this NSF page.
The current draft text states:
Collectively, NSF projects should help to advance a broad set of important national goals, including:
It does seem, though, that this list isn't particularly theory-friendly. Cryptographers can point to national security; my algorithmic work can certainly point to academia-industry partnerships and economic competitiveness. But more complexity-related proposals, or algorithmic proposals with less clear immediate practical applications -- where do they fit in? Should it be a national goal to support more theoretical research with long-term and unclear payoffs? (I think so, particularly as that sort of research is generally relatively very cheap and has potential for huge benefits.) How would you place such research in the above Broader Impact context, or should a new bullet be added? What else would you add?
The current draft text states:
Collectively, NSF projects should help to advance a broad set of important national goals, including:
- Increased economic competitiveness of the United States.
- Development of a globally competitive STEM workforce.
- Increased participation of women, persons with disabilities, and underrepresented minorities in STEM.
- Increased partnerships between academia and industry.
- Improved pre-K–12 STEM education and teacher development.
- Improved undergraduate STEM education.
- Increased public scientific literacy and public engagement with science and technology.
- Increased national security.
- Enhanced infrastructure for research and education, including facilities, instrumentation, networks and partnerships.
It does seem, though, that this list isn't particularly theory-friendly. Cryptographers can point to national security; my algorithmic work can certainly point to academia-industry partnerships and economic competitiveness. But more complexity-related proposals, or algorithmic proposals with less clear immediate practical applications -- where do they fit in? Should it be a national goal to support more theoretical research with long-term and unclear payoffs? (I think so, particularly as that sort of research is generally relatively very cheap and has potential for huge benefits.) How would you place such research in the above Broader Impact context, or should a new bullet be added? What else would you add?
Thursday, June 16, 2011
Dr. Georgios Zervas
Congratulations to Georgios (alternatively, Giorgos), who defended his thesis today.* (There's still some paperwork to get in, but we drank the champagne afterward, so I'm calling it official.) He gave a great presentation covering some of our old work (on analyzing Swoopo, and efficient keyword value computation) plus some of our work-to-be on studying Groupon. (We've put an appetizer up on arxiv; now that this defense is done, we can finish preparing the main course this summer.) I hope to have the chance to swipe the slides and his jokes and give the talk myself sometime; however, if you'd like an interesting talk on data-driven e-commerce analysis, you should of course just invite him to present it instead.
Three cheers for Dr. Georgios Zervas.
*Giorgos is co-advised by me and John Byers.
Three cheers for Dr. Georgios Zervas.
*Giorgos is co-advised by me and John Byers.
Monday, June 13, 2011
NY Times on Computing
A couple of days ago there was a NY Times article on computing being cool (again), including a shout-out to Harvard's own CS 50 and of course the Social Network.
Matt Welsh has a take on it, but please also look for my comment (#7) if you read it. The issue seems worthy of further discussion -- yes, learning how to make something useful quickly is a really exciting aspect of computer science, but it's not what defines computer science as a field -- which may be taken up here later (or in comments at Matt's blog).
Matt Welsh has a take on it, but please also look for my comment (#7) if you read it. The issue seems worthy of further discussion -- yes, learning how to make something useful quickly is a really exciting aspect of computer science, but it's not what defines computer science as a field -- which may be taken up here later (or in comments at Matt's blog).
Sunday, June 12, 2011
2012 PCs
In an effort to return to normalcy, I find myself agreeing to serve on PCs again this year.
NSDI 2012 call for papers is up. Dina Katabi and Steve Gribble went with the old "The PC meeting will be in Boston" ploy -- very clever, made it hard to say no. They also politely asked that I avoid referring to them as stupid or misguided, and I'm expecting that to be an easy requirement to fulfill. Please send interesting papers, so I have something entertaining to read.
I will, finally, be on an ISIT PC, for ISIT 2012. No information up yet that I know of. But it will be held in Cambridge, MA, a little over a year from now. So it rates to be a HUGE conference. (ISIT is normally in the 700-800+ range, as I recall, so I wouldn't be surprised to see it hit 1000+ here.)
For balance, it might be nice to serve on a (CS) theory PC later in the year. (I was recently asked by one, but the timeline overlapped directly with ISIT, so I declined.) Or not -- I'm sure I'll have papers to push around here at Harvard.
NSDI 2012 call for papers is up. Dina Katabi and Steve Gribble went with the old "The PC meeting will be in Boston" ploy -- very clever, made it hard to say no. They also politely asked that I avoid referring to them as stupid or misguided, and I'm expecting that to be an easy requirement to fulfill. Please send interesting papers, so I have something entertaining to read.
I will, finally, be on an ISIT PC, for ISIT 2012. No information up yet that I know of. But it will be held in Cambridge, MA, a little over a year from now. So it rates to be a HUGE conference. (ISIT is normally in the 700-800+ range, as I recall, so I wouldn't be surprised to see it hit 1000+ here.)
For balance, it might be nice to serve on a (CS) theory PC later in the year. (I was recently asked by one, but the timeline overlapped directly with ISIT, so I declined.) Or not -- I'm sure I'll have papers to push around here at Harvard.
Wednesday, June 08, 2011
ITCS
I was asked to post the call for papers for the (renamed) Innovations in Theoretical Computer Science conference. (I'm glad they finally changed the name -- see previous posts here and here.)
This year the conference is moving out of China, where it was well-funded and the logistics were taken care of, to the US. I think this will be a defining year for the conference, as it tries to set out what it should be. The question I continue to have is how it should distinguish itself from and/or relate to FOCS/STOC/SODA. There seems to be a significant bloc in the theory community that is against making these well-established conferences any bigger; to me, this says that we don't need yet-another-conference with the same type of papers unless it's different somehow. So submit and help decide what the identity of ITCS will be.
This year the conference is moving out of China, where it was well-funded and the logistics were taken care of, to the US. I think this will be a defining year for the conference, as it tries to set out what it should be. The question I continue to have is how it should distinguish itself from and/or relate to FOCS/STOC/SODA. There seems to be a significant bloc in the theory community that is against making these well-established conferences any bigger; to me, this says that we don't need yet-another-conference with the same type of papers unless it's different somehow. So submit and help decide what the identity of ITCS will be.
Tuesday, June 07, 2011
FCRC Continued
I've been enjoying FCRC; of course, I like large conferences where lots of people show, as long as they're run well. Rooms have been pretty full at the talks, and lots of people around to talk to. I still don't understand why people object to the idea of making FOCS/STOC larger (and instead seem to prefer to create new conferences and workshops), but if that's the way the theory community wants it, I'd argue that more conference co-location is a good way to go.
I thought Les Valiant gave an excellent Turing lecture -- I'm sure it will be online soon. He provided a clear scientific challenge -- understanding how evolution could have accomplished so much in so little time (just several billion years) -- and made the case the computational complexity (and in particular learning theory) would be a necessary tool in developing an understanding to this problem. I thought especially he did an excellent job gearing the talk to a general computer science audience, limiting the technical discussion and giving a broad overview of the importance of complexity theory, particularly as it might apply in this setting.
Naturally, my favorite session so far has been the "randomized algorithms" session (1A) for STOC, including The Power of Simple Tabulation Hashing (Patrascu/Thorup), Tight Bounds for Randomized Load Balancing (Lenzen/Wattenhofer), and Social Networks Spread Rumors in Sublogarithmic Time (Doerr/Fouz/Friedrich). The first paper shows that tabulation hashing, while only being 3-wise independent, can provide strong theoretical bounds (and excellent practical performance) for most of the natural application of hashing. The second paper looks at parallel load balancing strategies, and shows that many of the lower bounds proven years ago can be beaten by loosening assumptions that led to the lower bounds in quite natural ways. The third paper considered randomized rumor spreading in social network graphs, including the surprising result that taking care not to (randomly) send a message to the same neighbor in consecutive rounds changes the asymptotic behavior (to just barely sublogarithmic) in this setting. All three of the talks were well-presented, making getting up for an 8:30 session worthwhile.
I'd have to say that the STOC poster session -- done for the first time -- seemed to be a successful experiment. There were plenty of people around talking to the poster presenters, so much so that that it didn't seem to wrap up until more like 11 instead of the scheduled 10:30. Hopefully students who presented will comment on how they liked the experience -- either on this blog, or, more directly, with e-mail to the organizers -- and let them know if they found it valuable. I think getting students to present their work in this way will encourage and benefit them greatly and thereby strengthen the field.
I thought Les Valiant gave an excellent Turing lecture -- I'm sure it will be online soon. He provided a clear scientific challenge -- understanding how evolution could have accomplished so much in so little time (just several billion years) -- and made the case the computational complexity (and in particular learning theory) would be a necessary tool in developing an understanding to this problem. I thought especially he did an excellent job gearing the talk to a general computer science audience, limiting the technical discussion and giving a broad overview of the importance of complexity theory, particularly as it might apply in this setting.
Naturally, my favorite session so far has been the "randomized algorithms" session (1A) for STOC, including The Power of Simple Tabulation Hashing (Patrascu/Thorup), Tight Bounds for Randomized Load Balancing (Lenzen/Wattenhofer), and Social Networks Spread Rumors in Sublogarithmic Time (Doerr/Fouz/Friedrich). The first paper shows that tabulation hashing, while only being 3-wise independent, can provide strong theoretical bounds (and excellent practical performance) for most of the natural application of hashing. The second paper looks at parallel load balancing strategies, and shows that many of the lower bounds proven years ago can be beaten by loosening assumptions that led to the lower bounds in quite natural ways. The third paper considered randomized rumor spreading in social network graphs, including the surprising result that taking care not to (randomly) send a message to the same neighbor in consecutive rounds changes the asymptotic behavior (to just barely sublogarithmic) in this setting. All three of the talks were well-presented, making getting up for an 8:30 session worthwhile.
I'd have to say that the STOC poster session -- done for the first time -- seemed to be a successful experiment. There were plenty of people around talking to the poster presenters, so much so that that it didn't seem to wrap up until more like 11 instead of the scheduled 10:30. Hopefully students who presented will comment on how they liked the experience -- either on this blog, or, more directly, with e-mail to the organizers -- and let them know if they found it valuable. I think getting students to present their work in this way will encourage and benefit them greatly and thereby strengthen the field.
Monday, June 06, 2011
Harvard CS Hires (2011 Edition)
At FCRC, I'm getting asked a lot about hiring. Our hiring season still isn't quite yet finished, but I'm going to go ahead and announce three new faculty who will be joining Harvard. (At least, that's what they've told me!)
On the theory side, Jelani Nelson will be joining us, though in a delayed fashion, as he'll be postdoc-ing first. I know this was reported in a comment on Lance's blog some time ago (before he formally accepted our offer, in fact), so I'm glad to be able to confirm it's correct.
Ryan Adams, who works in machine learning and computational statistics, will also be joining us, and we're thrilled to have hired someone in this increasingly key (and highly competitive) area. Ryan was a student of David MacKay, for whom I've previously expressed worship (most recently here).
On the systems side, Eddie Kohler, well known for his work on the Click router as well as many other systems projects, will be joining us. Non-systems people may know him as the writer of HotCRP, the best conference management software available today. (Yes, I've said it!)
More seriously, we're very excited that all three of these outstanding researchers will be coming to Harvard, allowing us to broaden the department's scope and capabilities significantly. While I'd like to take all the credit (and am totally fine with anyone who wants to give it to me), the real credit goes to David Parkes, who led the search committee this year, and of course all the rest of the highly overworked search committee members.
On the theory side, Jelani Nelson will be joining us, though in a delayed fashion, as he'll be postdoc-ing first. I know this was reported in a comment on Lance's blog some time ago (before he formally accepted our offer, in fact), so I'm glad to be able to confirm it's correct.
Ryan Adams, who works in machine learning and computational statistics, will also be joining us, and we're thrilled to have hired someone in this increasingly key (and highly competitive) area. Ryan was a student of David MacKay, for whom I've previously expressed worship (most recently here).
On the systems side, Eddie Kohler, well known for his work on the Click router as well as many other systems projects, will be joining us. Non-systems people may know him as the writer of HotCRP, the best conference management software available today. (Yes, I've said it!)
More seriously, we're very excited that all three of these outstanding researchers will be coming to Harvard, allowing us to broaden the department's scope and capabilities significantly. While I'd like to take all the credit (and am totally fine with anyone who wants to give it to me), the real credit goes to David Parkes, who led the search committee this year, and of course all the rest of the highly overworked search committee members.
Sunday, June 05, 2011
FCRC : Awards Banquet
I got to FCRC a little early to attend the ACM Awards Reception and Banquet. (Les Valiant nicely put my name on a list.) For more on the awards you can also go the ACM award page. They have a nice little award booklet they gave out at the reception, but it looks like last year's is still up on the page -- I imagine they'll update it soon. They also had copies of the latest Communications of the ACM out, which is sporting a cover with an extremely nice picture of Les on it.
It was a very nice and extremely well-run event. It was black-tie optional, and I was one of the half in a regular tie. It's odd to see that many computer scientists I know in a tux -- certainly not something I've ever seen before! It was at the Fairmont, in a suitably-large-sized space, and with much better food than I was expecting (and after flying all day, I was suitably hungry to enjoy it). While there were a lot of awards to go through, they kept it moving along quite quickly, so it didn't drag on at all. (I'd like to thank the award-winners, for keeping their speeches both short and entertaining.) The theory highlights were of course Les for the Turing Award, but also Craig Gentry received the Grace Murray Hopper Award for his work on fully homomorphic encryption, and Kurt Melhorn received the Paris Kanellakis Theory and Practice Award for his work leading to LEDA. Bryan Parno, a Harvard undergrad and CMU grad student, received the Doctoral Dissertation Award. On the systems side, Frans Kaashoek received the ACM-Infosys Foundation Award. And of course there were the new ACM Fellows.
Thanks to everyone involved.
It was a very nice and extremely well-run event. It was black-tie optional, and I was one of the half in a regular tie. It's odd to see that many computer scientists I know in a tux -- certainly not something I've ever seen before! It was at the Fairmont, in a suitably-large-sized space, and with much better food than I was expecting (and after flying all day, I was suitably hungry to enjoy it). While there were a lot of awards to go through, they kept it moving along quite quickly, so it didn't drag on at all. (I'd like to thank the award-winners, for keeping their speeches both short and entertaining.) The theory highlights were of course Les for the Turing Award, but also Craig Gentry received the Grace Murray Hopper Award for his work on fully homomorphic encryption, and Kurt Melhorn received the Paris Kanellakis Theory and Practice Award for his work leading to LEDA. Bryan Parno, a Harvard undergrad and CMU grad student, received the Doctoral Dissertation Award. On the systems side, Frans Kaashoek received the ACM-Infosys Foundation Award. And of course there were the new ACM Fellows.
Thanks to everyone involved.
Wednesday, June 01, 2011
Justin's Poster at FCRC
Justin Thaler, a student I'm advising (or, quite arguably, the other way around), will be at the poster session for STOC, ready to talk about a bunch of his currently-under-submission work on streaming interactive proofs, including the most recent, Practical Verified Computation with Streaming Interactive Proofs (with me and Graham Cormode). Justin has been working for some time on streaming problems with the following motivation: you're gathering a big data set that you're going to store, and compute on, on the cloud. How do you trust that the cloud is going to give you the right answer? A natural theorists' answer is via an interactive proof, and here the natural limitation is to a streaming verifier: a verifier that sees all the data initially, forwarding it to the cloud, but can't store it all due to limited memory, including later when the prover (the cloud) wants to prove that it's done the computation correctly.
We didn't initiate these models, to be sure. There's now been a chain of work, including the "annotations" paper by Chakrabarti, Cormode, and McGregor, which was a primary motivator. For Justin's other theoretical work, see the arxiv version of his ESA paper (with me and Cormode, journal version under submission) and this paper of his with Cormode and Yi (under submission).
Some time ago I challenged Justin to figure out if this work on streaming verifiers was "practical" for real-world cloud settings, and if not, why not. The outcome (so far) is the Practical Verified Computation with Streaming Interactive Proofs paper. We're not the only ones to have noticed that perhaps interactive proofs are ready for deployment in these kinds of real-world systems. Apparently, there was a recent HotOS paper, Toward Practical and Unconditional Verification of Remote Computations, on the same theme, by real-live honest-to-goodness systems people. I'll avoid (biased) comparisons, and leave that to others.
But I can highlight some of what Justin's done. He's considered and implemented both special-purpose "building-block" functions, like self-joins (or F_2 computations), and a fully general approach for arbitrary computations based on the "Muggles" protocol (interactive proofs with polynomial time provers). He's considered and implemented both non-interactive protocols, where the prover sends a single message that includes both the answer and the verification, and interactive protocols, where the prover and verifier have a multi-round conversation to verify the result. Along the way he's had to come up with several "engineering" improvements (with some strong theoretical foundations) to make things practical, including a clever use of FFTs for the non-interactive protocols that seems new, and adopting the approach of linearizing polynomials from previous work on interactive proofs to improve efficiency to these protocols.
Our experience, I think, shows that with some significant engineering, interactive proof systems in the streaming verifier setting are ready for real systems. So if you get a chance stop by and ask Justin more about the work. He's eager to talk about it!
We didn't initiate these models, to be sure. There's now been a chain of work, including the "annotations" paper by Chakrabarti, Cormode, and McGregor, which was a primary motivator. For Justin's other theoretical work, see the arxiv version of his ESA paper (with me and Cormode, journal version under submission) and this paper of his with Cormode and Yi (under submission).
Some time ago I challenged Justin to figure out if this work on streaming verifiers was "practical" for real-world cloud settings, and if not, why not. The outcome (so far) is the Practical Verified Computation with Streaming Interactive Proofs paper. We're not the only ones to have noticed that perhaps interactive proofs are ready for deployment in these kinds of real-world systems. Apparently, there was a recent HotOS paper, Toward Practical and Unconditional Verification of Remote Computations, on the same theme, by real-live honest-to-goodness systems people. I'll avoid (biased) comparisons, and leave that to others.
But I can highlight some of what Justin's done. He's considered and implemented both special-purpose "building-block" functions, like self-joins (or F_2 computations), and a fully general approach for arbitrary computations based on the "Muggles" protocol (interactive proofs with polynomial time provers). He's considered and implemented both non-interactive protocols, where the prover sends a single message that includes both the answer and the verification, and interactive protocols, where the prover and verifier have a multi-round conversation to verify the result. Along the way he's had to come up with several "engineering" improvements (with some strong theoretical foundations) to make things practical, including a clever use of FFTs for the non-interactive protocols that seems new, and adopting the approach of linearizing polynomials from previous work on interactive proofs to improve efficiency to these protocols.
Our experience, I think, shows that with some significant engineering, interactive proof systems in the streaming verifier setting are ready for real systems. So if you get a chance stop by and ask Justin more about the work. He's eager to talk about it!
Monday, May 30, 2011
Deletion Channel Pointer : Kanoria and Montanari
For those half a dozen of us in the world who care about the deletion channel (and perhaps I'm overcounting), I'm a bit late in pointing to the now available extended version of the Kanoria and Montanari paper from ISIT last year. It follows a path laid out by my student Adam Kirsch by looking at an information theoretic characterization of the channel, but then uses a perturbation analysis to get the right degree distribution and very tight bounds as the deletion probability goes to 0. There's still plenty we don't understand about the deletion channel, but this paper moves us forward nicely.
Thursday, May 26, 2011
Wednesday, May 25, 2011
Annual Facing the Reviews
Teaching reviews for spring (Algorithms and Data Structures) came in today; time to face the music once again.
Actually, this year, my numbers were up substantially; still room to improve, of course, but unlike the last two years, they didn't make me cringe. If it seems surprising that my teaching numbers would go up when I'm now busy being Area Dean, it seems clear that the credit actually goes to the class. This was easily the best class of students I've had in several years -- a really strong bunch. I think the delta in scores reflect their capabilities more than anything else.
It's always interesting to see the contradictions embedded in the responses. This year, I decided to take advantage of the opportunity to ask specific questions, and asked the class if they preferred the written assignments or programming assignments (and why), and which lecture they would want to see removed/not want to see removed. It was almost 50-50 for the written/programming assignments, with a slight edge to written assignments. And it seems like for every person who really liked the primality testing/RSA lectures, or the least common ancestor/suffix tree lectures, or the lecture on heuristics, there's another who would remove the exact same things. This is entirely consistent with feedback I've gotten directly over the years. You can't please everyone. (Sorry, that should be "I can't please everyone." I shouldn't speak for you.)
A number of students commented on how valuable the material was. The negative version of this is that the course is "CS broccoli" ("you really ought to take it, but you probably won't enjoy it much"), but the positive version is much more pleasant -- the class really shapes how you think about problems, and is IMPORTANT knowledge for CS majors. I made a point this semester of really emphasizing the point that correctness is a design consideration that can be traded off with other performance metrics like time and space, and multiple students commented specifically on finding that idea exciting.
On the downside, I'm still intimidating to some students (on the other hand, several others took me up on my open invitation to go to lunch with them this semester), the exams are too hard, and they want more feedback. And there are too many math majors coming in and messing up the curve.
How is this last problem handled elsewhere? It's almost tempting to have a CS theory course for CS majors and a harder course for math majors. Is it fair to have an "honors track" within the class for the math types and modify the grading curve accordingly?
If you're from the class and you've stumbled on this -- congratulations on making it through. Even if your grade wasn't as high as you might have liked, please don't let it get you down. As you move on how you do on problem sets and timed tests is less important; it's what you can accomplish with the knowledge you've gained. So accomplish something great, and come back and show off to me -- I'll be eager to see it!
Actually, this year, my numbers were up substantially; still room to improve, of course, but unlike the last two years, they didn't make me cringe. If it seems surprising that my teaching numbers would go up when I'm now busy being Area Dean, it seems clear that the credit actually goes to the class. This was easily the best class of students I've had in several years -- a really strong bunch. I think the delta in scores reflect their capabilities more than anything else.
It's always interesting to see the contradictions embedded in the responses. This year, I decided to take advantage of the opportunity to ask specific questions, and asked the class if they preferred the written assignments or programming assignments (and why), and which lecture they would want to see removed/not want to see removed. It was almost 50-50 for the written/programming assignments, with a slight edge to written assignments. And it seems like for every person who really liked the primality testing/RSA lectures, or the least common ancestor/suffix tree lectures, or the lecture on heuristics, there's another who would remove the exact same things. This is entirely consistent with feedback I've gotten directly over the years. You can't please everyone. (Sorry, that should be "I can't please everyone." I shouldn't speak for you.)
A number of students commented on how valuable the material was. The negative version of this is that the course is "CS broccoli" ("you really ought to take it, but you probably won't enjoy it much"), but the positive version is much more pleasant -- the class really shapes how you think about problems, and is IMPORTANT knowledge for CS majors. I made a point this semester of really emphasizing the point that correctness is a design consideration that can be traded off with other performance metrics like time and space, and multiple students commented specifically on finding that idea exciting.
On the downside, I'm still intimidating to some students (on the other hand, several others took me up on my open invitation to go to lunch with them this semester), the exams are too hard, and they want more feedback. And there are too many math majors coming in and messing up the curve.
How is this last problem handled elsewhere? It's almost tempting to have a CS theory course for CS majors and a harder course for math majors. Is it fair to have an "honors track" within the class for the math types and modify the grading curve accordingly?
If you're from the class and you've stumbled on this -- congratulations on making it through. Even if your grade wasn't as high as you might have liked, please don't let it get you down. As you move on how you do on problem sets and timed tests is less important; it's what you can accomplish with the knowledge you've gained. So accomplish something great, and come back and show off to me -- I'll be eager to see it!
Friday, May 20, 2011
NSF Bows to Blog Pressure (Tongue-in-Cheek)
As some of you may recall, I accused the NSF of being "misguided" in changing its graduate fellowship policy to effectively disallow teaching.
So I was please to get home tonight and see that some students had forwarded me the following e-mail from the NSF:
More seriously, I'm glad they're pausing and getting some more input on the issue. As I like to repeat often, the NSF is a wonderful institution, and it's nice to see them showing willingness to revisit this issue, given my opinion that their new policy was questionable in terms of its benefit to students. I imagine many institutions encompassing large bureaucracies would never manage to reconsider a decision like this, so it is to their credit.
So I was please to get home tonight and see that some students had forwarded me the following e-mail from the NSF:
Dear Colleague:Now of course I wouldn't want to claim that this about-face was all due to my blog post. I'll just let you draw your own conclusions.
The purpose of this memorandum is to inform you of recent developments
in the NSF Graduate Research Fellowship Program (GRFP). There was a
recent change in policy that NSF has decided to reconsider. In
particular, the policy concerns what can be expected of Fellows during
the three years they receive NSF funding (on tenure). NSF has decided
to reinstate the previous policy with respect to this issue while
further study is conducted to inform this and other GRFP policies.
The policy that will be in effect during the 2011-2012 Fellowship Year
is an updated version of the one described in the 2009 Guide (NSF
09-62), which is as follows:
Each Fellow is expected to devote full time to advanced scientific
study or work during tenure. However, because it is generally accepted
that teaching or similar activity constitutes a valuable part of the
education and training of many graduate students, a Fellow may
undertake a reasonable amount of such activities, without NSF
approval. It is expected that furtherance of the Fellow's educational
objectives and the gain of substantive teaching or other experience,
not service to the institution as such, will govern these activities.
Compensation for such activities is permitted based on the affiliated
institution’s policies and the general employment policies outlined in
this document.
You can refer to the 2011 Guide (NSF 11-031) at
http://www.nsf.gov/publications/pub_summ.jsp?ods_ key=nsf11031 for
further information about teaching, research, and other work
activities during tenure years.
We apologize for confusion these changes may have caused, but look
forward to working with you to ensure the GRFP is as effective as
possible in helping to ensure the vitality of the U. S. scientific and
engineering workforce.
Sincerely,
The Graduate Research Fellowship Program Office
Division of Graduate Education
Directorate for Education & Human Resources
National Science Foundation
More seriously, I'm glad they're pausing and getting some more input on the issue. As I like to repeat often, the NSF is a wonderful institution, and it's nice to see them showing willingness to revisit this issue, given my opinion that their new policy was questionable in terms of its benefit to students. I imagine many institutions encompassing large bureaucracies would never manage to reconsider a decision like this, so it is to their credit.
Wednesday, May 18, 2011
Serving Non-Majors in CS Classes
At the end of the year, I gave a short in-house presentation highlighting some aspects of the state of CS at Harvard. In gathering data, one thing that struck me -- and I highlighted in our presentation -- is that most of the students taking our classes are not majoring (or, in Harvard-speak, concentrating) in computer science.
This shouldn't have been a big surprise -- if you look at the number of concentrators and then do the math this pretty much had to have been the case -- but it was a surprise to me how large and widespread the effect was. Sure, our intro programming classes are filled with non-majors. That's not hard to figure out, given we had about 500 people taking our first semester intro programming class this year. We have LOTS more economics majors than CS majors in that class. But even in my Algorithms and Data Structures, which I think of as core CS, only about 1/2 the class was CS majors. (Lots of math, applied math, physics, as well as several from other majors.) In some of our classes that are designed more to be outreach classes, like our courses on visualization and user interfaces, only about 1/3 of the class is CS majors, and others are from all over the campus.
This is, I think a great thing. I'd like Harvard applied math, math, physics, engineering, government, statistics, sociology, economics, and English majors to leave Harvard with some strong foundations in CS. The question is, how should we in CS at Harvard think about it? One idea is that there's certainly room for us to attract more majors into CS at Harvard, and we're certainly working on that. But another idea is that we should be looking for opportunities to teach classes that are both good for our majors and can appeal broadly to others as well. Harvard offers something like minors (call "secondaries") which requires only a small number of classes; another measure of success for us would be if we can significantly increase the number of CS secondaries.
Along these lines, David Parkes will be offering his version of an undergraduate Econ-CS course for the first time next year. I expect it will be a very popular offering, for CS majors and others.
This shouldn't have been a big surprise -- if you look at the number of concentrators and then do the math this pretty much had to have been the case -- but it was a surprise to me how large and widespread the effect was. Sure, our intro programming classes are filled with non-majors. That's not hard to figure out, given we had about 500 people taking our first semester intro programming class this year. We have LOTS more economics majors than CS majors in that class. But even in my Algorithms and Data Structures, which I think of as core CS, only about 1/2 the class was CS majors. (Lots of math, applied math, physics, as well as several from other majors.) In some of our classes that are designed more to be outreach classes, like our courses on visualization and user interfaces, only about 1/3 of the class is CS majors, and others are from all over the campus.
This is, I think a great thing. I'd like Harvard applied math, math, physics, engineering, government, statistics, sociology, economics, and English majors to leave Harvard with some strong foundations in CS. The question is, how should we in CS at Harvard think about it? One idea is that there's certainly room for us to attract more majors into CS at Harvard, and we're certainly working on that. But another idea is that we should be looking for opportunities to teach classes that are both good for our majors and can appeal broadly to others as well. Harvard offers something like minors (call "secondaries") which requires only a small number of classes; another measure of success for us would be if we can significantly increase the number of CS secondaries.
Along these lines, David Parkes will be offering his version of an undergraduate Econ-CS course for the first time next year. I expect it will be a very popular offering, for CS majors and others.
Monday, May 16, 2011
Daily Updates
Getting slowly back into blogging, some happenings from the day.
I've gotten a couple of nice notes from students saying they learned a lot from my class this semester. To any students reading the blog, I encourage you to send such notes. It will make your prof feel maybe it's all worthwhile.
A colleague pointed me to a nice example of a real-world application of Bloom filters.
I hosted a large dinner at my house a while back as part of recruiting our new faculty. Now I'm being told that as Harvard is tax-exempt I was supposed to give the caterer a form with Harvard's tax-exempt status and I need to get them to refund the tax (or I won't get the tax reimbursed). It's not a big deal, but I just love university financial offices and their fun rules. (How I'm supposed to know this, I don't know. When we take a candidate to dinner, we don't get to claim tax-exempt status, but apparently for a meal catered in your home... sigh.) I'm sure it will get worked out.
I've gotten a couple of nice notes from students saying they learned a lot from my class this semester. To any students reading the blog, I encourage you to send such notes. It will make your prof feel maybe it's all worthwhile.
A colleague pointed me to a nice example of a real-world application of Bloom filters.
I hosted a large dinner at my house a while back as part of recruiting our new faculty. Now I'm being told that as Harvard is tax-exempt I was supposed to give the caterer a form with Harvard's tax-exempt status and I need to get them to refund the tax (or I won't get the tax reimbursed). It's not a big deal, but I just love university financial offices and their fun rules. (How I'm supposed to know this, I don't know. When we take a candidate to dinner, we don't get to claim tax-exempt status, but apparently for a meal catered in your home... sigh.) I'm sure it will get worked out.
Friday, May 13, 2011
Back to Blogging
I've given my final, and have grades ready to submit. The semester is over!
Over the summer I may do some blogging again, as I may have time for it. I was noticing that on my calendar, I now have empty days ahead, something I haven't seen for a while. I'm looking forward to those.
To start off, I've just finishing registering for FCRC, and it seemed apropos to complain about how expensive it was. I'll be there about 4 days, for 2 overlapping conferences (that last 5 days), and it costs nearly $1000 in registration fees.
But then I looked at other conference prices. Int'l Symposium on Information Theory 2011 is $725. That does include several lunches, a banquet, etc., and it is a 5-day conference. SIGCOMM 2011 is $625, again with banquet, 3-day conference. Not sure about lunches.
FCRC still looks expensive, but perhaps not ridiculously so.
Over the summer I may do some blogging again, as I may have time for it. I was noticing that on my calendar, I now have empty days ahead, something I haven't seen for a while. I'm looking forward to those.
To start off, I've just finishing registering for FCRC, and it seemed apropos to complain about how expensive it was. I'll be there about 4 days, for 2 overlapping conferences (that last 5 days), and it costs nearly $1000 in registration fees.
But then I looked at other conference prices. Int'l Symposium on Information Theory 2011 is $725. That does include several lunches, a banquet, etc., and it is a 5-day conference. SIGCOMM 2011 is $625, again with banquet, 3-day conference. Not sure about lunches.
FCRC still looks expensive, but perhaps not ridiculously so.
Wednesday, April 20, 2011
Harvard CS -- Growth in Women Majors
Some good news for us. With the growth in our introductory course, more women are declaring Computer Science as their concentration. And we seem to be growing.
Crimson article here.
Crimson article here.
Subscribe to:
Posts (Atom)