The HLF Portraits: Bob Tarjan
Formal Metadata
Title 
The HLF Portraits: Bob Tarjan

Title of Series  
Author 

Contributors 

License 
No Open Access License:
German copyright law applies. This film may be used for your own use but it may not be distributed via the internet or passed on to external parties. 
Identifiers 

Publisher 

Release Date 
2017

Language 
English

Content Metadata
Subject Area  
Abstract 
The Heidelberg Laureate Forum Foundation presents the HLF Portraits: Bob Tarjan; Nevanlinna Prize, 1982 & ACM A.M. Turing Award, 1986 Recipients of the ACM A.M. Turing Award and the Abel Prize in discussion with Marc Pachter, Director Emeritus National Portrait Gallery, Smithsonian Institute, about their lives, their research, their careers and the circumstances that led to the awards. Video interviews produced for the Heidelberg Laureate Forum Foundation by the Berlin photographer Peter Badge. The opinions expressed in this video do not necessarily reflect the views of the Heidelberg Laureate Forum Foundation or any other person or associated institution involved in the making and distribution of the video. Background: The Heidelberg Laureate Forum Foundation (HLFF) annually organizes the Heidelberg Laureate Forum (HLF), which is a networking event for mathematicians and computer scientists from all over the world. The HLFF was established and is funded by the German foundation the Klaus Tschira Stiftung (KTS), which promotes natural sciences, mathematics and computer science. The HLF is strongly supported by the awardgranting institutions, the Association for Computing Machinery (ACM: ACM A.M. Turing Award, ACM Prize in Computing), the International Mathematical Union (IMU: Fields Medal, Nevanlinna Prize), and the Norwegian Academy of Science and Letters (DNVA: Abel Prize). The Scientific Partners of the HLFF are the Heidelberg Institute for Theoretical Studies (HITS) and Heidelberg University.

