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 was kind of a lazy student as an undergraduate and even in my first year in graduate school. And I think it was when I started doing research. I had a couple of summer jobs where I was able to contribute. And I had an idea. And then there was one particular course on mathematical methods and operations research where I just gobbled up the material and I scored 20 points higher than anybody else in the class and came to the attention of the faculty. And it made me realize that I had some ability that I was going somewhere.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Different from everybody, you have to work differently with students. Some of them just don't need much. Influence you're just running with what they're doing and they just need an ear now and then. Others need a little prodding. Others need to be persuaded to collaborate among themselves rather than working alone. Have their personal ups and downs, so you have to deal with each student as a human being Bring out the best.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Because it gives you the ease to deal with any situation that comes up in the classroom. And if you discover that you're not getting through one way, you can do it another way. If the students have questions, you can handle the questions.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“And so I sort of take pride, at least in my early years as a faculty member at Berkeley, I was exemplary in preparing my lectures and I always came in prepared to the teeth and able, therefore, to deviate according to what happened in the class and to really really provide a model for the students.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“On rare occasions, I would get a chance to sneak into his classroom and observe. observe it and I think he was at his best in the classroom. I think he really came to life. And had fun not only teaching but But engaging in chit-chat with the students and ingratiating himself with the students. And what I inherited from that is the great desire to be a teacher. I retired recently and a lot of my former students came, students with whom I had done research or who had read my papers or who had been in my classes. And when they talked about About me. They talk not about my about what came away in my classes and not just the details but just the approach and the manner of teaching”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Seeing him standing in front of a class at the blackboard, drawing perfect circles. and showing his ability to Attract the interest of the motley collection of eighth grade students that he was teaching”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, it's a big data, it's a statistical big data problem for sure. So, you know, the biological data sets are increasing. Our ability to Study our ancestry to study the tendencies towards disease, to personalize treatment according to what's in our genomes and what tendencies for disease we have. To be able to predict what troubles might come upon us in the future and anticipate them to Understand Whether you For a woman, whether proclivity for Breast cancer is so strong enough that you would want to take action to avoid it.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, I mean, we can certainly analyze genomic data to figure out which genes are operative in the cell and under what conditions and which proteins affect one another, which proteins physically interact. We can sequence proteins and modify them.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, so it raises very severe ethical questions. Um And even doing it on individuals There's a lot of hubris involved that you can assume that Knocking out a particular gene is going to beneficial because you don't know what the side effects are going to be. So we have this wonderful. New world of gene editing. Which is very, very impressive and it could be used in agriculture. It could be used in medicine in various ways. But very serious ethical problems arise.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“But it raises a lot of questions. You have to distinguish between doing it on an individual or doing it on somebody's germline, which means that all of the descendants will be affected.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“It's amazing, and what's really amazing is that we are beginning to learn how to edit. which is very fascinating This ability to Take a sequence, find it in the genome, and do something to it.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Oh maybe, yeah. I guess you can say the same thing about our brain that when we perform acts of cognition, we have no idea how we do it, really. We do, though. I mean, At least for the visual system, the auditory system, and so on. We do. Get something understanding of the principles that they operate under. for many deeper cognitive tasks. We don't have that.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“It's a function. It's a computable function. Once you have the network, you can simulate it on a given input and figure out the output. But if you're trying to recognize images. then you don't know what features of the image are really. determinant of what the circuit is doing. The circuit is Sort of very intricate and it's not clear that The simple characteristics that you're looking for, the edges of the objects or whatever they may be. They're not emerging from the structure of the circuit.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“AI at their disposal, then they can solve all kinds of problems. But there are limitations One is that the solutions that you get to supervised learning problems through Convolutional neural networks. Seem to perform amazingly well, even for inputs that are outside the training set. But we don't have any theoretical understanding of why that's true. Secondly, the solutions, the networks that you get. Are very hard to understand, and so very little insight comes out. So, yeah, yeah, they may seem to work on your training set, and you may be able to discover whether your photos occur in a Different sample of inputs or not. But we don't really know what's going on. We don't know the features that distinguish the photographs or the objects are not easy to characterize.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, it's really very different from the theoretical computer science world because the results about algorithmic performance tend to be empirical. It's more akin to the world of set solvers where we observe that for formulas arising in practice, the solver does well. So it's of that type. We're moving into the empirical evaluation of algorithms. Now, it's clear that there have been huge successes in image processing, robotics, natural language processing, a little less so, but across the spectrum of game playing is another one. There have been great successes. And one of those effects is that it's not too hard to become a millionaire if you can get a reputation in machine learning and there'll be all kinds of companies that will be willing to offer you the moon because Think that if they have”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, I think it would be evidence that NP doesn't have small circuits because something so bizarre would happen. Again, it's only evidence, not proof.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Harder and harder to solve And what Lifted and I showed was that if NP had small circuits, then this hierarchy would collapse down to the second level. In other words, you wouldn't get any more mileage by complicating your expressions with three quantifiers or four quantifiers or any number.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, so the NP. And NP deals with statements of that kind that there exists a solution. Now you could imagine a more complicated expression which says for all X there exists a Y such that Some proposition holds involving both x and y. So that would say, for example, in game theory, for all. Strategies for the first player. There exists a strategy for the second player such that the first player wins. That would be at the second level of the hierarchy. The third level would be there exists an A such that for all B, there exists a C that something holds. And you can imagine going higher and higher in the hierarchy. And you'd expect that the complexity class, the classes that correspond to those different cases would get bigger and bigger What do you”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“So we have to define this hierarchy in which the first level of the hierarchy is P and the second level is NP. And what is NP? NP involves statements of the form. There exists a something such that something holds. So, for example, there exists a coloring such that a graph can be colored. Only that number of colors, or there exists a Hamiltonian circuit.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“What we proved is that if that were possible, then something strange would happen in complexity theory, some high-level... Which I could briefly describe. Something strange would happen. So I'll take a stab at describing what I mean.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“That would be hard, yeah. But there's the existential question. Everybody talks nowadays about existential questions, existential challenges You could ask the question. The Hamiltonian circuit problem have a small circuit for every size, for each size, a different small circuit. In other words, could you tailor solutions Depending on the size and get polynomial size.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Now we know that if P is equal to NP, then in fact these problems will have small circuits. But what about the converse? Could a problem have small circuits, meaning that an algorithm tailored to any particular size could work well? And yet not be a polynomial time algorithm. That is, you couldn't write it as a single uniform algorithm good for all sizes.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, there were all kinds of relationships among complexity classes that can be studied. Just to mention one thing I wrote a paper with Richard Lipton in 1979. Where we ask the following question. If you take a combinatorial problem, And you Choose and you pick the size of the problem. Say it's a traveling salesman problem, but of size 52. And you ask, could you get a small Boolean circuit tailored for that size, 52, where you could feed the edges of the graph in And get as an output the question of whether or not there's a tour of a certain length. And that would, in other words, briefly what you would say in that case is that the problem has small circuits, polynomial size circuits.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“They haven't really come together, I would say that there is a field of experimental algorithmics where people sometimes they're given some family of examples. Sometimes they just generate them at random and they report on performance, but there's no convincing. Evidence that the sample is representative of anything at all.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, there's nothing available there that would be analogous to the training set for supervised learning, where you sort of assume that the world has given you a bunch of examples to work with. We don't really have that for. Problems for combinatorial problems on graphs and networks.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Not really. Don Knuth started to collect Examples of graphs coming from various places so he would have a whole zoo of different graphs that he could choose from and he could study the performance of algorithms on different types of graphs.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“The field tended to be rather lukewarm about accepting these results as meaningful because we were making such a simplistic assumption about the kinds of graphs that we would be dealing with. So we could show all kinds of wonderful things. It was a great playground. I enjoyed doing it. But after a while, I... Concluded that That it didn't have a lot of bite in terms of the practical application.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“And within that model, I could prove all kinds of wonderful things and others who also worked on this. So we could show that we know exactly how many edges there have to be in order for. there be a so-called Hamiltonian circuit that's a cycle that visits each vertex exactly once. We know that if the number of edges is a little bit more than n log n we're in is the number of vertices, then such a cycle is very likely to exist. And we can give a heuristic that will find it with high probability. And we got the community in which I was working got a lot of results along these lines.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“That's very difficult. So after I did my original work on getting Showing all these problems to be NP complete. I looked around for a way to get some, shed some positive light on combinatorial algorithms. And what I tried to do was to study problems, behavior on the average or with high probability. But I had to make some assumptions about what's the probability space, what's the sample space, what do we mean by typical problems? That's very hard to say. So I took the easy way out and made some very simplistic assumptions. So I assumed, for example, that if we were generating a graph with a certain number of vertices and edges, then we would generate the graph by simply choosing one edge at a time at random until we got the right number of edges. That's a particular model of random graphs that has been studied mathematically a lot.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Geometric instances of the problem where the cities are, let's say, points in the plane and get optimal solutions to problems with tens of thousands of cities. Actually, it'll take a few computer months to solve a problem of that size, but for problems of size 1,000 or two, it'll rapidly get optimal solutions, provably optimal solutions, even though, again, we know that it's unlikely to that the traveling salesman problem can be solved in polynomial time.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“And there are many examples. For example, we talked about the traveling salesman problem. So, just to refresh our memories, the problem is you've got a set of cities, you have pairwise distances between cities. And you want to find a tour through all the cities that minimizes the total cost of all the edges traversed, all the trips between cities. The problem is NP hard, but people using integer programming codes together with some other mathematical tricks can solve”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Right, and that's unfortunate. I think a good example is going back to the satisfiability problem. There are very powerful programs called SAT solvers. Which in practice fairly reliably solve instances with many millions of variables that arise in a digital design or in improving programs correct and other applications? And so in many application areas, even though satisfiability, as we've already discussed is NP complete. The SAT solvers will work so well that the people in that discipline tend to think of satisfiability as an easy problem. So, in other words, just for some reason that we don't entirely understand the instances that people formulate in designing digital circuits or other applications are such that Satisfiability is not hard to check. And even searching for a satisfying solution can be done efficiently in practice.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“So if worst case analysis shows that an algorithm is always good, that's fine. If worst case analysis... Is used to show that the problem, that the solution is not always good. Then you have to step back and do something else to ask how often will you get a good solution?”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“algebraic identities you get two formulas that may look very different you want to know if they're really identical what you can do is just pick a random value and evaluate the formulas at that value and seeing if they agree and you depend on the fact that if the formulas are distinct then they're going to disagree a lot and so therefore a random choice will exhibit the disagreement If there are many ways for the two to disagree. And you only need to find one disagreement, then random choice is likely to yield it.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“So what you can do is draw from the rows according to the number of ones if a row has more ones, it gets drawn more frequently. But then if you draw from that row, You have to go up the column and looking at where that same one is repeated in different rows. and only counted as a success or a hit if it's the earliest row that contains the one. And that gives you a robust statistical estimate of the total number of columns that contain at least one of the ones. So that is an example of the same principle that was used in Studying random sampling. Another viewpoint is that If you have a phenomenon that occurs almost all the time, Then if you sample one of the occasions where it occurs, you're most likely to, and you're looking for an occurrence, a random occurrence is likely to work. So that comes up in solving identities, solving”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“So you have a collection of Formulas And you want to count number of Solutions that satisfy at least one of the formulas. And you can count the number of solutions that satisfy any particular one of the formulas, but you have to account for the fact that that Solution might be counted many times if it solves. More than one of the formulas. And so what you do is you Sample from the formulas according to the number of solutions that satisfy each individual one. And that way you draw a random solution, but then you correct by looking at the number of formulas that satisfy that random solution. and don't double count. So you can think of it this way you have a matrix of zeros and ones. And you want to know how many columns of that matrix contain at least one And you can count in each row how many ones there are.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, the example of conducting an election where you could take, in theory, you could take a sample and depend on the validity of the sample to really represent the whole. Is it just a basic fact of statistics, which gives a lot of opportunities? And I actually exploited that sort of random sampling idea in designing an algorithm for counting the number of solutions that satisfy a particular. Formula and propositional logic.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“value unequal you will get a violation of Fairma's result is very high and so this gives you a way of rapidly proving that a number is not prime. A little more complicated than that because there are certain values of n where something a little more elaborate has to be done, but that's the basic idea. sticking an identity that holds for primes and therefore if it ever fails on any instance for a non-prime, you know that the number is not prime. It's a quick joy, a fast choice, fast proof that a number is not prime.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“just a random picking would be would solve the problem with a very low probability of error. Another example is testing whether a number is prime. So if I want to test whether 17 is prime. I could pick any number between 1 and 17. Raised it to the 16th power modulo seventeen, and you should get back the original number. That's a famous formula due to Fermat about, it's called Ferma's little theorem, that if you take any number of A in the range 0 through n minus 1. and raise it to the n minus 1 power modulo n, you'll get back the number a. The number is if A is prime. So, if you don't get back the number A, that's a proof that a number is not prime. And you can show that suitably define the probability that you will get”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“And I guess thirdly, there could be a tie, in which case we wouldn't have a significant difference between two candidates.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, it's just the ability to draw a random number from... From some range or to associate a random number with some object or to draw at random from some set. So another example is very simple if we're conducting a presidential election And we would like to pick the winner In principle, we could draw a random sample of all of the voters in the country. And if it was of substantial size, say a few thousand, then the most popular candidate in that group would be very likely to be the correct choice that would come out of counting all the millions of votes. Of course, we can't do this because, first of all, everybody has to feel that his or her vote counted. And secondly, we can't really do a purely random sample from that population”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“And so there's a small probability of error which can be checked after the fact. And also the ease of doing the computation because you're working with these fingerprints, which are remainders modulo, some big prime.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Which usually are combinatorial and don't involve the idea of taking a random fingerprint And doing the fingerprinting has two advantages. One is that as we slide along the long word, digit by digit, we keep a window of a certain size, the size of the word we're looking for, and we compute the fingerprint of every stretch of that length. And it turns out that just a couple of arithmetical operations will take you from the fingerprint of one part to what you get when you slide over by one position. So the computation of all the fingerprints is simple. And secondly, It's unlikely if the prime is chosen randomly from a certain range that you will get two of the segments in question having the same fingerprint.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Right. So every word can then be thought of as a number with the letters being the digits of that number. And then we pick a random prime number in a certain range. And we take That word viewed as a number and take the remainder on dividing that number by the prime.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“I like the Rabin Carp algorithm because it illustrates the power of randomization. So The problem there is to Is to decide whether a given long string of symbols from some alphabet contains a given word. Whether a particular word occurs within some very much longer word. And so the idea of the Algorith It is to associate with the word that we're looking for a fingerprint. Some number or some combinatorial object that The scribes that word. And then to look for an occurrence of that same fingerprint as you slide along the longer word. And what we do is we associate with each word a number. So first of all, we think of the letters that occur in a word as the digits of, let's say, decimal or whatever. Whatever number of different symbols there are in the”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“No, no, that was due to Gail and Shapley and my friend David Gale passed away before he could get part of a Nobel Prize. But his partner, Shapley, shared in a Nobel Prize with somebody else for For economics, for ideas stemming from this stable matching idea”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Okay, what's confusing you is that in the first interpretation of the problem, I had boys matching with girls. In the second interpretation, you have humans matching with institutions.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“The fact that you have this additional constraint, that it's not just the preferences of individuals, but the fact that the Partners to a marriage have to be assigned to the same place.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Residents have their own preferences. References residents both male and female have their own preferences. The hospitals have their preferences. But if Resident A, the boy, is going to Philadelphia, then you'd like his wife also to be assigned to a hospital in Philadelphia.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, well, you get complications. For example, what happens when a husband and wife want to be assigned to the same hospital? You have to take those constraints into account. And then the problem becomes NPR.”
2020-07-26 · Lex Fridman Podcast · #111 – Richard Karp: Algorithms and Computational Complexity · IDENTIFIED FROM THE TRANSCRIPT · source