Research Life-Stories: Bobby Kleinberg

Our project continues with Bobby Kleinberg.

————————————————————

As an undergraduate I majored in mathematics and took only one computer science course. In fact quite a few of the mathematicians who influenced me were openly dismissive of computer science. Of course, throughout this period my brother Jon would continually talk to me about TCS — a subject he had chosen to pursue a couple of years earlier — so I was well aware of some of the mathematical gems the field contained. But I fell in love with topology and went to graduate school with my heart set on becoming a topologist.

Early in my first year of grad school, at one of the innumerable dinners in Central Square with officemates, we started debating the question, “What are the greatest mathematical discoveries of the 20th century?” My own candidate, Gödel’s Incompleteness Theorem, didn’t get much traction with this group. A common thread among the suggested alternatives was that a great deal of specialized knowledge was required even to understand the statement of the theorem, much less apprehend its significance. This struck me as a very sad state of affairs, and it still does. My favorite pieces of mathematics are those that apply deep methods to derive elementary consequences. I acknowledge the value of the more specialized papers that often enable those discoveries, but when a subfield of mathematics turns so far inward that its greatest discoveries are impenetrable to non-specialists, it is a loss for the mathematics community as a whole. My feelings on this subject were reinforced in 2010 when experts tried in vain to explain the work of Fields Medalist Ngô Bảu Châu to the mathematical public.

Though I didn’t know it at the time, this incident prefigured two years of growing disillusionment with the state of contemporary research on geometry and topology, which was increasingly focused on questions that I found to be excessively distant from geometric intuition. By the spring of my second year of graduate school, I was devoting my creative energy to an esoteric topic in algebraic topology whose importance I couldn’t explain even to myself; if the research were to succeed, I couldn’t point to a single mathematical consequence that might turn out to be of interest to me. It was obvious that a change was needed. (Aside: in hindsight, there were — and still are — plenty of wonderful topics of active research in geometry and topology that probably would have satisfied my intellectual cravings at the time. For example, I bet that if I had known more about Gromov’s work at the time, I would have been hooked on it.)

To “reboot” my search for a research topic, I discovered that I needed to give myself a break from grad school, and thus I started looking for a summer job. At the time this felt to me like an act of desperation, but it turned out to be the most pivotal decision of my career. I took a job at Akamai Technologies, which was then a start-up with just under 100 employees. Shifting from the algebraic topology group at MIT to the Mapping Group at Akamai felt, to me, almost as abrupt and disorienting as Dorothy’s arrival in the Land of Oz. After nearly two years of working painfully slowly, in near-isolation, on problems whose importance I couldn’t justify even to myself, I found myself, literally overnight, embedded in a team of people rushing at top speed to solve problems with a startlingly direct impact on reality: influencing, for example, the length of time it took for different users worldwide to load Yahoo’s home page. The sense of shared purpose, and the pride in working on a system used by billions of people, were intoxicating to me. Instead of spending one summer at Akamai, I ended up staying there for three years. This was one of the most productive and fulfilling periods in my career so far. While the work didn’t involve proving theorems, I was pleased to find that it exercised some of the same problem-solving skills that I enjoyed using when working on mathematics. And Akamai at that time was loaded with world-class theoreticians. Working alongside those people made it much easier, later on, for me to feel integrated into the theory research community when it became my intellectual home.

In 2002 I was still loving my job at Akamai, but I could tell that my future lay in more mathematical pursuits, so I returned to graduate school. I still faced a choice between theoretical computer science and topology; my industry experience had whet my appetite for TCS, but my love for topology had remained with me. Reflecting on the many factors that pushed me toward TCS over the course of the next year, three things stand out in my mind. The first is the extreme awesomeness of Santosh Vempala’s course on random walks and convex geometry and Madhu Sudan’s course on essential coding theory, the two most interesting courses I took that year. The second is my brother’s inspired decision to give me Motwani and Raghavan’s textbook “Randomized Algorithms” for Hanukkah the winter before my return to grad school. I’ve never asked him if he intended the gift as a form of gentle persuasion (at the time, all he said is that he thought I would enjoy reading it) but it certainly had that effect.

The third, and most important, thing that pushed me towards TCS was the experience of starting to do research with Tom Leighton. Having worked together quite closely at Akamai, Tom and I already had an easy, familiar relationship with each other. (How many grad students have had the experience of staying up all night working with their advisor, before they ever started collaborating on research?) Tom’s instincts as an advisor, I now realize, were miraculous. He knew how to bring out the best in me, using his fierce intelligence to inspire rather than demoralize me. In situations where I might say to my student, “I bet that X is true, and if so then Y seems to follow, but you should try to prove it,” Tom instead says, “Suppose for a second that X were true; then do you think we could prove Y?” (And, when questioned about why he believes X, he insists with a self-deprecating smile that he’s just speculating and would be excited to see a proof.) When I would give an overly sophisticated proof of some step and Tom came up with an elementary argument on the spot, instead of “Here’s an easy proof you missed,” he would say, “You’re so good at proving things that way. I’ll never get the hang of it, which is why this other proof is more natural for me.” And for any result that I could present to him, he could identify an extension that seemed even cooler, and potentially within reach.

My second paper with Tom introduced me to two topics (multi-armed bandits and algorithmic pricing) that became mainstays of my research in subsequent years. More importantly for me at the time, the paper “put me on the map.” To my surprise, people whom I venerated heard about the result and sought me out: Baruch Awerbuch called out of the blue to see if I wanted to help with a problem he had been thinking about; Éva Tardos approached me at a conference and said, “I hear you have a result I should find out about.” From that moment onward, my research became self-sustaining: each project I worked on generated more ideas for other projects, and more opportunities to meet new people and try absorbing their ideas.

About a year later, my wife Miranda asked me to describe my research over brunch at the Town Diner. (If you ever go to Watertown, Massachusetts, eat there! And order the sweet potato pancakes.) This was the first time I had tried to summarize all of my papers at once, and in the course of explaining the research to her it dawned on me that I had a Ph.D. thesis. After spending so many years worrying how I would choose a thesis topic, I marveled at how the topic had instead materialized through the (largely unplanned) accumulation of inter-related projects.

Reflecting on my transformation from a frustrated aspiring topologist to a fulfilled theoretical computer scientist, I am torn between two contrasting narratives that account for the pattern of events. In one narrative, I was adrift intellectually until I worked for Akamai. That experience guided me to a set of topics (routing, learning, pricing) that were both a natural outgrowth of the work and a firm basis for my Ph.D. thesis. In the other narrative, the process was unplanned and serendipitous. I joined Akamai to escape from grad school, not to gain a new viewpoint on research. I stumbled upon multi-armed bandits and algorithmic pricing, not because I perceived their potential as a research theme, but because Tom and I wanted to solve a cute problem he had heard about while visiting Ticketmaster. Instead of choosing a thesis topic, I decided to stop worrying about The Big Choice and work on individual problems that struck me as interesting, only to discover afterward that they could be presented as a unified contribution. Order or chaos? It’s impossible to choose between the two explanations. My research-life story, like everyone else’s, can only be explained with a healthy dose of both.