The Heidelberg Laureate Forum has a single purpose: To provide some of the brightest minds in mathematics and computer science with the space and time to make connections and find inspiration. The HLFF Spotlight series shines a light on some of the brilliant individuals attending the event.

---

Robert Endre Tarjan is the recipient of the 1982 Nevanlinna Prize, which he received for “devising near-optimal algorithms for many graph-theoretic and geometric problems for the development and exploitation of data structures supporting efficient algorithms, and for contributing several algorithmic analyses of striking profundity and elegance.” 

He also received the ACM A.M. Turing Award in 1986 together with John E. Hopcroft “for fundamental achievements in the design and analysis of algorithms and data structures.”

What first inspired you to pursue a career in your field?

When I was a child, I loved science fiction. I wanted to be the first person on Mars. When I was 12 or so, I discovered Martin Gardner's Mathematical Games column in the Scientific American and became transfixed by mathematical puzzles, mathematical games, and other board games. In the 8th and 9th grades, I had an amazing mathematics teacher. He taught us Peano's axioms, including proofs by induction. In high school, I had the opportunity to work during the summers in a small medical statistics research group, using IBM punch card machines, notably a calculator programmable using a plugboard. I attended a summer science program during which we had an opportunity to program a real digital computer, in FORTRAN, an eye-opening experience. During my senior year of high school, I took a couple of mathematics classes at Harvey Mudd college, which was nearby, and when I went to Cal Tech as an undergraduate, mathematics was the obvious choice for a major. During the summers of my undergraduate years (1965-1969) I continued to work in the statistics research group, which by then had a real computer. In my spare time, I used the computer to enumerate 4-colorings of so-called "reducible configurations" of planar graphs. The idea of reducible configurations is one of the two key ideas that later led to the computer-aided proof of the four color theorem, although I didn't have access to the computer power to pursue the problem seriously, nor did I know about the second key idea, which is a way to obtain a finite, complete set of reducible configurations, thereby reducing the problem to a finite calculation. When choosing a graduate school and major, I knew that I wanted to do mathematics related to computation, specifically dealing with discrete objects like graphs. I applied to both math and computer science programs, and chose computer science at Stanford. It was a great choice.

What is the most exciting or meaningful development happening in your field right now and why?

My field is the design and analysis of data structures and combinatorial algorithms. The most exciting developments recently are the use of techniques from continuous optimization, notably so-called "interior point" methods, to solve classical graph optimization problems such as maximum flow and minimum-cost flow much more efficiently than was previously known possible. These new results combine many different sophisticated ideas, including new data structures and new ways of decomposing graphs. So far, all these new algorithms are only "efficient" in theory; they are very far from being practical. But these results are all very new, and will be improved.

What advice would you give to young researchers still at the beginning of their careers?

Choose a field because you love it. Research is hard. Be prepared to fail many more times than you succeed. Follow your own path; ask your own questions. Asking the right question is the start of great research. Have more than one problem to work on, so that when you are stuck on one you can turn to the other one. Teach. It is the best way to learn new material, and interacting with students is (at least for me) a huge motivator for doing research.

What do you enjoy most about attending the Heidelberg Laureate Forum?

The human interactions, both with the young researchers and with my colleagues, many of whom (those in mathematics and even many in computer science) I only have a chance to see at the HLF.