YouSaid · the spoken record

Richard Karp

lines on the record: 126
first: 2020-07-26
most recent: 2020-07-26
sittings or episodes: 1
sources: podcast

Every line below is reproduced as it was said and linked to the record it came from. Nothing here is summarised or generated. Directory · Search · Corrections

“I thought that it wasn't a very good test because it was too subjective. So I didn't feel that the Turing test was really the right way to calibrate how intelligent an algorithm could be.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, she was a smart woman and there was just a feeling that this was going to change the world. But I didn't think of it in terms of personal computing. I had no. Anticipation that we would be walking around with computers in our pockets or anything like that.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“I couldn't imagine that. There was a sense in the laboratory that this was the wave of the future. In fact, my mother influenced me. She told me that data processing was going to be really big and I should get into it.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Or mid Yeah, we had a UNIVAC UNIVAC with 2,000 words of storage. And so you had to work hard to allocate the memory properly to also the excess time from one word to another depended on the number of the particular worries. And so there was an art to sort of arranging the storage allocation to fetching data rapid.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“The Mark IV filled a large room much bigger than this large office that we were Talking in now. And you could walk around inside it. There were rows of relays. You could just walk around the interior and the... Machine would sometimes fail because of bugs, which literally meant flying creatures landing on the switches. So I never use that machine for any practical purpose. The lab eventually acquired one of the earlier commercial computers.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“That we can do. Of course, another attribute of geeks is they're not necessarily endowed with emotional intelligence so they can live in a world of abstractions without having to master the complexities of dealing with people.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“I think that you can do amazing things. You can test whether large numbers are prime. Can solve little puzzles about cannibals and missionaries And that's a kind of achievement. It's puzzle solving. And at a higher level, the fact that you can do this reasoning, that you can prove in an absolutely ironclad way that some of the angles of a triangle is 180 degrees.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, well, I wasn't particularly charming, but I could be very repetitious and loud. And the other employees were... Sort of juvenile delinquents who had no academic bent, but somehow I found that I could impress them by performing this mental arithmetic.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, I had a summer job at a beach resort outside of Boston. The other, I was the Barker at a ski ball game. Used to sit at a microphone saying, come one, come all, come in and play, ski ball, five cents to play, nickel to win, and so on.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“I think so. I always like to play with numbers. I used to amuse myself by multiplying four digit decimal numbers in my head. and putting myself to sleep by starting with one and doubling the number as long as I could go and testing my memory, my ability to retain the information.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, it's really cool. If I had mechanical ability, I would probably like to do woodworking or other activities where you sort of shape something into something beautiful and orderly. And there's something about the orderly systematic nature of that inertive algorithm that is pleasing to me.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, the simplicity lies in how you find what I oversimplified slightly, what you will end up subtracting a constant from some rows or columns and adding the same constant back to other rows and columns so as not to reduce any of the zero elements, you leave them unchanged. Each individual step modifies several rows and columns by the same amount, but overall decreases the cost.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“While maintaining the property All the elements are non negative And so You have to do find. Small moves which will decrease the total cost while subtracting constants from rows or columns. And there's a particular way of doing that by computing the kind of shortest path through the elements in the matrix. And you just keep going in this way until you finally get a full permutation of zeros while the matrix is non-negative. And then you know that that has to be the cheapest.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, all one-to-one correspondences are permissible. If there is a connection that is not allowed, then you can think of it as having an infinite cost. So what you do is To depend on the observation that the identity of the optimal Assignment Or, as we call it, the optimal permutation is not changed if you subtract A constant from any row or column of the matrix. You can see that the comparison between the different assignments is not changed by that. Because if you decrease a particular row, all the elements of a row by some constant, all solutions decrease by the cost of an amount equal to that constant. So, the idea of the algorithm is to start with a matrix of non-negative numbers. Keep subtracting from rows or from our entire columns. In such a way that you subtract the same constant from all the elements of that row or column.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“So in the assignment problem, you have n boys and girls, and you are given the desirability or the cost of matching. The Ith boy with the Jirl for all INJ. You're given a matrix of numbers. And you want to find the one-to-one matching of the boys with the girls such that the sum of the associated costs will be minimized. So the best way to match the boys with the girls or men with jobs or any two sets.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, the magic is just the fact that it... that the gap from the optimum decreases monotonically. And you can see it happening. And various metrics of what's going on are improving all along until finally you hit the optimum. Perhaps later we'll talk about the assignment problem. Illustrate.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, just that as the algorithm proceeded. Because you were making progress, continual progress. And eventually getting to the optimum point.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Tried to take steps that get closer and having the certainty of converging. So it's basically the mechanics of the algorithm is often very simple. But especially when you're trying something out on the computer. So, for example, I did some work on the traveling salesman problem. And I could see there was a particular function that had to be minimized and it was fascinating to see the successive approaches to the minimum, to the optimum.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, I think that usually an algorithm involves a repetition of some inner loop. And so I can sort of visualize the distance from the desired solution as Iteratively reducing until you finally hit the exact solution.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, the interpretation in terms of For example, finding the highest point on a polyhedron, as in linear programming, is motivating. But again, I don't have the high-dimensional intuition that would particularly inform me. So I sort of lean on the algebra.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Not Euclidean geometry particularly. I think Use tools like linear programming and integer programming a lot, but those require high-dimensional visualization. And so I tend to go by the algebraic properties. Right.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“You started a corner and draw a line. Parallel to the opposite side And that line sort of trisects the angle. between the other two sides. And you get a half plane which has to add up to 180 degrees. And the angles by the equality of alternate angles, what's it called? You get a correspondence between the angles created along the side of the triangle and the three angles of the triangle.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Three dimensional objects or surfaces, hyperplanes, and so on. So there I didn't have an intuition. For example, the fact that the sum of the angles of a triangle is 180 degrees is proved convincingly and it comes as a surprise that that can be done”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, just that you could establish a fact about geometry. Beyond dispute by pure reasoning. I also enjoy the challenge of solving puzzles in plane geometry. It was much more fun than the earlier mathematics courses, which were mostly about arithmetic operations and manipulating them.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, any segment joining the two circles, if you extend it by taking the radius on each side, you get a segment, a path with three edges, which connects the two centers. And this has to be at least as long as the shortest path, which is the straight line”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“So Michael Rabin told me this story. About an experience he had when he was a young student. Who was tossed out of his classroom for bad behavior and was wandering through the corridors of his school? Came upon two older students. Who were studying the problem of finding the shortest distance between two non-overlapping circles And Michael thought about it and said, Take the straight line between the two centers and the segment between the two circles is the shortest because a straight line is the shortest distance between the two centers in any other line connecting the circles would be on a longer line. And I thought, and he thought, and I agreed that this was just elegant, the pure reasoning could come up with such a result”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source