The HLF Portraits: Richard Manning Karp

Video thumbnail (Frame 0) Video thumbnail (Frame 9205) Video thumbnail (Frame 18324) Video thumbnail (Frame 31409) Video thumbnail (Frame 44493) Video thumbnail (Frame 54099) Video thumbnail (Frame 61173) Video thumbnail (Frame 74379) Video thumbnail (Frame 86408) Video thumbnail (Frame 98436)
Video in TIB AV-Portal: The HLF Portraits: Richard Manning Karp

Formal Metadata

The HLF Portraits: Richard Manning Karp
Title of Series
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.
Release Date

Content Metadata

Subject Area
The Heidelberg Laureate Forum Foundation presents the HLF Portraits: Richard Manning Karp; ACM A.M. Turing Award, 1985 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 award-granting 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

Group action Electric generator Momentum Inheritance (object-oriented programming) Software developer Direction (geometry) Closed set Gradient Neighbourhood (graph theory) Sheaf (mathematics) Mereology Mental calculation Number Mathematics Goodness of fit Internet forum Video game Musical ensemble Family Position operator Geometry Exception handling Social class
Point (geometry) Group action Latin square Multiplication sign Image resolution Solid geometry Student's t-test Neuroinformatik Element (mathematics) Mathematics Energy level Circle Nichtlineares Gleichungssystem Social class Graphics tablet Area Arm Inheritance (object-oriented programming) Cellular automaton Software developer Gradient Shared memory Euklidische Geometrie Demoscene Radical (chemistry) Physicist Video game Right angle Quicksort Geometry
Computer chess Complex (psychology) Greatest element Digital electronics Latin square Confidence interval Direction (geometry) Multiplication sign Modal logic Decision theory Solid geometry Mereology Food energy Abundant number Computer programming Neuroinformatik Mathematics Core dump Control theory Office suite Logic gate Error message Social class Area Block (periodic table) Software developer Gradient Moment (mathematics) Data storage device Physicalism Bit Surface of revolution Variable (mathematics) Probability theory Degree (graph theory) Data mining Category of being Process (computing) Angle Computer science Self-organization Right angle Quicksort Figurate number Mathematician Point (geometry) Statistics Branch (computer science) Student's t-test Applied mathematics Regular graph Theory 2 (number) Hypothesis Goodness of fit Causality Term (mathematics) Maschinelle Übersetzung Computer hardware Energy level Data structure Traffic reporting Combinatorics Metropolitan area network Form (programming) Complex analysis Electronic data processing MIDI Focus (optics) Fields Medal Host Identity Protocol Graph (mathematics) Inheritance (object-oriented programming) Chemical equation Forcing (mathematics) Projective plane Division (mathematics) Calculus Line (geometry) Limit (category theory) Cartesian coordinate system Uniform resource locator Logic Mixed reality Physicist Universe (mathematics) Vertex (graph theory) Numerical analysis Video game
Axiom of choice Group action Operations research Scheduling (computing) Direction (geometry) Multiplication sign Travelling salesman problem Disk read-and-write head Computer programming Neuroinformatik Formal language Permutation Programmer (hardware) Mathematics Different (Kate Ryan album) Matrix (mathematics) Office suite Algebra Position operator Physical system Programming language Algorithm Constraint (mathematics) Electric generator Bit Hecke operator Maxima and minima Artificial life Automaton Variable (mathematics) Process (computing) Combinatorial optimization Chain Computer science Right angle Quicksort Point (geometry) Service (economics) Computational linguistics Control flow Distance Code Theory Number Hypothesis Product (business) Goodness of fit Term (mathematics) Data structure Acoustic shadow Metropolitan area network Form (programming) Projective plane Total S.A. Theoretical computer science Word Software Personal digital assistant Logic Network topology Physicist Universe (mathematics) Video game Family
Complex (psychology) State of matter Multiplication sign Set (mathematics) Travelling salesman problem Disk read-and-write head Public key certificate Mathematical structure Mathematics Hill differential equation Social class Boss Corporation Algorithm Maxima and minima Variable (mathematics) Data management Process (computing) Computer science Right angle Cycle (graph theory) Quicksort Figurate number Mathematician Point (geometry) Divisor Distance Rule of inference Theory Goodness of fit Hierarchy Theorem Data structure Computability theory Associative property Standard deviation Fields Medal Plastikkarte System call Theoretical computer science Equivalence relation Computational complexity theory Loop (music) Software Integrated development environment Personal digital assistant Network topology Hybrid computer Universe (mathematics) Video game Iteration Musical ensemble
Complex (psychology) Suite (music) Group action Multiplication sign Direction (geometry) Source code 1 (number) Open set Mereology Computer programming Neuroinformatik Usability Mathematics Circle Computer engineering Propositional calculus Boolean satisfiability problem Social class Physical system Area Potenz <Mathematik> Arm Constraint (mathematics) File format Software developer Moment (mathematics) Electronic mailing list Bit Computer scientist Automaton Lattice (order) Variable (mathematics) Complete metric space Connected space Electronic signature Category of being Data management Phase transition Computer science Right angle Quicksort Mathematician Resultant Turing test Point (geometry) Sine Variety (linguistics) Similarity (geometry) Branch (computer science) Theory Machine vision Number Revision control Frequency Internetworking Term (mathematics) Reduction of order Representation (politics) Nichtlineares Gleichungssystem Boolean algebra Dependent and independent variables Fields Medal Key (cryptography) Expression Library catalog Theoretical computer science Faculty (division) Word Logic Universe (mathematics) Statement (computer science) Video game
Internet forum
that's a car introduce me is the boy you were where are you living what is your family's life intellectual particularly I grew up in the suburb of Boston Massachusetts that's actually a section of the city called Dorchester the breeding ground of many famous Jewish scientists and business men perhaps analogous to the world of Brooklyn played played in the development of New York sleep okay my father was a schoolteacher he graduated from Harvard in 1927 my parents locality a depression mentality so playing it safe was extremely important and so he gave up his dream of going to medical school and took a safe position as a teacher but not a lucrative one but he spent many evenings and late afternoons traveling around the city to scrape up a few dollars giving tutorials so here it is very important journey was very important my mother was a very intelligent woman but she as with many people that generation she did not go to college she finished high school and we had various secretarial positions before raising the family before before yeah I'm the oldest and I have two younger brothers and younger sister they were born at four-year intervals provided for the skate for the facing of college education expenses and I was a quiet child allegedly precocious I was reading very early did well in school in the early years skipped a grade and not question to that I understand how ambitious they are for you the later found out that the impetus for skipping the grade was from the school from the teacher who felt that I would be bored okay but they were ambitious and it was education of all so I was exempted from many of the duties the good family participant like be expected to have as long as I filled out my performance at school that was most important letter that was the most important thing and how early were your interests shaping in what direction versus the matter not so terribly early I think I discovered my bench for mathematics only in high school when I took plain geometry but I was very proud of my mental arithmetic skills which I entertained people with by multiplying three-digit numbers or Asian early four-digit numbers and you had school guys who were to take by that know this was actually I didn't really have close relationships with school mates in part because I was a year and a half when my classmates in fact one of the tragedies of my youth was when I applied to be a member of the neighborhood social group that headed a football team and various secret activities and I was denied on allegedly on the grounds of age oh okay so Europe is it melodramatics a lonely can't I would I was a lonely give it I'm not I wasn't lonely but I didn't have close friendships as importantly I I went to Boston Latin School from seventh grade on and that served the whole city so the kids came and by the way was all-male and the kids came from all over the city and dispersed and I had some friendships but on the whole I didn't have a very active social life what about it I bought supplies a particular teacher at mentor somebody taking an interest in you with yes I had a math teacher who did take a particular interest in me and for some reason I was while I was I was first in the class but I was more or less co-equal with some of the other bright kids except in math where for some reason nobody else stood out as talented in mathematics and with a gayness to guide you into a professional interest in it yeah that not the teacher to come the teacher gave me a lot of support alone he was austere fillable I and I don't
think he ever had an arm around the year or treated me parentally but but he recognized that I was strong in mathematics my parents recognized it one of the misfortunes was that I somehow couldn't take instruction from the father and we have the first boy and heavier so he tried to introduce me to chemistry and memorizing the names of the elements was not interesting for me right and he tried to teach me some math he was a math teacher he was a you mathematically he was a math teacher in a junior high school math teacher his knowledge of mathematics didn't extend very far he had difficulty understanding some simple motions which I so I quickly surpassed in mathematics and probably let him know that yeah it was mystified by the fact that the equation x equals 1 has only one solution but if you square it you get two solutions you learn that quite mysterious things like that so so he didn't really try to teach me mathematics on so I was sort of once I had given evidence of being inclined that way right in tenth grade and we did Euclidean geometry which was really eye-opening for me minute elegance that I I would pretend to be sick so that I could stay home and solve geometry problems right others say it shows another reason to protect but yeah four years is all for all yeah but but I was a very I would say submissive child I make I never did anything radical and I didn't skip school I had to and are very respectful of my mother although in in my teenage years I began to resent her again not another you understand so well in Latin of course it's what it was one of the past speakers for harder to try to that well he seemed inevitable next that yeah yeah in fact and they have a very special relationship with Harvard and at the time they would take as many as eighty students I think now it's a small even though the school has maintained its level over the years and adapted nicely to the changes in the population of Boston now they take about twenty kids I think but a team of design they took eight eighty and I got a so-called national scholarship which enabled me to live in the dorms which was said community and employing a better computing community from Dorchester we're computing okay so they're going hard yeah how are you sorting out your major your teachers your centum cells well I have an exaggerated sense of self murder at the point of high school graduation because I mopped up a lion share of the awards of graduation and hey and so forth and in at the time I had no self no sense I was suspending self criticism or somehow I thought that I I only have to choose between being a Nobel Prize winning physicist or becoming governor of Massachusetts well because I got opposition that was understood so he were confident I'm not sure that I was confident down deep I think I think I had a fantasy life in which finishing first in the class was just the launching pad for greatness but I don't I wouldn't say that I was confident a Tennessee so how are you setting out the future brightness art well with a solid base equation so first of all I was pretty immature I started I was starting at age 63 at earnest and I well I had a wonderful group of three roommates who have remained lifelong friends and that was very fortunate development so that was great and I came up with it socially or I had some friends circle of friends but I quickly discovered that I was not the most talented kid in the class you know as often arteries area yeah the first of all the preppies scene from Andover and Exeter seemed to be first of all they had much more savoir faire and which I was totally lacking at the time and also seemed to be better prepared
even hidden mathematics in his height yeah for example the physics that I had at high school was laughable really I remember Danny Shea was the instructor he stood in the corner of the room in the own only thing he ever taught us was something about the angle at which a pile of coal forms the physics class was totally useless so you had catchy has to do I have ai yai and I didn't take chemistry in high school because I got I like Latin a lot and opted to take a sixth year of Latin in moved chemistry so so I hadn't had either chemistry or physics you being guided and harker does somebody say well if you're going in this direction you'd better do this another eye I had a nominally I had an advisor I met with him a couple of times he we chatted about math and it was clear pretty clear that I wanted to be a math major okay well I are going to do something something related to math okay I think my in that era the the balance of science with theoretical physicists of course has to be after Manhattan apartment project and so my my mother who was more of a dry driving force my father was rather relatively passive my mine and my mother sort of planted the seed that maybe I would be a physicist there she is that mission for you she yeah she was definitely ambitious all of tolerance because when I didn't have perfect grades that they were never critical like my first year was mixed I had a mix of A's and B's that I wasn't anywhere near the top right and I was signed in math briefs through the math hello it was just basic calculus so in those days you didn't have calculus in high school and I hadn't done anything exceptional to build my math background so I was just taking the regular freshman math which was very easy for me right but I found physics challenging huh and I for whether you were a deep repair I had essentially no preparation hi and the the preppies all look at at solid physics core and I also felt that the explanations are somehow unsatisfying oh I want to stay there because being unsatisfied an explanation mark sure so you are you so many have your potential to be the business your mother watching well I wasn't anywhere close to be committed to that direction right but the mathematics was solid yeah for you right were you did you have a mentor yet I mean when does it turn out that there's a significant figure that shaped a little bit my senior year I would sweet I could go to talk about that yes yes so my senior year was mixed because I was just sort of encountering graduate level mathematics and it was a different well first of all I had after a fee in the second half of my junior year I got ditched by a girlfriend and went into a funk during which I spent all my afternoons playing chess at the Boylston Chess Club in downtown Boston and and so my my grades tailed off and I remember a dramatic moments with my parents with my grade report arrived they had never you know been critical about my career you know my performance in but it went off a cliff to the second half of my junior year and I tearfully broke down and told them that Lisa had ditched me right so it took me a while to climb back to climb back up but she did like I did in my senior year but the experience was mixed because I took them I took an introductory probability course in I had some kind of a bench for probability and combinatoric and and so I was sailing through that course and relishing there watching every minute of and I did have a professor hardly Rogers who had a important career in mathematical logic later with them Teaching Fellow and he encouraged me he let me know that I had something going for me and what formed is I heard some tactics by year senior year you're taking what back what I'm thinking what next and actually I want to digress to also talk about the other side of the coffee okay which is that I was taking some graduate a graduate course on complex analysis taking okay and there were three students in the class who were miles ed of me and I didn't know that one of them was going to get a Nobel Prize and the other one was going to get Fields Medal oh my and third one also had a serious career in mathematics and he was actually the most precocious he was a freshman and I I knew that I wasn't in there leaked and and so I solely the year was mixed because I was great in this probability little errors and also a baby statistics course there was a piece of cake for me but then in the Graduate mathematics you were in here minute age I would begin items perceiving limitations right and I drifted into the computation lab and so and took I think I guess I took two semesters of numerical analysis which was again I was a lazy student and I wasn't really at the very top there but I could have been if I had worked I mean I had you you want me to say that thought computation at this point having that you're you're the cusp of a revolution we are all of the cause of a revolution that what are you thinking about that as you drifted into the computational well Harvard was one of the few places that really had a computer in those days the the term computer science had not coined but how it had a kind of had a graduate program which was a mix of classical applied mathematics and a little bit of probability theory and statistics and and then some courses on computer hardware and organization of computations and something called switching theory which had to do with the design of the logical circuits in the computer and and so I was all of that was part of my very superficial abroad graduate program it's a control theory circuits courses I took a course on vacuum tube circuits Jared you see you divide your company retain no no this is I'm jumping hips now okay good Hill directs graduate year so to fill in the blanks I applied for admission to be for the degree of you
know I guess doctorate in Applied Mathematics and with the intention of hanging out of the computation line which is what I did the the question of applied theoretical is an important division at pact right you knew but we have the experiences in no no no it was the organizational structure of the university if I wanted to be in computation lab that I went through the division of engineering and applied science okay so there and then I would have had a latitude to take graduate courses in the math department but I didn't avail myself of it I did what I was told in fact I there's one terrible moment in in the middle of my senior year I knew that I was headed for the computation lab so I went to see an instructor in the computation lab and for guidance about my program and he said looking at my grades which we had some Hayes but also some B's is he said I think you should take a good solid course in accounting and not a class it would say I don't know whether it was discriminatory or will they would send it to anyone or not know what was it is mine but being a submissive fellow I took it seriously it happens to clash with the second semester complex office well I named Chelsea County not sure / contractor I turned around again I went to see professor outdoors eminence mathematician who had written the textbook for the apply for the complex analysis course and I asked him for permission to drop the course of mid ear and he said why yes good lesson in the end I said because it's an accounting course you could take and he said you me please of course human society survives as bad decision yeah and develops a graduate program develop in a tragic world and were to write I mean and again in but in the first year I I was under an indifferent student ID I I had a close friend who encouraged me to sort of goof off together and and I my grades were mixed in fact they were low enough well what also happened was that jumping around a bit in the second semester of my senior year I again following bad advice or no advice I'm not sure I I started attending a course on alternating current circuits and I went to the first lecture and I was totally turned off but I didn't bother to drop the course I didn't go to any lectures or very few I went to the labs because that was rock bottom necessity by the night before the final exam I realized that I didn't have any extra credits and wouldn't graduate with my class if I didn't get a passing grade in this circuit course which I paid no attention so I sat up in the rest of textbook and went for a long walk by the river contemplating my parents reaction as I didn't graduate right and the goodness goodness of his heart to get a BSc - so I graduated with my class so much energy but just well no extra credit oh yeah and so I graduated Kula I had hoped for a magnet right which I thought I deserved but probably I'm not sure exactly what sealed my fate I mean I was Akuma's it sort of like getting second at Cambridge or something right it's not a big distinction right but he like in graduate school why why are people encouraged by your future with this I think it would I think the Harvard lab didn't have an excessive number of applicants who would have a new field and very high pasties not very high perseus not it was a really lucky for me the timing was perfect I was also encouraged to go that way by my mother who had some precedence about the future and she said to me data processing is going to be really big not plastic to do something like that probably applies to think it's going to be really big right right well because I want to advance in your career how do you go about choosing the subject of your thesis well I had a couple of I had a couple of summer jobs which unlike the coursework and do me with confidence because I did well at both of those when MIT weakened lab and I got a stint with general election another misstep in my career was in my life was to spend the summer in Cincinnati which I didn't enjoy or not but I worked at General Electric and I did okay there and so I haven't feel like that I you know had something to offer him and I just I just hit upon an idea at the beginning of my I guess it was my third year certain yeah yeah yeah being with my second year of graduate school probably got the idea driving back from Cincinnati after the summer that that you could look at a computer program as having associated with a graph a directed graph in which the vertices would be the blocks of the program or the straight line path of the program in the edges would correspond to branch points and that by viewing it graph theoretically you could analyze certain properties with programs for example you could find out that certain parts of the program when ever accessed or that certain certain variables we're never active at the same time and so they could share a common storage location and so forth like you're given sort of analyzing the structure computer program this is not throw out the thought elsewhere w-what kind of it is this is something I was coming up with I mean later it became commonplace but there was no prior literature on this and that became a focus and that became the focus of my thesis I I my advisor was a man named Tony Ottinger who his own work was on machine translation of Russian and I actually flirted with the idea of working on on machine translation but it really for one thing I would have had to learn Russian and okay I couldn't feel like doing that because you know for residents throughout all these years I was not hard-working student right and so I went to Tony Hollinger and I I had
impressed him earlier because I was a teaching assistant and of course on computational linguistics that he was running and he had some incorrect ideas about Markov chains and I showed him examples and he loved that direction anyway yeah yes I would so he saw that I had a little something going for me right and also I took a course on mathematical methods and operations research from a man named Ken Iverson who was a very impressive person his own research were fun languages but he taught this course and I there's right up my alley and I was about 25 points higher than anybody else on final exam and I and so the word got around the lab that I was okay okay even though I wasn't located in the other lab any of the heart of your courses or and I got some B's and some other courses that I just didn't care about and when people have designated uniformly as theoretical in regards while there was a national issues well I suppose there was no well first of all there was no computer science anyway anyway they were certainly no theoretical computer science the number of public a number of books was minuscule there was a orange princeton that the princeton book about automata theory universe and martin Davis's book on computability it was Queenie's book which was over my head and i read a little bit about logic in there there is virtually nothing so how could you guide yourself and what the heck step is going to be in a world of us is forming well I got lucky in my first job after the PhD which had helped which was crucially important but the Stars the thesis was concerned I just pursued it on my own totally on my own and it wasn't great thesis I mean it was original well that was great me but it was hardly deep I mean I was never really really proud of it and you know I didn't plead wasn't he and he's great achievement and later that feels kind of developed and and with a more structure developed at new ideas that I hadn't had and it became a respectable people love within the programming languages and programming systems they originated something to do well I had one publication out of the thesis I don't think I've affected the course of history okay I'm gonna get you to your first challenge okay I really got lucky I will I walked into the restroom at the Harvard computation lab it's a good birthday something and a sudden voice drifted towards me from one of the stalls mom was man named Fred Brooks maybe a note knew and and he said when you come into interview with IBM and so it is and I interviewed a number of places but the IBM situation was by far the best so I have a choice between that and acne here or there was no academia I just selected magazine you know I guess I could have gotten possibly I could have applied for a jumped into the electrical engineering department there were no computer science department service well I think there were a couple just starting it was one at Purdue maybe Stanford already had something MIT and some MIT was further with further along than Harvard was but I didn't think in those terms I was like everybody else that was coming up that year I in my catcher a and this is I know there are a number of golden ages of commercial research but certainly the idea watches but the other chemist was one of the great heights it was one of the great places it was a little bit in the shadow of ALS which was usually considered number one right industry but maybe it was number two yeah probably it was and anyway my interviews there went well Mike I got I was offered positions in about seven different departments IBM came down to a choice between a group that was doing switching theory which was up my alley it was gone into total mathematics versus Fred Brooks group designing a computer at pickasee and I had enough sense of myself to know that the switching theory was a much better choice and you you clearly feel that that wasn't right oh yeah definitely doesn't so you are products is teens and well as bribes with team I have the head of the team was a man called Roth who was an algebraic topology stand had done interesting work in switching theory and there are a few other colleagues are probably platic members of the team and I was a by then I had become a little a little bit of brash sometimes I remember in my summer job
back had weakened labs I somehow went to lunch every day with it with a group of kind of reserved physicists and I became the life of the party I rolled with Joker in and I think I was beginning to feel maybe because I got good offers and so on I was beginning to feel maybe Erica a bit arrogant and I felt that some of my colleagues oh gosh I don't want this to be public but well I mean he's still the young man here a lot of other heads yeah so I so I did a you know I was single when they were raising families and I even though I wasn't killing myself exactly I was pretty dedicated to my work and I felt that I was easily holding my own how are you choosing here problems or were they chosen for you as hell partly I was working under the influence of Paul Roth and I had to work on the next generation of switching theory software and I kind of bungled that actually he put me in charge of the programming group to to actually write do the coding for the algorithm so I worked on the algorithms and did some good stuff there but I was very relaxed with these with the programmers and I didn't really run it as a shot with goals and deadlines I just sort of let that let it drift huh so I but somehow Paul Roth ptolemaeus automated tolerated this and and I have some independent projects as well I want to get you to your first break my first break through okay so in some time around 1960 I started a very than 59 with sometime around 1960 I wrote a little note on a combinatorial problems a scheduling problem that involved sort of relaxing the problem so to admit some of the constraints to solve a simpler problem but then fiddling with the certain variables to it's a technique that I later learned that mean it's called lagrangean relaxation and but I kind of reinvented it in a primitive form so I wrote this little note on the scheduling problem didn't think much of it and a fella named Mike health who was working in New York City I was up in Westchester County Mike hell noticed it and we got together I went to his office in New York City and we realized that we could apply the same technique to the Traveling Salesman problem okay which you need to explain such a classic okay suddenly the Traveling Salesman problem is perhaps the most well known combinatorial optimization problem and it's the problem of a salesman who wants to visit all the cities in his territory at minimum total travel cost so where the distances or costs between the cities are known are given so you've given this matrix of distance from New York to Boston is 240 miles and so on and you try to search to sift through all of the possible permutations of the cities to find the one that has the minimum travel cost right okay so so we had some ideas about the Traveling Salesman problem and the first idea was really not particularly important but it led to a
publication which is still cited because it gives the best-known worst case complexity for the Traveling Salesman problem so one of the issues in the theory of computation is how you judge an algorithm and the standard way by clear clear occasions is to look at the worst case that even if an adversary could pick the cities and the distances confound the algorithm how long would it take so so we gave a bound turned out that independently that was done by somebody else but if you publish that and still stands as the bound and we try to base a algorithm on that but that that didn't work well and then you got the idea of
applying this lagrangean relaxation so the idea is basically that while finding the shortest tour through a set of cities is latif is the challenging traveling salesman problem finding the shortest tree connecting all of the cities in a tree-like structure is is easy so so we got the idea of a sort of hybrid algorithm where the inner loop would be computing the best tree and then in between the iterations we would fiddle with the costs in a certain way to make it converge towards a cycle which is like a tree but with everybody having only two neighbors so we so the requirement that you only have two neighbors was handled by fiddling music auxiliary variables not turned out to be a pretty good way to attack the problem and we developed software for it and well this is probably called well it was probably called it's not recall the held carp relaxation and generically its lagrangean relaxation okay and there are still people writing theoretical papers about the performance of the hill card okay so this is a breaker well yes I guess you could say so I mean I remember that my boss and one of my idols at the time was Alan Hoffman a very strong mathematician but a much more theoretically inclined so I don't think he would said it with the pictures because if we weren't many theorem is one theorem in the paper and what may stand out was it would work better than other approaches sorry so the four appears that maybe it wasn't a breakthrough but I think you could say that it was a breakthrough because it's still cited and referred to computation itself still doesn't have a very high reputation as a field of inquiry at this point the considered sort of a lower or applied automatics had been um I certainly I was in an environment by that time where it was definitely not a second classes and within the IBM research lab with the IBM mathematics but that was my world I mean my world was IBM pretty much right at that time so I didn't feel there there was a kind of hierarchy within what we would now call theoretical computer science that computational complexity theory was beginning to emerge and automata theory which was a sort of forerunner of computational complexity theory and that has a rich mathematical structure and difficult problems and I think that probably would have been before caviar right right he can with that you know rule what that wasn't my world was that not that I do a case not not at that time but I was a breast of it and I was reading the literature and I there were some very strong young scientists who are doing it and most of all Michael Raven who's a legendary figure in this field and he and he became a close friend as I can describe also and a little layer in the mid-60s so in the early days at IBM I certainly felt that I was in the right place and the kind of thing I did was supported and my manager my initial manager Paul Roth supported me and switching theory work whether you hear the siren call of academia I begin getting interested in the mid-60s what happened was I started looking looking around a bit in nineteen well it was kind of a complicated situation I I sort of fell somewhat unwillingly into an engagement to a young woman in 1963 and I guess properly I was looking for a way out human factors I would play and okay and in one way helped was to look for an academic job which was sort of I was beginning to be attracted to that anyway I was a convenient activity and academia was the opportunity started cropping up yeah so so the first one that I've looked into let me called recalled chronology I think the first one that I looked into was at the University of Chicago and they had a small computer science department and they offered me a job but it didn't look as if there's anything very interesting going on and I didn't like the idea of living in Chicago with her so the cold winters right and and so I declined that job and then more or less simultaneously I was offered that was an associate professorship I think with Kenya are not sure I was offered an associate professorship at Berkeley and also a friends at the University of Michigan invited me to come for a year and I visited Berkeley I had loved it but stupidly instead of taking Berkeley offer which would have meant burning my bridges without the end I decided I thought well Berkley Michigan they're both big state universities they're pretty much in an equivalence class so you know why not for a year to Michigan and that's what I did why did she say stupid certificate is right at Pelican well below here Michigan is not dirty I'm sorry you need to the pleasure of living in West versus the other hill living one and then Berkeley was more advanced in my field oh they love our head and anyway in Arbor and I did not hit it off okay I blew up to about 220 pounds that year we have minimal social life right but what I did do that year was I discovered that I was a good teacher okay that's very important and how did he were assigned in class yeah well right so they I had a full teaching
moment but in particular there was this one class in automata theory and lacking the social life I threw myself into it and I must say my lectures were perfect yes I am one of the words that a perfect lecture in their clarity in clarity in clarity yeah but I came into every class totally prepared I wrote notes for the class and I realized that that I had a knack for teaching I had actually done some casual teaching while working at IBM I had taught courses that I forgetting I think back as early as 61 and shot at NYU and later at Columbia and Brooklyn Polytechnic so I had a all along through my time at IBM but but it was the year that Michigan when I taught that class realize that I really was very good at you I think you're the one that what is the relationship to teaching and your own theoretical research work are they reinforcing each other are they distinct part of your brain how how does teaching and fear hello definitely reinforcing very much so you can teach a course without really penetrating deeply and I think sort of arms me for some of my future work and I've always and you know over the years it's always been a important connection what is that future work let's get you as your next truly productive phase okay so having missed the chance to come to Berkeley in 64 I've got another chance in 68 and this time I accepted so I came to Berkeley as a full professor in a fledgling department that had been formed Berkeley has two departments the well established electrical engineering department which had a branch for computer science and this new department with about seven faculty members that allegedly was supposed to go off in a different direction closer to the humanities and Social Sciences but that connection actually never developed and so I joined this little department which featured three future Turing Award winners we didn't know that's it and it was really a very good group but it became clear that the university did not need two similar computer science departments and so there was a forced marriage in 1972 or 70 73 I guess and being the only tenured faculty member who was not involved in ferocious politics they made me care of Computer Science Division of the new merged department but that that's something ahead a little bit because I getting back to my research right the the big fracture of my life occurred in 71 72 or so in in 1971 I read a paper by Steven cook who had been a colleague at Berkeley but moved to the University of Toronto and he showed a certain problem called the satisfiability problem of propositional logic and was as hard as any problem in a certain class I have to describe what that problem is and and what it means to be hard so the satisfiability problem is essentially a system solving a system of equations in boolean variables so a boolean variable is a very moment represents a but the truth of a statement so it can assume only to thousands - or false huh so to valued logic and the satisfiability problem essentially in that problem you're given a bunch of statements that either X is true or Y is true or Z is false and overstating a whole bunch of those statements and then the question is whether there exists an assignment of truth values to those boolean variables which satisfy all those equations right so and what cook showed is that that problem is as it has such generality that you can express succinctly Express a huge class of other problems and these other problems are essentially problems where you're given a bunch of constraints we are a solution to the constraints it's easy to verify but may be very hard to solve so so if you go back to the satisfiability problem it's very hard to sit through the exponential number of truth assignments to these variables you may have been many variables but if somebody gives you the correct truth assignments you can easily look at the equations and the check that they're satisfied so problems with this character that a solution may be hard to find but it's easy to verify that's so that goes by the name NP and P is the collection of problems where a solution is easy to find right intuitively verifying is a lot easier than finding a solution right but the big the biggest open question in theoretical computer science is whether key is equal to a fertility problem so what is your contribution I think up setting this this in titanium issue Rex you jump into it so I jumped into it by realizing that the satisfiability problem is not unique in its generality and I had experience with many other come to Torre alums having the same character aren't dissolved but easy to verify right and so I just systematically began using a certain technique of reducing one problem to another I began to show that
there was a whole circle of problems that shared with the satisfiability problem the property that a solution is hard to find but easy to verify so you send this into the world yeah this way of thinking Rex and how does the world respond with immediate enthusiasm so it was it was clear from the beginning that so these problems which are the source artists ones are called np-complete and so I wrote a paper giving a list of 21 and P complete problems and they still being worked on yes yes but that would they were involved more for a number of years and 70s where people would prove that even seemingly very special problems where np-complete and there were thousands of such discoveries and it reached the point where a new way in a completeness result was no longer published unless there was some really interesting twist to it that it became relatively routine so you might say that I opened Pandora's box and then he was sort of easy to carry on further reductions of the kind that I had used and and so many papers were written in the 70s and there was a book with the catalogues and so on but it reached a point where you couldn't just publish a new India completeness result you can submit it to the catalogue that situation now ok as you talk to the young as they begin to explore what needs to be loved that right where might you are taking or many where is you're taking now in terms of what needs to be looked at it theoretical well I become the director of an institute dedicated to theoretical computer science and if I may not give a little background for that because if time allowed is so in I have been involved through the 80s and mid 90s or even beyond in various politicking for the theoretical computer science community we had a committee to raise funds and we we actually were instrumental in the creation of a congressionally mandated program that brought a lot of money not only to the theory area but related areas and in 2009 I was invited to go to the Simon foundation for meeting that included mathematicians a couple of computer scientists statisticians so I figure out what Jim you know about Jim I'm sure for the sake of our audience ease suit endlessly successful hedge fund manager after Bridget early career in mathematics and he and his wife founded a foundation and had among other things supported mathematics and in 2009 they were looking for new things to sponsor in the mathematical world and they were treating to other computer science representatives in this meeting of the big lessons from the Institute for Advanced Study and Margaret writes from NYU and together we proposed the creation of an institute for theoretical computer science and there was no looser than a competition so from 2009 onward I've been totally involved in first in the competition and then I success was punished by the creation of the imaginary the developer hidden which led me to to take on idea of an administrative post so for your sins you continue to to think about this way as well well right so basically what I'm experiencing here at the Institute is that every semester we run two programs and selected focal areas and we bring 50 or more people together to spend a semester working on those programs and they range over a wide variety topics one of the directions that the berkeley group including myself but all of us have pursued even prior to the formation of this institute actually starting in the early part of the century was the notion that we call the computational lens and this is the idea that computational phenomena occur not only in computer design and programming but in the natural sciences the economic sciences engineering that you can think of the immune system as a computer figuring out how to fight off invaders you can yes you can think of a marketplace created via the internet as a as a as a complex aim of conflict between parties who are both competing and collaborating you can think of certain physical systems as performing computation and and so this this lens on the sciences was sort of a theme for the whole group at Berkeley starting in the early period of the century and then we adopted that theme as our signature theme for the Institute and in the woods this vision which was broader than most of the competitive visions because we were reaching out to many scientific fields that I think helped us to win the Institute so your your vision of the future is the overlap that's probably the right word but the national connection right seeing what you had learned in theoretical computation had need to apply some of those insights into other fields and even particularly biological but well yes so so that's one of the major themes of the Institute but really also sponsored programs in course theoretical computer science and in related areas of mathematics and now of course on data science has come along as the new cry so to speak this is data science a Irish attentional yeah well I guess you could say