Sunday, February 02, 2020

Current CS 124 Stats

This is as much personal recording for me (and perhaps of interest to Harvard people who read the blog).  But also putting the numbers here for others to know for comparison.

I'm teaching the undergraduate algorithms and data structures class, CS 124, for the first time in a few years, so let's look at the initial enrollment numbers.  Harvard has its strange and wonderful shopping period, so I'm just getting the numbers now after the first week.  (Feel free to comment with comparative stats from your own institution!)

Current numbers are a bit over 280 students, about 20 more than last year, about 60 more than the last time I taught it.  Seems like the course has been growing about 20 people a year for the last few years.  This number may go up or down a few (most likely down), but is probably close to where the class will end up.  I keep thinking we've hit "peak 124", but it keep going upwards.  Part of this seems to be because a few more grad students (especially various master's students) are taking it.  Something like 1/7 of the undergraduates take this course now, which to me always seems amazing.  When I was an undergraduate at Harvard, CS courses were just not this big.  My first year teaching at Harvard, CS 124 was about 90 students, and that was huge.  I do realize, of course, that many places have even larger CS classes;  I'm not meaning to complain.

Surprising to me, about 1/4 of the course is first-years.  This is more than I remember from my previous years teaching it;  it's a hard course that requires both math and programming background, so first-years usually wait.  On the other hand, the first-years taking it are self-selecting, and in past years the first-year grade average is notably higher than the class average.

About 40% sophomores, not surprisingly the largest group.  Then a mix of juniors, seniors, and grad students from various programs.

The course is also offered through the Extension School;  here numbers change a lot.  Right now it's about 45, but that will most likely drop further.

If I've counted right, it's my 18th time teaching the class.  I'm pretty sure I'll get to 20.  I suppose it's possible I'll get to 30 or more, but it's likely someone else will take it over at some point.

Tuesday, January 14, 2020

ITCS 2020, Reflections

I've spent Sunday/Monday at ITCS, or Innovations in Theoretical Computer Science, where I am giving a talk on this paper on Scheduling with Prediction and the Price of Misprediction (LIPIcs page) (which is one of several recent works on Algorithms with Predictions (powerpoint slides)).

I'm told it's 10 years since ITCS started as a conference, and I was one of the skeptics that really did not think it was a good idea 10 years ago.  So as I'm sitting in the sessions, what do I think now?  What are the pros and cons of ITCS?

On the negative side, ITCS is not very big.  It is just over 100 people registered, so it's like a big workshop/small conference size.  (And considering that it's usually held in central places with lots of students, those numbers are buffered by locals.)  Somehow, it's scheduled the 2nd week of January, right after SODA, which seems problematic, and certainly (if it's kept that way) may keep it from getting any larger.  The number of "senior people" around at any one time seemed generally small, a problem for things like "Graduating Bits" (see below).  As ITCS, at least 10 years ago, was supposed to build up to another "premier" TCS conference, focused on "innovative" work, the attendance seems a bit disappointing.

On the neutral side, the conference is single-session, and to make that work, talks this year are limited to 12 minutes.  Your mileage may vary on whether you think this is good or bad;  it seems to work.  (My take:  I slightly prefer parallel sessions, because it means there's more times where there's something I want to see, and that's more important than the times where there are two talks at the same time I want to see.  And 12 minutes is certainly workable but maybe a few minutes short.  But again, that's just my opinion.)  This year (and possibly going forward), some papers were accepted without a full talk -- instead they have a 3-minute talk and a poster in a poster session.  Again, it's not clear to me if this is good or bad (though more paper acceptances makes me lean to the good side), but it seemed to work fine and people were happy with it.  (Such papers are considered full publications and treated the same in the proceedings.)

