My take on computer science -- 
algorithms, networking, information theory -- 
and related items.
As a member of FODSI (Foundations of Data Science Institute -- an NSF funded institute with the aim of advancing theoretical foundations for data science), I'm self-interestedly posting the call for postdocs for this year. Two of the areas are a) Sketching, Sampling, and Sublinear-Time Algorithms and b) Machine Learning for Algorithms (which includes what I call "Algorithms with Predictions.") I'd…
HotNets has asked that we let people know that the 2021 presentations are available here . I'm using that an excuse to highlight our paper on Zero-CPU Collection with Direct Telemetry Access ( arxiv version here ), but really I want to highlight the talk by graduate student Jonatan Langlet (Queen Mary University of London) who, as is the nature of graduate students, did all of the real work, and…
In this post, we'll look at the natural problem of how to communicate an estimate of a real value in [0,1], using just 1 bit. The post is based on this paper (by Ran Ben-Basat of UCL and Shay Vargaftik of VMware Research and myself -- they helped also with the post) that appeared in ICALP last year. This question is motivated by various aggregation problems; multiple sending devices may measure a…
The last couple of years one aspect of research I've greatly enjoyed is getting back into networking, which is really due to my excellent (and patient) collaborators Ran Ben Basat (now at UCL, was a postdoc at Harvard) and Minlan Yu (at Harvard). Minlan and I are working to establish a larger-scale Networking+Theory (hopefully broadening to an even larger Systems+Theory) group at Harvard, working…
I was looking at today's Harvard Crimson, and noted that Harvard's shopping period looks ready to be vanished again . Shopping period is that wonderful Harvard tradition where students don't preregister for classes, but instead they choose classes after the first week, after having a chance to go to a lecture or two and see how they like it. I encourage students -- and faculty -- to push back…
I have had papers rejected, with comments of the form that the results seem too easy, and are at the level of a homework assignment. Generally, I think these reviewers miss the point. The fact that the results seem easy may be because the point isn't the derivation but the conception and framing of the problem. I actually think that generally it's an interesting subclass of good papers that can be…
We're having an online workshop on "Machine Learning for Algorithms" on July 13-14, with a great group of speakers. Announcement below, link at https://fodsi.us/ml4a.html , free registration (but please register in advance)! In recent years there has been increasing interest in using machine learning to improve the performance of classical algorithms in computer science, by fine-tuning their…
I wanted to give a pointer to a new preprint on bioRxiv on developing diagnostic assays for viruses, by (first author) Hayden Metsky (and others!) out of the Sabeti Lab at the Broad Institute (that I've been a bit involved with). Hayden, who somehow is both a computer science PhD and an expert in virology, has devised a novel software pipeline for developing diagnostics that are designed from the…
I wanted to link to a survey that is up entitled Committee on TCS Connections Questionnaire . They are examining modifying approaches to publishing in the theoretical computer science community, and they are focusing on FOCS/STOC. I personally approve of the idea of the committee, though I admit I am concerned that it's too little, too late. For years, FOCS/STOC has been a culture concerned with…
I have a loose association with the Broad Institute, an institute created so that "complementary expertise of the genomic scientists and the chemical biologists across MIT and Harvard be brought together in one place to drive the transformation of medicine with molecular knowledge." (See https://www.broadinstitute.org/history ) They recently passed an amazing milestone, having performed over 1…
The STOC workshop on Algorithms with Predictions was on Friday, and I thought it went really well! I can't speak for my talk, but the other 3 talks (Tim Roughgarden, Edith Cohen, Ravi Kumar) were fantastic and inspiring, and I really recommend them for anyone with an interest in "Beyond Worst-Case Analysis". The talks are all on Youtube . And the workshop page is full of useful links and…
This post both relates to some of the stuff I'll be presenting at Friday's STOC workshop on Algorithms with Predictions, but is also for future students in my classes, who sometimes wonder why I have them write code on theory material. (Somehow this might be a theme for a lecture in my grad class next semester, so maybe these are a first attempt at notes for the lecture. Comments and suggestions…
There's a whole new, interesting theory trend -- Algorithms with Predictions. The idea, spurred by advances in machine learning, is that you assume you have predictor that tells you something about your input. For example, in caching, you might have a prediction of when the item you are currently accessing will be next accessed. Of course, machine learning predictions aren't perfect. Still, you'd…
Reposting an important call -- these events have had big impact in the past! The CATCS will be hosting a virtual “Visioning Workshop” the week of July 20 in order to identify broad research themes within theoretical computer science (TCS) that have potential for a major impact in the future. The goals are similar to the workshop of the same name in 2008: to package these themes in a way that can…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
Michael O. Rabin Postdoctoral Fellowship in Theoretical Computer Science Deadline for full consideration: December 3, 2018. Applications can be submitted here: https://academicpositions.harvard.edu/postings/8512 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…