Interview with Sampath Kannan

On July 1, Sampath Kannan became the Simons Institute’s new associate director. A UC Berkeley alumnus (PhD 1989), Sampath is the Henry Salvatori Professor in the Department of Computer and Information Science at the University of Pennsylvania, where he also served as associate dean for academics in the School of Engineering and Applied Science. He was previously the division director of Computing and Communication Foundations at the National Science Foundation. We sat down with Sampath to discuss his research interests, vision for his new role, and perspectives on how developments in AI are transforming the field of theoretical computer science. We traverse some memory-lane Berkeley in the 80s territory too.
 

How did you get interested in theoretical computer science?

When I was in high school, my brother who was in college was trying to prove the four-color theorem and filled pages and pages of paper with maps/graphs and colorings of them. I remember being fascinated by the simple (in hindsight) fact that the problem was the same whether you thought about it on maps or on graphs.

As an undergraduate in an era before it was possible to get a computer science degree, I enrolled in IIT Bombay to study electrical engineering, and again encountered graphs in some way when learning about solving for currents and voltages in resistance networks. But when I entered graduate school in Princeton, I was still not completely set on theory research. In fact, I began working with Richard Lipton on applied problems about VLSI layout, which might have had graph theory at their foundations. But personal circumstances made me switch to doing the PhD at Berkeley. I was really fortunate to have Manuel Blum as an advisor, and be close to the center of the exciting revolution in cryptography and complexity that was happening then. My research on program checking both derived a lot from this ferment, and ended up contributing to it. While this had very little to do with graph theory, the area that drew me into theory, I was able to do some work on the side on problems in computational biology that did involve graph theory.
 

What research questions are you interested in right now?

Like many theorists, I am attracted to specific problems rather than to general research directions. However, having had a career of 35 years working on several different threads of research, it is pretty easy for me to relate any new problem I work on to one of these threads.

Thus, I can say that I am interested in certain threads that run throughout my career, although I am not always working on all of them. These include program checking, computational biology, streaming and sublinear algorithms, sorting and searching, and computational fairness. Most recently I have been thinking a lot about computational fairness — how algorithmic decision-making in areas such as recidivism prediction, college admissions, and hiring might discriminate against groups of people, and how such discrimination could perpetuate inequalities across generations. Of course, we look at these problems from a highly simplified, mathematically tractable viewpoint.
 

You were a graduate student in theory at UC Berkeley, working with Manuel Blum. What are some of your best memories of that time? How has the environment evolved or stayed the same since you last lived here? And what, if anything, do you think it is about Berkeley that makes it such a potent place for theory?

Manuel was an amazing person to have as an advisor. I learned from him what it takes to formulate a problem to solve. He was one of the best at formulating entirely new questions and directions in theoretical computer science. From him, all of his other students and I learned the joy of formulating elegant yet impactful questions that one could have a hope of solving. Manuel also honed our ability to articulate our ideas. In meetings with him, one always had to explain from scratch the problem one was working on as well as the ideas and theorems up to that point. This got increasingly challenging as you made progress on the problem, but was excellent training.

The obvious reason that Berkeley has been an excellent place for theory is that it has had some of the best faculty in the world throughout the brief history of theoretical computer science. Of course this has meant that it has attracted some of the brightest graduate students, who have gone on to be leaders in the field. A less tangible reason is that Berkeley faculty have always encouraged students to be independent from day one. That is why you see many papers whose authors are all students, and often students with different advisors. My first paper was written with my office-mates Steven Rudich and Moni Naor; hanging out and thinking about problems with them and other students in the office was one of the highlights of the Berkeley experience.

Perhaps, the ability of students to work together by themselves is one of the biggest reasons why Berkeley has remained a potent place for theory.
 

In the last few years, machine learning and AI have come to dominate the cultural and technology landscape. How are these changes impacting TCS as a field, and how is the Simons Institute responding?

One of the interesting facts about theoretical computer science is that it has been the first subfield of computer science to “make friends” with other disciplines. Historically, theory has forged the first connection with physics (quantum computing), biology (computational biology), economics (mechanism design, algorithmic game theory), and of course much more obviously with statistics, operations research, and network science. The Simons Institute has been at the forefront of continuing this record with its recent programming on connections with neuroscience, psychology, and the brain, with animal communication, and with understanding reproducibility of scientific research.

While machine learning has also been forging connections with other disciplines in the last decade or so, theory remains essential in arriving at an understanding of the scientific principles underlying other disciplines.

At the Simons Institute, we have been pursuing the connection with machine learning vigorously over the last several years. Machine learning was closely connected with theory at its inception. Over the recent decades, as it has become a powerful tool in many disciplines, it has become urgent to understand machine learning algorithms from a theoretical perspective and answer questions such as: How can they be made robust to manipulation? Do they protect the privacy of the data on which they are trained? Are they fair? Are the results they produce explainable? What more are they capable of than what they are currently doing? I expect the partnership between theory and ML to be a very fruitful one for years to come, and the Simons Institute will actively foster this relationship.
 

What do you see as the particular challenges and opportunities for the Simons Institute in its second decade? And what is your vision for what you’d like to accomplish in your new role?

The theoretical computer science perspective is incredibly powerful and has been fruitfully brought to bear on many fields of inquiry. The Simons Institute should continue to play a leading role in facilitating such bridge-building. We are already doing this vigorously. For example, in the last year we had a summer cluster on AI, Psychology, and Neuroscience and a workshop on Decoding Communication in Nonhuman Species. This year we are looking at machine learning and large language models from a theoretical perspective, asking: Can we build such systems to satisfy various normative societal goals? Theoretical computer science has had a brilliant track record over the last several decades in precisely this sort of thing, taking seemingly unquantifiable desiderata such as security, privacy, or fairness and providing an essential mathematical framework for reasoning about them. I expect that the program on LLMs and others in the future will continue this aspect of the contribution of TCS. Finally, and most importantly, the central mission of the Simons Institute is to help “recharge the font” — to continue to make progress on exciting questions at the core of theoretical computer science.