On the positive side, the conference seems well run.  It's held in a university building, so no expensive hotel costs;  instead they're generous with food and keep registration costs reasonably low.  They use LIPIcs, which provides a good system and approach for publishing papers at low cost.  (Note, I was until recently part of the LIPIcs editorial board, so I'm biased there.)  They seem to be covering their expenses from what I understand.  The business meeting was blessedly short.  They're recording all the talks.  They're doing interesting things like "Graduating Bits" for people who are job-looking (where people graduating or coming out of a postdoc give short talks about their work).

In terms of content, it seems really good.  I've seen several good talks and interesting papers.  While I'm not sure how to quantify whether ITCS work is more "innovative" than the work at other major TCS conferences, I do actually think they are noticeably more open at ITCS than other conferences about accepting papers based on the paper's underlying idea rather than on "technical mastery".

My thoughts 10 years ago were that ITCS was not a great outcome for the community, and that instead the community should push for:

1)  Aiming to do better about opening up the criteria for paper acceptance, including weighing innovation/practical relevance in reviewing papers at FOCS/STOC/SODA.
2)  Increasing the number of papers accepted to these conferences, as too many good papers were being rejected.

Viewed under this lens, ITCS could, I think, be viewed as a success.  The theory community seems unwilling to expand conferences by accepting more papers.  (I note that while the STOC theory-fest has changed and expanded STOC, it hasn't really seemed to increase attendance, and while the number of accepted papers has increased slightly, it hasn't kept pace with the growth in the field.)  ITCS provides another venue for high-quality theory papers, thereby increasing the number of such papers published each year within the theory community, and I think it is generally viewed as a high-quality conference.  And, as I mentioned, ITCS seems at least somewhat more flexible in its criteria for what is an acceptable paper.  ITCS has, I think, in these regards been a benefit for the theory community.

However, despite the success of ITCS, I think it's a band-aid on structural issues in the theory community.  While these issues are complex and many-sided, just comparing with the growth and excitement in the AI community is a little depressing.  Indeed, what I see is AI absorbing significant parts of the theory community;  lots of theory papers now end up at NeurIPS, AAAI, ICML, or AISTATS, because the theory community doesn't seem to have room for them, or doesn't judge them as sufficiently significant.  I view this as a problem for the theory community, the result of the problems I saw 10 years ago for which I didn't think ITCS was the right response.  (Though perhaps it was/is not really viewed as a problem by others;  all of CS, including theory, seems to continue growing;  theory just seems to me to be growing less than it could or should.)

To conclude, my thanks and congratulations to those many people that have organized and maintained ITCS over the years;  I appreciate your work, as I think the whole community does. 

By the way, I thought it never snowed in Seattle, so I'm confused; what is all the cold white stuff outside?

Wednesday, November 13, 2019

Allston : Students Should Speak Up

I have had (as is pretty usual for me) some number of lunches with students this semester, and many of them asked me about the Computer Science move to Allston.  A lot of times, these questions are concerns:  what food will we have there, how frequently will buses run, what sort of space will there be for students to hang out/study etc., what all will be over there?

These are good questions.  I don't know the answers, I think a lot is still being worked out or decided.  I realize that's not a great response. 

I've started encouraging students to start asking these questions, more directly, to the powers that be.  Specifically, I've suggested to the small number of undergrads I've been lunching with that they should start sending e-mails to the powers that be, asking whatever questions they have, and expressing their concerns.  If you have questions, or wishes, regarding the food, safety, transportation, etc. at the new Allston building, you should ask or let your desires be known.  And, I'll be frank here, you should not (just) let the faculty know -- we're at best an indirect channel to the powers, and they may listen to all of you more than they listen to us.  Contact the powers directly.

(Graduate students too.)

It might be more impactful if students organize to make their questions and/or wishes known.  Or not.  That's up to you really.  But if you want Allston to be successful from where you stand, now is a pretty good time to get involved, before we all start over there next fall.  For Allston to be the academic home you want, you may have to speak up. 

I realize undergrads might not know who are the powers that be that they should contact.  So I'll provide a starting list:

Frank Doyle, Dean of the School of Engineering and Applied Sciences
Claudine Gay, Dean of the Faculty of Arts and Sciences
Alan Garber, Provost
Rakesh Khurana, Dean of Harvard College
Amanda Claybaugh, Dean of Undergraduate Education

And finally, yes, of course it's a Buffy (well, Angel) reference

Saturday, October 12, 2019

Crimson Editorial on Allston

This was the first Crimson editorial I can recall about the upcoming move computer science will be making to Allston next year. 

