People of ACM - Jelani Nelson

October 5, 2021

How did you initially become interested in the design and analysis of algorithms?

I've always been a gamer; my earliest memory of gaming was playing a Nintendo Entertainment System my parents bought me for my fourth birthday. From there I expanded my gaming to include other video games, computer games, card games, and board games. Eventually in 2004 as a junior at MIT, a couple of friends (Hubert Hwang and David Pritchard) introduced me to the wonderful world of competitive programming—yet another game for me to dive into. I had already taken an undergraduate algorithms course in 2003, but it wasn't until 2004—training myself and competing on TopCoder—that I really immersed myself in algorithms. Competitive programming was, to me, just the next game, and I spent hours and hours every day on it, seven days a week, for years. Algorithms is a nice mix of computer science and rigorous mathematics, both of which I had always enjoyed, and thus the topic greatly appealed to me. To this day, I still find joy in both the aesthetics, writing and simplifying proof of a nice theorem, and the practice, writing and simplifying code that incorporates nontrivial algorithmic observations.

What is an area within the theory of computation you are working on now? What do you hope will come out of your current line of inquiry?

I work quite a bit on "sketching" algorithms; a sketch is simply a compressed representation of data that allows for answering queries about that data (sometimes while also supporting data updates). As suggested by the word "compressed," we want sketches whose memory footprint is far less than what would be required to store all the data. I'm happy to be working in a subarea of theoretical computer science that already has found many practical applications; a Google search for "engineering hyperloglog" reveals interest in the topic from big tech companies such as Facebook, Google, and beyond (Hyper Loglog sketching algorithm for estimating the number of distinct elements in a set, which supports inserting new elements into that set). Given that ideas from this space are already being used widely, my hope is simply that we will find new domains to have applied impact while also developing new theory. For example, work over recent years has found some interesting crossover between ideas in sketching and differential privacy. In fact, I recently (since June 2021) have started spending a day a week as a Research Scientist at Google, where I'm exploring some problems in this space motivated by applications.

Will you tell us a little about the Committee for the Advancement of Theoretical Computer Science? Do you think the field is attracting enough new students, research grants, etc.?

As outlined on the CATCS website, the goals of the committee include attracting more funding to theoretical computer science (TCS), and developing and promoting materials about TCS to educate those outside the field. I think our field is healthy and still attracting great students, and I also get the sense that we're seeing an increasing number of students attracted to areas at the boundary of TCS and other areas, e.g., foundations of machine learning. Regarding grants, a large funder of TCS research in the US is the National Science Foundation (NSF). Here's the latest budget request for NSF’s Directorate for Computer and Information Science Engineering (CISE), which funds computer science research in all areas. Within the budget, you can see the amount requested for the TCS division (which is called "CCF") for 2022 is $218.5 million, though the amount allocated may differ from what is eventually allocated in the federal budget. By googling for these budget documents over the past five years, we find the amounts allocated to TCS (adjusted for inflation) look fairly flat. I do hope funding of TCS increases.

There are many new exciting directions our community is pursuing, which are outlined in a report that was developed after a visioning workshop involving dozens of senior members in our community. TCS has developed key ideas with major impact in the US and the world, from cryptography, to the foundations of machine learning and data science, to massively scalable algorithms that power the world's largest tech companies, to private mechanisms employed by the latest US Census, and more.

Many deep developments, e.g., in the theoretical foundations of quantum computing, are poised to have major impact once developments in hardware catch up with theory. It is true that not all theoretical pursuits bear fruit in practice, but as any Silicon Valley venture capitalist can tell you, you only need a couple of unicorns after placing many bets for the overall returns to be massive, and the TCS ecosystem has a track record of producing these "research unicorns." If the US doesn’t continue being at the forefront of innovating in the foundations of our field, then our competitors will—so this is really a matter of national security.

What is the goal of AddisCoder, the summer program you founded in Ethiopia for high school students that introduces them to programming and algorithms? What have you learned from this experience that could be applied to launch similar programs in other countries?

As mentioned, my introduction to algorithms was via the lens of a gamer, through competitive programming. One regret is that I only discovered this world later in life, as a junior in college. I want to expose this beautiful world to the youth, as I wish I had been exposed to it at that age. What I've learned from the 500+ students we've taught so far is that there are many students who do appreciate the exposure, and knowing that I'm spreading that joy keeps me going with the program. Regarding launching it in other countries, one of our summer 2020 teaching assistants was to fly in from Rio de Janeiro, and he was interested in spreading the program to Brazil; unfortunately that did not materialize, as we had to cancel the 2020 and 2021 editions of the program at the last minute due to the pandemic. We hope to spread the program's impact soon, though, and indeed we have already expanded to a few other cities in Ethiopia via offshoot programs.

What advice would you offer a younger colleague who is just starting out in the field?

It depends how young we're talking about. If you're pre-graduate school, my advice is to do as much as you can to self-train. There are many more educational resources freely available online now than when I was your age! To someone who is already in graduate school or beyond, my advice is to focus on doing good work: quality over quantity. I personally would rather publish no paper than an unimportant paper. Make sure you deeply understand the motivation behind the problem you're studying; if there are problems with the motivation, don't work on it! Also, do not confuse the difficulty of a problem with its importance. There are hard problems that are important, but there are also hard problems that are unimportant. Similarly, there are important problems that have yet-to-be-discovered easy solutions.