Related Material
00:00
Point (geometry)
Inheritance (objectoriented programming)
Term (mathematics)
State of matter
View (database)
Neighbourhood (graph theory)
Video game
Musical ensemble
Family
Number
02:08
Point (geometry)
Axiom of choice
Trail
Statistics
Context awareness
Observational study
Open source
State of matter
Multiplication sign
Direction (geometry)
Decision theory
Virtual machine
Propositional formula
Neue Mathematik
Computer programming
Wave packet
Neuroinformatik
Mathematics
Goodness of fit
Energy level
Software testing
Unterhaltungsmathematik
Fiber (mathematics)
Physical system
Social class
MIDI
Artificial neural network
Prisoner's dilemma
Gradient
Plastikkarte
Bit
Library catalog
Axiom
Process (computing)
Integrated development environment
Logic
Universe (mathematics)
Computer science
Statement (computer science)
Video game
Hill differential equation
Right angle
Whiteboard
Game theory
Family
Reading (process)
Spacetime
Library (computing)
12:32
Axiom of choice
Logical constant
Complex (psychology)
Open set
Inverse element
TuringMaschine
Computer programming
Neuroinformatik
Explosion
Different (Kate Ryan album)
Office suite
Error message
Collaborationism
Potenz <Mathematik>
Mapping
Gradient
Computer simulation
Maxima and minima
Median
Computer scientist
Category of being
Arithmetic mean
Process (computing)
Graph coloring
Quicksort
Mathematician
Point (geometry)
Student's ttest
Number
Element (mathematics)
Term (mathematics)
Authorization
Selectivity (electronic)
Data structure
Pairwise comparison
Graph (mathematics)
Artificial neural network
Counting
Basis <Mathematik>
Total S.A.
Depthfirst search
Cartesian coordinate system
Planar graph
Symbol table
Integrated development environment
Network topology
Game theory
Asymptotic analysis
Graph isomorphism
Run time (program lifecycle phase)
Digital electronics
State of matter
Interior (topology)
Multiplication sign
Decision theory
Direction (geometry)
View (database)
1 (number)
Set (mathematics)
Primitive (album)
Mereology
Mathematics
Bit rate
Recursion
Algorithm
Moment (mathematics)
Automaton
Flow separation
Connected space
Linearization
Computer science
Selforganization
Right angle
Resultant
Row (database)
Dataflow
Inverse function
Functional (mathematics)
Divisor
Random access
Virtual machine
Login
Graph coloring
Field (computer science)
Theory
Hypothesis
2 (number)
Moore's law
McCarthy, John
Natural number
Operator (mathematics)
Software testing
Differential equation
Task (computing)
Hazard (2005 film)
Projective plane
Bound state
Mathematical analysis
Analytic set
Planning
Logic
Vertex (graph theory)
Einbettung <Mathematik>
Object (grammar)
Abstraction
26:34
Axiom of choice
Complex (psychology)
Dynamical system
Context awareness
Multiplication sign
Decision theory
Bell and Howell
Insertion loss
Mereology
Neuroinformatik
Mathematics
Different (Kate Ryan album)
Position operator
Algorithm
Channel capacity
Search tree
Gradient
Binary code
Computer scientist
Maxima and minima
Category of being
Process (computing)
Computer science
Right angle
Quicksort
Resultant
Point (geometry)
Dataflow
Trail
Functional (mathematics)
Student's ttest
Mass
Field (computer science)
Hypothesis
2 (number)
Operator (mathematics)
Linear programming
Theorem
Data structure
Associative property
Compilation album
Condition number
Form (programming)
Dependent and independent variables
Graph (mathematics)
Inheritance (objectoriented programming)
Information
Chemical equation
Mathematical analysis
Interactive television
Division (mathematics)
Depthfirst search
Cartesian coordinate system
Integrated development environment
Software
Personal digital assistant
Network topology
Universe (mathematics)
38:59
Axiom of choice
Context awareness
Group action
Code
Multiplication sign
View (database)
Decision theory
Direction (geometry)
1 (number)
Bell and Howell
Data analysis
Food energy
Information technology consulting
Computer programming
Neuroinformatik
Mathematics
Mechanism design
Strategy game
Different (Kate Ryan album)
Semiconductor memory
Information security
Position operator
Physical system
Area
Algorithm
Concentric
Speicherhierarchie
Bit
Instance (computer science)
Perturbation theory
Surface of revolution
Sequence
Connected space
Data mining
Data management
Digital rights management
Message passing
Process (computing)
Telecommunication
Computer science
Right angle
Quicksort
Writing
Resultant
Spacetime
Point (geometry)
Trail
Random access
Virtual machine
Student's ttest
Coprocessor
Scalability
Theory
Field (computer science)
Number
Latent heat
Term (mathematics)
Internetworking
Theorem
Acoustic shadow
Data structure
Artificial neural network
Weight
Cartesian coordinate system
Integrated development environment
Software
Personal digital assistant
Universe (mathematics)
Statement (computer science)
Video game
Codec
Abstraction
52:47
Internet forum
Bit rate
00:00
[Music] professor introduced me to yourself as an eightyearold where are you living who are your parents what is your childhood like at that point I was living in Southern California in Pomona my dad was superintendent of a state mental hospital for the mentally retarded now called developmentally disabled so he was a superintendent we had a house on the hospital grounds big old Spanish house my mom was a housewife there was an orange grove behind the house it was kind of old old Southern California a lost world above your knees I'm guessing a pretty nice happy childhood in terms of circumstances I don't know I can't complain I had a brother we had some small number of kids in the neighborhood so we used to run around play outdoor sports indoor sports toys an Indian's baseball football and so long invisible life oh you guys the kind of people who have strong views about what who you should be what you should become are they pushing you either ethic ethically or or professionally at a young age well my father was a Hungarian refugee a Jewish refugee from World War two so he lost his parents and his brother in the war he and his sister got out and he was a doctor he had to retrain himself after he got in this country had to redo his internship in US yes yes so he met my my
02:12
mother was born in the US he met her in nursing school because he was teaching at the nursing school and she was there and they got married in those days you couldn't be in if you were married so she dropped out of nursing school married him then he joined the US Army because he wanted to help against the Nazis so he the first thing that they did was they sentient a Utah where they had a prisoner of war camp because he spoke fluent German so he was interviewing German prisoners of war and then eventually he went into the Pacific front so he was a doctor in the Pacific front he never did get back to of course that's here of where you're born that was before it was born yes so my mom moved to San Francisco while he was in the Pacific and then he came back and they loved California so he moved to Southern California got the job with the state government that I was born there in 1948 so three years after them I made sure to do that one more I have a younger brother Jim so the two four years younger just the two many kids are their strong ambitions in the household that you feel as a child or are you pretty much led to develop yourself intellectually on your own well I think my dad always valued intellectual achievement on top of which he was worried in this hospital for developmentally disabled and he was working with the psychologists and so on so they had like intelligence tests and what and they tried all these things out on me it was scoring off the top of the charge so he was there was clear that what he valued was intellectual achievement I was what are you reading what are you yourself fellows an eightyear all I loved science fiction actually I wanted to be the first person on Mars in those days that was kind of the Space Age right so I would have been 1956 right eight years old do you think there's really a relationship between that kind of fascination all those so many boys particularly have been interested in science fiction and a kind of formulation of thinking about the future of science and participating in it or is that not really it's possible the next thing that happened to me the way I got into mathematics and computer science actually well the first thing that happened to me was my mother introduced me to the public library in Pomona where I grew up so I spent a lot of time reading and then I discovered Martin Gardner's column in the Scientific American mathematical games that was probably when I was in fifth or sixth grade something like that and then I became fascinated by mathematical games board games mathematics so I sort of switched my interest from outerspace to mathematics and I well I went to a biscuit ball school kindergarten through sixth grade at very small small classes and it was a wonderful environment then I switched into the public school and junior high school but they had a tracking system so the smart kids got really good teachers and in particular I had a mathematical a math teacher named mr. wall who was this rotund guy used to sit back in this chair and challenge us he gave us the new mathematics before there was such a thing as a new mathematics he taught us pianos axioms all kinds of stuff elgyn logic and so on so I'm sorry he's in school that was in the public Skynet but actually yes so I was completely consumed by mathematics at this point and I got a great education even though it was in the public school I was before proposition 13 when California still had money to spend on education and I mean it was Pomona was not a Beverly Hills there were plenty of Hispanics and blacks and so on and but the education was really good you were all pushed in the direction yes at least at least for those of us so those were right it was a really good thing yes just because it's a rich life and a short amount of time to talk about it I need to get you into high school and I need to pitch with the college what is going to publish our high school shaping you what is the level of your intellectual interest even
07:22
passion at that point well I'll buy that so my father was superintendent at the State Hospital which when he got there was basically devoted to taking care of these people but not trying to improve their lives and he was rising yeah we're housing but he was interested in improving their lives and he's set up a research center within the State Hospital so they were doing a lot of statistical analysis and stuff and I got a chance to actually work there during the summers I hesitate to call it programming originally because it involved IBM punch card machines that were not even but yes yes so I worked there every summer starting maybe eight the ninth grade something like that and that kind of got me interested in pre computers if you will you gotta make a choice from University how are you going how are you going about making that decision well again when I was a kid my dad again cuz he was interested in research on Miller retarded kids he was working with  Pauling was a Caltech at that time studying fetal ketonuria which is you can't process a certain amino acid and it produces mental retardation so you can treat it with diet but anyway Alliance Linus Pauling came over to the house and I played mathematical games with him and he left a catalog for Caltech so that was one possibility and also when I was in high school I kind of ran out of math courses to take so I started taking math courses at Harvey Mudd while I was still at in high school so I applied to both Harvey Mudd and Caltech and ended up going to Caltech which was probably an easy decision it was a bigger school it was a little I knew Harvey Mudd a little bit at the time it seemed like a straightforward decision both very challenging right places I had I if I had it to do over again I would have applied more broadly and looked at liberal arts universities I think because I think I got a great education at Caltech but it was not very rounded it was all men at the time right and it was incredibly intense it was really challenging high school was easy but right not accused of that University no so it was a great place to be from I made a lot of good friends right but after that I mean grad school was relatively easy so when when I got to I got the Cal Tech I was determined to be a math major so I okay was a math major but I'd done a lot of programming I was in a summer science program where I did a lot of programming I took all the stuff that passed for computer science courses when it came to grad school I applied both the math departments into computer science departments ended up going to Stanford in computer science so math throughout Caltech principally although um is who Computer Studies there weren't really any computer science departments in the country at that point they were just starting to be formed in the mid to late 60s I think maybe Purdue was the first one and mostly they started out as graduate programs are you aware of Stanford of having particularly good training in computer science or are you still a California in the statement in California how how selective was your decision to go to Stanford well I applied to Stanford in computer science Berkeley and math Wisconsin and math and Cornell and computer science of fibers so if you had only gotten into math programs you would have I would have done well yes except the what I've done throughout my career you can think of as mathematics but applied the computer science problem okay it was always kind of what I wanted to do although Stanford has a great reputation in artificial intelligence so I kind of was thinking I would do the mathematical side of artificial intelligence whatever that was in wade was not having to make the choice but doing applied mathematics in that context yeah I I'm happy I went into a computer science department but I think I would have been also happy going to a math to Birdman there we are at Stanford kind of the right place at the right time if we look if it was one of the good places to be in those days yes tell me how you're formulating or who is formulating for you the study program in this still
12:34
relatively young field how was that being change back when I was in high school I got interested in the four color problem how can you call her countries on a map so that any two countries touching have to be different colors so this was a notorious unsolved problem at that point it finally got solved in 1976 by Hawking and Appell Appel and Haken Apelles Sun actually is a professor in our department at Princeton but it was unsolved back when I was looking at it and I was working on it not with enough computational power and not with all the mathematical tools but this was the sort of thing I was yeah it was the task you were interested in so it raised questions about planar graphs it's planar graphs that you want to color because a map is a planar right object and I the summer before I went to Stanford I was working at Lawrence Livermore Lab actually in my spare time I did a lot of reading anatomica theory and so on so I was thinking about automaton complexity and so on and I had this vague idea to go into artificial intelligence I got to Stanford I took lots of courses artificial intelligence was very fuzzy it wasn't so clear how to combine it with mathematics I talked to Michael ARB it was a automata theory professor in the EE Department at Stanford and he said don't do what tammana Theory do something more like complexity and then Don Knuth was it Stanford big algorithms guy so a few minutes do I mean you got you got it all with him that's true that's true amazing organ player hazard the things so I took a lisp programming course symbolic programming with John McCarthy and he gave us a final project and there were choices but one choice was given a graph is it planar devised an algorithm to the test whether a graph is planar or not so I knew about planar graphs they knew about Curtis Keys criterion which is the mathematical way to resolve this question but it doesn't produce a good algorithm but I found an algorithm in the literature that like program and I actually succeeded in doing the project and the people who tried that problem I think I was the only one who came up with anything any good so after my first year I had this exposure to plain arity testing I had passed all my exams so I was ready to do research John Hopcroft came to Stanford on sabbatical so he and I started talking about graph problems graph algorithms started exploring the idea of depthfirst search and what one could do with it and then things kind of explode I'm interested in the nature of collaboration in your field so one seeks out the other because an understanding of a common interest how did your you're working together as I recall we were in an office together and we just started talking about problems I was interested in graph algorithms and he was interested in graph algorithms so we just started bouncing ideas of each other computer science I think is a very collaborative field more so maybe than mathematics right certainly I really enjoy collaboration in it it goes in different directions with different people there's no right one right path but you're clearly developing the solid intellectual relationship over a shared interest yes at this point is this going to be the basis of your dissertation yes yes yes so we explored depth first search on simpler problems we figured out an algorithm to divide a graph into by connected components which means are there individual vertices whose removal breaks the graph at the right of several pieces then we looked at tried connected components and we looked at planarity testing it's turned out to be really hard we came up with a not quite linear time algorithm in log n time outer than were innocent number of vertices and then I spent a long time finally came up with a linear time algorithm for plain error T and that was the main part of my thesis to speak of a Eureka moment and essentially that kind of a moment happens around a decision to publish are you publishing before you actually do the dissertation yes because we we did some of this work on depthfirst search we were looking at graph isomorphism for planar graphs and various graph problems so we published some of the early work on depthfirst search while I was still a pH the whole process were went pretty fast though it was only a student for two years and one record or something like that really nine quarters which was the minimal residency requirement so you'll stand for graduate school for relatively a short time quite short when is your doctorate given to January of a 72 okay can you describe for me the state of knowledge in the fields are about to enter full time with a PhD at this point what is what is known and even about algorithms at this point I suppose there were plenty of outer rhythms but not a lot in the way of algorithmic analysis and it wasn't so clear what the right way to do analysis was so one thing that John and I concentrated on was ignoring constant factors getting the asymptotic growth rate and really worrying about efficiency so Knuth for example really paid attention to constant factors and even second order terms and was looking at very exact and exacting bounds for algorithms which is beautiful if you can
19:35
actually get results but it's really tough to do if you can pay a little less attention to the details abstract things go to a very simple computer model random access machine and just count steps and ignore constant factors this turns out to be a very powerful way of looking at algorithms so this was our point of view and then there were plenty of algorithms but no analysis so the field was kind of wide open at the time I mean when I was at Stanford also we didn't just look at graph algorithms we looked at selection there's a wonderful story about well it was a great environment because there were lots of Torii Award winner at Stanford I spent a lot of time with Bob Floyd who was my thesis advisor and Knuth and Hopcroft and dick Karp was at Berkeley and gene Waller was at Berkeley and Manny Blum was at Berkeley and Manny Blum came to visit talking about finding the median so given in numbers you want to find the one that's in the middle that is the one that's half of the numbers are smaller and half of the numbers are bigger you can do it by sorting all the numbers of picking the one in the middle that takes n log in time and that's a lower bound if you're just doing binary comparisons but can you do it faster so Manny had this idea for doing it faster and he talked to Bob Floyd and Rivest was Floyd's student and various of us got talking together and eventually we came with but the linear time way to do it so we ended up with a 5 author papers want pratt was on that paper too this is the first time that this approach has been the linear approach has been solved if you will nobody knew how to do it faster than sorting yes yes so the game was to come up with algorithms that had faster running times asymptotically that previous algorithm so for example in the planarity testing situation they are rhythm that I had implemented as a grad student was quadratic time although the paper didn't say anything about the running time to get it down to linear time was the best possible because you have to look at all the data and people were kind of amazed both at the fact that you could actually do it in linear time and what basically does that help us do I mean what's applications of planarity testing there are quasi applications I mean the justification is any linear circuits it's basically a planar graph so if you want to lay it on your circuit without crossings it's a plain arity testing problem but it's more than to land the techniques have many different applications and if you can embed a graph in the plane which are outer them do it helps in doing other things like if you want to find shortest paths or flows between points in planar graph it helps to have an embedding I'm gonna ask a broad question before I get you in your career to the next step and that is so often once these particularly mathematicians but also analytic computer scientists or mathematicians essentially use terms like beautiful and elegant love overuse turns but I am straining minute in differences something because if a solution is beautiful there must be solutions that are considered not beautiful yes so what what is in general meant by that describe a an algorithm as beautiful or elegant beautiful is in the eye of the beholder elegant to me means simple but deep so I would give you an example there's an algorithm that I've now been studying for 40 years or more still studying the disjoint set Union algorithm which solves a very simple problem we're given a collection of Singleton's we got two operations that they're gonna get grouped together in two sets and the sets become bigger and bigger so one operation is given elements in two sets put the two sets together into one set second operation is given an element find the set containing it that's all lots of that's this one has lots of applications actually so there's a beautiful data structure that uses trees and linking trees together which has the property that the total running time is the number of operations times inverse Ackermann function so what is inverse Ackermann function in the early 30s when logicians were studying computation computational models what do you need to define universal computation touring machine is an example but there are other ones general recursive functions this is another one that's equivalent to Turing machine so Ackerman invented this function to show that primitive recursion which is one variable recursion is not sufficient to allow you to do possible computations we need multivariable right recursion so this Ackermann function generalizes it diagonalizes over primitive recursive functions so it's kind of like a hyper hyper hyper exponential you can think of it that way it grows incredibly fast the inverse function grows incredibly slowly constant for all practical purposes but it grows so this is something so this algorithm has this inverse Ackermann function bound per operation for all practical purpose is constant but theoretically non constant this is an elegant algorithm it's deep it's simple it's easy to program the analysis and the actual running time comes out of left field no thank you there's an example I've always tried to produce simple algorithms because I mean if you can put
26:36
the analysis the put the complexity and the analysis keep the algorithm simple then being able to use it people only use simple things but it doesn't matter if the analysis is Kompany you want the analysis to justify the simple idea that's that's my approach to this question of elegance you've got your PhD you have to make a decision I'm thinking most computer scientists have to make this with their PhD and have and that is do I go into industry or do I go into academics maybe that's a false decision but tell me how you are thinking about your next step yes I think it's still true that that's the case people have to well so I applied to both sorts of places I apply the universities I also interviewed IBM Yorktown it's possible that was the only industrial lab I interviewed I basically decided at that point I wanted to be in academia I always thought myself as a professor so I applied on both sides but then I took a university position I ended up going to Cornell follow Hopcroft back to Cornell was not prepared for the Ithaca winters so I managed to survive for two winters and ethic you are Southern Californian after all yes well so I got my PhD in January of 72 actually I could have been finished in September and I had a job starting in September but Bob Floyd was my PhD advisor was a real stickler he was very perfectionistic so Stanford needed nine quarters of tuition so I had to pay for the extra quarter of anyway he wanted changes in the thesis so I ended up to land going to Ithaca until second semester which was January of 1972 I drove my fire engine red Mustang from Southern California from LA where my parents were I think of New York I get to Ithaca what's this white stuff coming out of the sky I'm sliding around in the road so that was my introduction to Ithaca so your shop I'm actively shocked it was a great department great students the climate was hard for me to take by the department because now you're in another university again at this cusp of computer thinking are they well prepared and have they committed to computational study it was a very strong the part well yeah hot broth was their heart Manas was there okay harass art mass another Tori Award winner he was the chair at the time it was definitely a really good so there's no you might've stayed one yes yes although it thing is also quite an isolated place which somehow didn't mean okay so really so I I'm with other things I get applied to Berkeley for a postdoc which they gave me and they would have they would have taken me after six months at Cornell but I thought that's that's not fair to Cornell I should try again so so I lasted another my last year and a half at Cornell two winters then I took a postdoc at Berkeley I think I may be the only person was given up an assistant professor to take a postdoc but Berkeley has these wonderful post parts called Miller fellowships which are twoyear positions no responsibilities no requirements and the pay was the same as a assistant professors right I wasn't so concerned about money so yeah so I retreated from the winter after a year and a half and what his birthday offer is it environment is another great computer science mathematics environment and dick Karp is there Jean Waller is there amazing students freedom California sunshine Bay Area paradise I'm gonna again that's a very broad question which may not be very significant that is the comparative vitality in your field of Berkeley versus Stanford Stanford has gotten the the reputation as the placement is generating the most inquiry or maybe practical results I don't know what and Burleigh is solid but but Stafford is the better place to be is this remotely true at this point well after my first year at Berkeley places started pinging me to join as a professor so I got Stanford made me an assistant professor offer and said I
32:08
could delay for a year finish my postdoc Berkeley would have made me acting associate professor I talked to a lot of people they told me what you just told you know it just Stanford was a better place not so clear to me I ended up going to Stanford I had great students he loved Stanford as a grad student Stanford as an assistant professor was maybe not so much fun somehow but this is a different answer than Berkeley has a great computer science division actually Stanford is great so as MIT can its argue against anything righteousness yeah there's huge amount of interaction actually sometimes I think that had I stayed in Berkeley I would have stayed in Berkeley forever but it's hard to know anyway I went to back in Stanford those access Stanford what are you what are you setting as you that's your intellectual goals at this point take the hammer of depth first search and kill off any possible problem and explore all combinatorial problems that are susceptible to efficient algorithms basically just taking my toolbox looking at interesting problems trying to find problems that are important to which I could make some contributions and in what did you make contributions well I mentioned a few of them we found lots of applications of depthfirst search I I analyzed the disjoint set Union algorithm I mentioned the universe a common function about that I actually finished up at Berkeley but one of my grad students at Stanford and I Tom Wingo ER who's in Germany we devised an algorithm that use depthfirst search and has this the idea of the disjoint set Union data structure in it at the saw graph problem that got that out rhythm got built in to pretty much all optimizing compilers that exist I worked out a bunch of other stuff too I mean that was I had really good students one who deserves special mention I think is Danny Slater I'm you know I've always been kind of eclectic in my choice of problems so I got interested in network flow finding a maximum flow in a graph with capacities and it turns out this problem among many other graph problems you can turn it into a data structure problem which means that if you want to solve the problem efficiently you need to figure out exactly what information you need to saw the problem and exactly how to represent it and what kind of operations you need to do on that information so as to get the solution to the problem you know what the minimal data structure that supports the needed computation so he worked on the network full problem and it turns out the data structure you need is sort of dynamic trees it's like the trees in the disjoint set Union problem except instead of just hooking them together you have to be able to cut them apart too so linking and cutting and keeping track of information basically so we invented a data structure to solve that problem hoowee is MIPS later than me yeah and in the process we had to invent a particular kind of binary search tree to make this thing efficient yeah another of my students got involved with that that was Sam bent so we ended up with this very nice solution but then and then Danny went to Bell Labs after he graduated and we kept working together and thinking about what was going on what is going on is you don't need to make every operation deficient you're doing lots of operations so all it is required is that the total time of all the operations is somehow limited this means you can afford an expensive operation if it's compensated for it by cheap operations sooner or later this thing happened with the disjoint set Union problem individual operations are expensive but they're balanced out by cheap operations so we started studying this phenomenon carefully and systematically this led us to invest they invent what is called the splay tree which a selfadjusting form of search tree in which there's no explicit balance condition it's very simple you do a lookup or insertion or deletion and then restructure the tree to make the item that you just looked for easier to access later on which is kind of like what happens in the disjoint set data structure so very simple we could prove all kinds of beautiful theorems about this thing and that's invention eventually we got the peripera scott walker surprise daniel from that one for nasa see yeah because that data structure gets used a lot of practice because it adapts to match the behavior it has this empirical property and we were able to prove nice properties of it and there's still a beautiful open problem concerning that data structure right I I think you're gonna tie with the idea of industry at some point in your career as well though you're principally an academic I'd like because that's a different context in which to do research how did you get in the end involved with industrial research back in the late 70s when I was a professor at Stanford which was from about 75 to 1980 various people from Bell Labs came and visited Ron Graham's Ron Graham Mike
38:59
Geary Dave Johnson so Mike started collaborating with them and then they invited me to come consult at Bell Labs so I started to have a fairly semiregular consulting gig at Bell Labs when I was a house the difference from and academic context that you have both because you have yes but well eventually I ended up doing both so what happened was I went on sabbatical from Stanford to build labs okay liked it so much I stayed and then ever since I've had some connection on both sides so it wasn't uh like the snow shocked Connecticut wasn't a cultural shock to go from a an academic environment where I'm assuming you could enroll that will in terms of problems you choose to solve to again unassuming a corporate context where the company has certain goals for its research is that wrong well Bell Labs in those days was a very special place and we were in the mathematics research department at Bell Labs and we were free to roam intellectually so it was a was very much like a university environment I didn't have to write grant proposals to raise money didn't have students didn't have to teach but there were wonderful colleagues and visitors to collaborate with and summer interns and so on so from the point of view intellectual activity and research not so different in that place from being in the university the managers were responsible for trying to get us to talk to people in the applied side and trying to bridge the gap and bring interesting problems in and we were all interested in helping the company but it wasn't the requirement it was something that this kind of emerged naturally based upon the personalities of the people involved I would say so was rare environment phone company was a monopoly at that point Bell Labs was fabulous it's a pale shadow of its former self of course it got broken up into many pieces right IBM research at the time was similar I think Microsoft Research now has some aspects of that all it's much more applied and focused in general in industrial labs these days so it's not as great a transition as I might have imagined to go from it's an academic context to a Bell Labs approach to research that is correct yes yes yes are you tempted at all not that you have to make the decision presumably to stay in that universe or is it wouldn't be a matter of time before you go back to the Academy well what happened was I was at Bell Labs so I went on sabbatical for a year and then they made me a very nice offer so I decided to stay but I discovered that after a year I was somehow losing my motivation for doing research which was interesting and somehow I attributed that to not interacting enough with young people students so I started teaching I got an adjunct position at NYU in New York in search of having yeah yeah yeah so I taught one course one one semester course every year for the next four years at NYU in the evening and one PhD student at NYU also and then after five years I did another look around to try to think about something more permanent shall we say well what really happened was University of Texas had lots of oil money and they started dangling endowed chairs in front of people so I interviewed there but I thought I'm interviewing here I might as well interview many places so I interviewed many places and ended up going to Princeton but I retained a parttime position at Bell Labs and physically got so far in any case so ever since I've been at Princeton which is since 1985 I've had some kind of parttime industrial it hasn't had to be able to have to be a choice no it's really not about you you've again there's sort of the broad subjects you've also the course of your career have a number of patents yes have they been patents that have led to specific results racism tell me the process of just wanting a patent for something and then what the consequence of having that patent has been you could just take an instance among the many you've done well large corporations like to have patents so they can trade them with other corporations so nobody gets in trouble basically so there's motivation for researchers to write patents that's pretty much the only reason I've ever done patents because the it's a very strange legalistic process it's much different from a scientific process the one instance in which I had a patent that had some commercial significance was when I was working with at Inter Trust which was a digital rights management company we were working on software selfdefense the issue being you write a program it's on your phone maybe you're it's it's someplace where the customer has access to the code but you're trying to protect the code for example you want to run a movie on your computer or your phone or something like that or an audio track you want to make sure that the user doesn't hack the system so they can run the move arbitrarily many times if for example they just rented it how you protect the code so we devised another number of strategies methods for protecting code we wrote a pretty large patent doctor and those ideas actually got embodied in technology that the company later later implemented so one can also then conclude from that that security itself has been one of those questions that has interested you this yeah this is a solution as a security issue yes yes
45:53
I've spent time working in other areas besides data structures and algorithms and security is one some of the interviews I've had the privilege of doing have poopooed the obsession with security as the security was the problem of the future that they didn't feel that I feel it's overdone as a problem to be contemplated does that strike you as sensible or surprising it does not strike me as surprising it is not necessarily sensible I think security is a hard really hard problem and most systems the internet for example was not designed with security in mind and back fitting onto an unsecure system or insecure system some kind of security mechanism is really tough and we've seen the consequences massive hacking attacks ISIL on Social Security is only becoming more and more important is really a challenging are you taking knowledge matter that issue these days what are a little bit so Mike my industrial tie at this point is back with inner trust so among other things I'm looking at some of their security technologies not attractive how are you guiding guiding your students as they come to you the good students don't have have in terms of where they might invest their intellectual and professional energy at this point well my recommendation is pick a problem with some application or some consequences pick a problem that's important in real life in an application area perhaps that you can then I mean I'm a theoretician at heart right so my students I want to see them prove theorems find an applied problem abstract the essence of it through a theorem about it or design an algorithm that can then be used in practice build the tie there do something that's relevant to somebody who actually wants to do something that's that's the message I try to calculate I can understand that is as intellectual even more impressions but are they ever asking you what are the fields and directions that seem that we're on the cusp of that an investment of their intellectual energy would put them in in the mainstream where it's not exactly the wrong way no sometimes I make suggestions but I think it's it's really up to the student to figure this out eventually I ask you as you look at the near future and longer term where are the excitement's you think and the the next stage of take off because you've said as I've read in your earlier stages you have the advantage of being looking at problems without rhythms and so forth at sufficiently early stage where there were lots of things to look into lots of possibilities things we're not so circumscribed is there any field or direction or topic these days that might give what a sense of being at the beginning of another revolution that they're busy that's strong a statement the beginning of another another well everybody's all excited about big data data analytics the new kind of artificial intelligence neural nets so on and so forth that's one direction to go Sanjeev Arora my colleague at Princeton certainly gone in the direction of studying neural nets very important but I'm kind of reluctant to jump into hot topics computer science has this kind of it's a very young field still so as there is a tendency for everybody to jump into the hot topic and try to mine it and then go on to the next topic and mining and so on so my approach and certainly now that I'm getting older and may be running out of time here is I really want to understand the fundamental problems so there are problems that I've worked on off and on throughout my career that I still I'm not learning about mean the thing about computers is they're really fast they're getting faster and there's huge memory there's a rich design space for algorithms so there's plenty of room to play even concerning problems that we have solutions were but maybe they're not the best ones so getting back to this notion of elegance I would really like to find the nicest the best most elegant solutions for problems I read people really care about someone kind of concentrated on that but to give another answer most of the work I've done in algorithms has been sequential algorithms for random access machines that's flat memory one step at a time two important abstractions which allowed us to do get vast numbers of results but computers now have multiple processors and they have memory hierarchies and their communication issues and so so I've started looking at some problems related to some of these more complex models and if one thinks the design space for sequential algorithms is rich it's incredibly rich and complicated once you start throwing some of these other ideas and even proving correctness of algorithms and there are multiple processes doing things because they interfere with each other there's a scalability question I think that's in terms of theoretical research and how it impacts practicality really understanding some of these issues I think is important I think there's still open problems even though people have been studying this stuff for a long time so those are the directions thank you very much
52:59
you