I'd encourage students (both undergraduate and graduate, but perhaps especially  undergraduates -- there are more of you!) to find ways to make their concerns prior to the move and eventually their issues with the Allston move heard by the powers-that-be at Harvard.  You could interpret this as cynicism that I think Harvard will mess this up significantly in various ways.  Or you could interpret this as optimism that I think that, while of course problems will arise, Harvard will work to fix them when they are brought to their attention by enough people. 

Under either interpretation, I think the students making their own voice heard will be very important to helping make this move a success. 

Thursday, October 03, 2019

Harvard Admissions Lawsuit Decision Out

As someone who reads a significant number of court documents and decisions (I still do expert witness work), I can recommend for your reading pleasure the very recent decision on the Harvard admissions case.  For those who want a sense of how Harvard admissions works, you will get a good summary of the information that came out during the trial.  For those who want to see a well-written court decision, in my opinion, this is a good example.  (Whether you agree with the decision or not, you should find the decision well written;  it lays out the issues and challenges in determining the decision clearly, and similarly explains the reasons for the ultimate conclusion clearly.)  And for those who care about the actual underlying issues of discrimination and affirmative action, I think the document provides a lot of food for thought, with a depth beyond what you'll see in the  news coverage. 

Friday, September 20, 2019

Changing Times

An old friend from college sent me an e-mail, and it got me thinking.  When I was an undergraduate at Harvard some significant number of years ago, I took the graduate level algorithms course offered by Michael Rabin and the graduate level complexity course by Les Valiant.  There were maybe a half dozen people in each of the classes.  (They were great classes, of course. But CS at Harvard back then was really, really small.) 

This semester, I'm teaching the graduate level course on randomized algorithms and probabilistic analysis.  Right now, the enrollment is 74 students;  well more than half are undergraduates.  Somehow, that says something to me -- about how the field has grown, and in at least some regards how Harvard has changed.  And about how much more prepared students are these days for these kinds of classes.  (Knowledge or probability is much more prevalent.)  Class sizes have been creeping up for so long that while it's noticeable year-to-year, it's much more stark and remarkable when I think back to my own time in college. 

Of course, it's also on my mind because it's a pain teaching a graduate class that large.  But it's a pain I can live with -- if I didn't like teaching, I wouldn't have become a professor.  And it's gratifying, if not a little bit shocking, that there's this kind of interest in the subject I really love, that I've been excited by for decades. 

Saturday, September 07, 2019

Off to ALGO/ESA 2019

I'm shortly hopping on a plane to head to ALGO/ESA.  I'll be giving a survey-ish talk on Learning Augmented Algorithms, covering my work so far in the area as well as some of the work by others.  I think it's a highly promising direction fitting in the framework of Beyond Worst Case Analysis, so I'm excited to give the talk, and hoping it's still a novel enough area to be new to most of the audience. 

For those of you who are there, feel free to say hi -- I'm looking forward to talking to people. 

Wednesday, September 04, 2019

Happy New Academic Year: Teaching Randomized Algorithms

It seems I haven't written on this blog for a while.

Today was the start of a new semester.  I'll be teaching Randomized Algorithms and Probabilistic Analysis, using the new edition of my book with Eli Upfal as a base, and throwing in other material.  (Everyone should buy the book!  Here's a link.) 

It's a graduate level class, but generally designed for first year graduate students, and there were a lot of undergrads "shopping" it today.  (We don't do pre-registration at Harvard, and students get the first week to choose classes, known as shopping.)  So many that people were standing out the doors of the room.  But because we have a bit of a shortage of classes this semester, I'm guessing there's a good fraction of students just checking it out.  We'll see Thursday, but for now I'll predict we'll fit in the classroom, and wait to see if I'm wrong.  (If I'm wrong, that's wonderful too.)   

It's been four years since I last taught the course, so this time I'm trying something new.  When I've previously taught the course, I tried to make the class inviting and friendly by telling the class we'd begin without assuming the class knew probability, and so the first couple of weeks would be reviewing basics (like, say, linearity of expectations and union bounds), albeit in a CS algorithms context.  This time, I let the class know I'm assuming they know (or will pick up) basic probability, and so they should read chapters 1-4 on their own, and we'll start with Chapter 5, Balls and Bins models.  Over the last decade, I've seen a huge shift in probability knowledge -- Stat 110, Harvard's probability course, has become one of Harvard's biggest classes.  Many students have already taking AI or ML or even data science courses where they've done some (further) probability.  It feels appropriate (and safe) to assume people entering in the class know probability, or can review what they need on their own, and start the class further along.

