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.

Wednesday, December 05, 2018

NeurIPS 2018 Post

Today was my first day at a NeurIPS conference.  Advertising note, before my thoughts on the experience:
Tomorrow I'll be stationed at a poster 10:45 AM -- 12:45 PM @ Room 517 AB #169
A Model for Learned Bloom Filters and Optimizing by Sandwiching
and at the same time Diana Cai will be stationed at a poster I'm involved with:
Room 210 #26
A Bayesian Nonparametric View on Count-Min Sketch
Please stop by to talk to me if you're around -- Room 517 seems to be a bit off the beaten path and I'm concerned I'll be lonely with nobody to talk to.  And of course stop by to see Diana too.

NeurIPS is just huge.  It's like an extremely large academic conference (of 1000-2000 people) glued together to an extremely large industry conference (of more than that).   Just the academic part (talks and poster sessions, 3 parallel sessions for talks) is a lot, and then there's a trade show with booths from 50+ companies there too.

I think I'd like the academic part more if I was in the area -- I'm coming in from the algorithms perspective, and there's a bit of language gap.  It seems to me that conference suffers from some of the standard aspects of large conferences -- with scope and size that big, you have to look and find the things that are interesting and important to you, because a fair bit probably isn't.  And while I can't tell entirely myself, I'm told by others that, given the size, there's not a lot of "junk" -- the work seems good-on-average.  Also, given the conference size, it seems well organized -- staff managing the people flow, they keep things on time, plenty of room in the poster session (with appropriate food and drink stuff).  I can appreciate the work that must go into to making something this big work.

Because the conference is so big, I've run into a good number of "theory people" here.  As a percentage of attendees, we're probably small, but it's a good number because it's so big.  I kept running into people at the poster sessions, which was nice.

The trade show part is impressive in its own way.  If you didn't know AI was big, this would tell you.  All the big players are there, but there are at least a dozen machine-learning focused companies I haven't heard of, and that's not including the dozen or more consulting/Wall Street/hedge fund firms that are big enough into AI that they want to have a presence here.  I understand there's lots of networking and pre-interviewing and interviewing going on.  On the positive side, I feel like if I wanted to leave academia, I could land a job with a variety of AI-based companies, beyond the big companies.   

Hopefully tomorrow will be interesting as well.

Thursday, October 25, 2018

Rabin Postdoctoral Fellowship Advertising Post

Michael O. Rabin Postdoctoral Fellowship in Theoretical Computer Science

Deadline for full consideration: December 3, 2018.  Applications can be submitted here:

The Harvard John A. Paulson School of Engineering and Applied Sciences at Harvard University seeks applicants for the Michael O. Rabin Postdoctoral Fellowship in Theoretical Computer Science. The standard duration of the Rabin Fellowship is two years. Rabin Fellows will receive a generous salary as well as an annual allocation for research and travel expenses.

Past fellows are Mika Goos and Aviad Rubinstein and the current fellow is Alexander Golovnev.

We are looking for exceptional junior scientists in theoretical computer science, broadly construed. Rabin Fellows will be provided with the opportunity to pursue their research agenda in an intellectually vibrant environment with ample mentorship. While interaction with Harvard faculty, students, and visitors is encouraged, Rabin Fellows are free to pursue their own interests. Candidates are required to have a doctorate or terminal degree in Computer Science or a related area by the expected start date.

Required application documents include a cover letter, research statement, CV (including a list of publications), and names and contact information for three references. We recommend that papers mentioned in the CV be available online on your homepage or on electronic archives. Applicants will apply on-line at the above address. We encourage candidates to apply by December 3, 2018, but applications will be accepted until the position is filled.

Harvard is an equal opportunity employer and all qualified applicants will receive consideration for employment without regard to race, color, religion, sex, sexual orientation, gender identity, national origin, disability status, protected veteran status, or any other characteristic protected by law.

Monday, September 10, 2018

Lenore Blum interview

I've just read this, and do not have any specific comments, but I thought this interview with Lenore Blum on her recently announced resignation from CMU would be something of interest to the larger community.  (Thanks to Margo Seltzer for forwarding it to me.) 

Monday, July 23, 2018

Symposium on Simplicity in Algorithms, Submission Server

A reminder that the deadline for SOSA 2019 is August 16.  The submission server is live and running (and we already have some submissions!).  The easychair link is , and general information can be found at .

Friday, June 22, 2018

STOC Lunch Sign-ups, and Reminder

Just a reminder that next week is the 50th STOC in Los Angeles!  You can still come and register on site, so please come -- the program is STOC-full of good stuff.  Especially all you Californians -- no excuse not to be there.

An innovation introduced at last year's STOC was the junior/senior lunch meet-up.  Senior people sign up to meet with junior people over lunch at a day of their choosing, and then (three) junior people (undergrad/grad/postdoc) can sign up to go to lunch with the senior person.  The goal is to increase chances for junior people to get to network with more senior people, something that we hard heard was lacking previously.  (Everyone buys their own lunch.)  You can find the on-line sign-up sheet here.  Please go on and sign up as soon as you can!