Now finally, a request.  It's actually hard for me to teach when using this book, because I don't want to just read the book to the students.  That's boring.  On the other hand, if I thought something was important, I most likely already put it in the book.  We have to mix up the standard lecturing format a bit.  So two things we'll be doing are

1)  doing some "puzzle problems" at the beginning of most classes, so people can try to solve problems.  (Kind of a flipped classroom approach, but not a full commitment.)
2)  reading papers, related to the class topics.

So if you have any good suggestions of probability puzzle problems, or readable papers (particularly application papers) that use relatively basic probabilistic analysis in neat ways, send them over.  I've got a semester to fill.

For curious people, here's one of today's starting problems, which I first learned about in graduate school.  (I'm pretty sure I owe thanks to Claire Kenyon for teaching it.  I'll link to the corresponding Wikipedia page on the problem maybe later.)

After lunch, Bob suggests the following game to see who pays.  Alice and Bob will each choose a different sequence of three flips.  (So they could choose "Heads-Tails-Heads'', or "Tails-Tails-Tails'' for example.)  After they choose, a fair coin will be tossed until one of their sequences appears as a consecutive subsequence of the coin tosses.  The player whose sequence appears first wins. (Note that if they choose the above sequences, and if the flips come up Heads-Tails-Tails-Tails, the player that chose Tails-Tails-Tails would win as soon as their subsequence appears;  it's not three flips, then start over again.)  Bob politely says that Alice can choose first, and after she chooses and tells him her sequence he'll choose a different sequence.  What should Alice choose?

Wednesday, January 09, 2019


I spent the last few days at SODA-ANALCO-ALENEX-SOSA in San Diego.  (Nice location choice, I'd say!)  Here's some news.

This will be the last ANALCO (Analytic Algorithms and Combinatorics).  Apparently submissions have been decreasing, so they've decided it will halt and the work on these topics will go into SODA and other conferences.  I'm not sure how to think of it -- I think we as a community have far too many conferences/workshops generally, but I think the SODA model of having ANALCO and ALENEX (and now SOSA, I imagine) folded in cleanly into the main conference is an excellent model.  I also like the ANALCO topics.  But I can understand the time may have come to do something else.  Thanks to everyone who worked to organize ANALCO and keep it going these many years.

It looks like SOSA (Symposium on Simplicity in Algorithms) will be taking its place in the SODA lineup.  I co-chaired the symposium with Jeremy Fineman this year, the second for the symposium.  I was surprised by the high quality of the submissions, and was then further surprised by the strong turnout at SODA.  The room was quite full for the Tuesday afternoon sessions, and there were easily 75+ people at several of the talks.  I do think there's a need for SOSA -- no other workshop/conference hits the theme of simplicity in our area, and it's a really nice fit with the rest of SODA.  I'm hoping it will last, and in particular that they'll continue to have a good number of high quality submissions, but that depends on all of you.  Ideally, there will be a positive feedback loop here -- now that there's a good home for this type of work (besides notes on the arxiv), people will be more inclined to write up and submit things to SOSA.  For Tuesday's talks, I'll call out Josh Alman's great presentation on "An Illuminating Algorithm for the Light Bulb Problem" as my favorite for the day.

With ANALCO exiting, though, I think there's more room for additional satellite events at SODA, so hopefully some people will get creative.

If I had thought about it I should have live-blogged the business meeting.  I'd say as highlights, first, Sandy Irani presented the report of the ad hoc committee to combat harassment and discrimination in the theory of computing community.   (See here for the report.)  There was an overwhelming vote to adopt their recommendations going forward.  It's good to see progress in addressing these community concerns.  Second, Shuchi Chawla will be the next PC chair, and she brought forward a plan to have SODA PC members be allowed to submit papers (with a higher bar) that was voted on favorably as well.

I suppose the last note is that Jon Kleinberg's invited talk was the conference highlight you expect a Jon Kleinberg talk to be, with interesting results and models related to fairness and implicit bias.

Thanks to SIAM and all the organizers for their hard work.