Skip to main content
Loading Explore guides…
Theory of Computation · Acedra
Home
Explore
Computer Science
Theory of Computation
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
176 segments
Copy
Hide video
0:00
[BRUNO] --it's about theory of computation for, for the neuroscientists. And Christos is famous not only within computer science, but he's famous in all of Greece. Uh, one of my students who was Greek a few years ago told me that everybody in Greek, in-- everybody s-- everybody in Greece knows Christos. And that's true.
0:19
Even his mother knows who Christos is. You know, TV, all the [AUDIENCE MEMBER] Time. [BRUNO] So anyways, it's really great to have you. [CHRISTOS PAPADIMITRIOU] Thanks.
0:30
Uh, thanks a lot, Bruno. Delighted to be here.
0:36
Welcome everybody. Uh, I'm welcoming you. I mean, as you know, I work at Columbia, but I've spent a lot of time in this place. And uh, this is, I think, the fourth semester that I'm organizing uh, or help organize, I meant. And I don't think you know it, but you are in for an amazing treat. Okay? So we know that this is a semester like this, especially a semester like this one, which brings into contact two fields, theoretical computer science and another fascinating field is just amazing.
1:15
I mean, we have seen-- we have done uh, quantum uh, Hamiltonian and computation, computation. We have done evolution and computation. Okay? We have done economics and computation. Okay? So and this is great for us, but also for the participants from the other field, you know? So I really mean it that you are in for an amazing scientific experience. And you know, so get used to it, okay? So, you know, we are going to be mingling, we're rubbing shoulders
1:51
or, you know, discussing, you know, you are going to be answering our questions and asking us questions, you know, all semester long. Okay?
1:59
That's a major, major, major enterprise. Okay? It's a mind uh, changing and uh experience. And I think that the computer scientists in the audience have been just amazed by the talks we have seen from neuroscientists so far. And you know, you know, their view of the world, their worldview has changed tremendously. So it falls upon me to reciprocate. Okay? So, you know, and tell you what we are, who we are, okay? So, you know, because I don't expect the people who are not theoretical
2:42
computer scientists to know who theoretical, So in some sense, I mean, I'm not going to talk about computer science, but I'm going to talk about uh, really a cultural anthropology of, of theoretical computer science. Okay? And I mean it, okay? So, you know, I mean cultural anthropology. Okay? Right. So, where you try to understand sort of, you know, the mysterious inner workings of a tribe. Okay? Right. I mean, so the language sort of, you know, the behavior, so, you know, everything, you know,
3:14
So The history, all right? I mean, so this is what we are after, right? So good. So let's start. Okay? So, and you know, of course, you have to start with the history of the tribe, okay? You know, and in doing so, I could do worse than starting with this man here. Okay? You know, So what he did in at the age of 34, Okay? So, you know, occasionally I read-- uh, I, I teach a course in which we read his paper of, you know, PhD, PhD course that you know, I used to teach it at Berkeley.
3:52
Where we read his paper. And so, you know, it's, I think it's a singular experience for graduates-- for graduate students, because here is somebody who at the age of 24, their age, okay realized that something is very, is missing from science and took a semester off and then changed the world. Okay? You know, so that's sort of, that's an interesting that's a very interesting exemplar. So in 1936, he invented the Turing machine. He didn't call it that, but, I mean, the co-Turing machine,
4:21
and the reason he did it, is because he wanted to answer a mathematical challenge. Okay? And the mathematical challenge, the, the predominant mathematical challenge at the time, that's after Godel's theorem, is can math be automated? Okay? Uh Godel had shown that math cannot be complete, but math was still being done. Okay? So can the incomplete math that was being done, can it be automated? And for this, he invented this machine. Okay? For the first time, define what computation is, all right?
4:50
And it's sort of interesting, and maybe it has some didactic value for other sciences, including neuroscience, that mathematicians, before this moment, had not bothered to define what computation is. Okay? They were thinking about computation, they were seeking computation, but they had not bothered to define it. And the moment they defined it is precisely the moment when they needed to prove that computation is impossible.
5:23
Okay? And that's a very interesting, I think philosophical, so, you know, philosophy of science, philosophy of mathematics point, that if you want to show them computation is possible, okay, you don't need to define computation. The moment you want to show that computation is impossible, you need to define it, okay? You know, in order to show that you-- that the world is outside a particular area, you have to get inside the area and map it. Okay? So that's-- in any event, that's, that's the
5:51
story of, of Turing. And basically, what he came up is a very minimalistic conception of what computation is- And he taught us another very serious, very important lesson that to put it so, universality, that it hardly takes anything to have everything.
6:17
Okay? And this is a lesson sort of, you know, that is also uh, makes sense in other contexts, for example, in evolution, okay? So we know there is the wa-- the Wallacean fallacy, okay? Which basically if selection is a force, how come Africans are good at piano, okay? So we know they never used this, okay? You know, they never needed this. And you know, and after that, you know, because of that, it is about selection, okay? And his fallacy is this, that it hardly takes a you
6:47
know, in other words, that you have universality, okay? So you know, if you have this thing here, okay, you can do many other things, okay? That you can learn a lot of things. So in any event, that's the-- that's another good lesson. Incidentally, universality means another thing, means it's about learning, means about is about software, okay? So we know that you can have a machine and then teach it to do other things by just inserting the right bit stream, okay? That's--
7:20
Th-- that's something that Turing taught us. All right. So, one other thing that he did is he-- which is extremely important and marked the life of computer science since then, is that he proved that there are computational problems that are unsolvable, okay? He also ci-- studied the mind. So, you know, he defined artificial intelligence and as you know, during the second World War, came close to saving the world. Okay. So and here is his very important theorem that
7:54
there are simple-to-state mathematical problems that are impossible to solve, okay? And you know, anybody who works with very hard problems, okay, problems that warn you, okay, so you know, with all blinking lights that they're very hard, okay? You know, it's important to keep this in mind, all right? I mean, and if you are given a program, a MATLAB program, right? I mean, you know, and the numbers that we'll, you know, w-- it will input will it halt or will it loop, okay?
8:33
It turns out that can you, you know, think about it, I mean-- can you think that you know, can you figure out why it is unsolvable? It is unsolvable, okay? You cannot write a program to solve this problem. Okay? And the proof is not hard. It's quite easy, okay? In any event so one, the consequence of this is that computer science was born painfully aware of its own limitations, okay? So, as opposed to most other sciences, which become aware of their own limitations like the rest
9:11
of us, okay, in old age, okay? So and so for example, because the fact that this problem is unsolvable also means that there is no program that can tell you if this program is correct, okay? Or if this program will print anything, okay? Or if this program is a virus, okay?
9:38
So all these things are impossible and we learn to live with that, right? So that's the-- Okay. And also it gave computer science a-- We are all essentially mathematicians at heart, okay? So, all right. So good. Uh and then 10 years later von Neumann, deeply influenced by-- by Turing's ideas uh, defined the, you know, ba-- basically defined what computer is.
10:12
He wrote this amazing paper and built it, okay, at the same time, the same month, all right? And that's And I mean, built it.
10:19
He was part, he was the theoretical mathematical consultant of brilliant engineer, engineering team that built it, okay? But of course he gets all the credit. Okay. So okay. So excellent. And that's the beginning of our field, right? So uh, so what I'm going to tell you is uh, the status quo 27 years later. I'm gonna tell you about algorithms because that's what we do.
10:47
I'm gonna tell you about randomness or, you know, latching on-- on-- on what Wolfgang Maass told us three-- two days ago.
10:55
He basically told us that, "I think that we ne-- we have to need ran-- we have to use randomness in our modeling of the brain." Okay? We have, you know, we need-- we need much, much more randomness to, you know, and-- and-- and I-- I-- I-- I heard him, so, you know, so I'll tell you a few things about randomness and how computer scientists use it and face and sort of confront it.
11:16
I'll tell you about complexity. So, you know, the P versus NP problem, which in some sense is the major intellectual export of our field, okay? So, you know, it's-- it's-- It's probably uh, you know, if-- if-- if some of you know only one thing about computer science, it's probably P to the P versus NP problem, so I'll-- I'll-- I'll have to, I have to mention it. Then I'll have, I'll tell you what, you know, computer sci-- What computer scientists have-- uh, mostly theoreticians,
11:43
but also, but also uh, machine learning people and AI people, how uh, how they have been thinking about learning. Uh and then-- I'll tell you a few things about how computer science in the past has been engaged very productively, I think, with other sciences Be-- be-- you know, before neuroscience, okay? You know, and-- and-- and-- and uh finally I'm going to end uh giving you sort of, you know, a humble re-- here, a humble example of how might a computer scientist think about the brain, okay?
12:17
So then I'll tell, I'll talk about my work. All right? And then also this will probably be the last 10, 15 minutes. [AUDIENCE MEMBER] Good. [CHRISTOS PAPADIMITRIOU] Okay. So let's start it, okay? So since you know, the 70 years since 1946 have been really good years for computer science, okay? So, you know, so in order, you know for the vast majority, for, you know, for 50 out of these 70 years, scientists have been studying the computer, okay? Which now is sort of makes no sense, all right?
12:57
I mean, no, but we were obsessed with the computer for 50 years. I mean, and we did a lot of great work with it, okay? We solved fantastic engineering problems, you know, with operating systems, compilers, okay? So compilers, I mean, they were taking you know, operating systems and compilers, when they started in the '50s, they were taking sort of tens of you know, tens and many tens of personal years to build, all right? I mean, and now, they are sort of,
13:33
you know reasonable term projects for courses, right? I mean, so these are very difficult engineering problems that we solve. Databases right? I mean then machine learning, chips, okay? How to lay out chips.
13:47
Graphics okay? Networks, sleek interfaces, and then of course came the Internet, which changed everything, and basically the last 20 years, we forgot about the computer, sort of, you know, we didn't quite forget about it, sort of, you know, we use it, sort of, you know, we remember that it's the gadget that brought us the Internet. But we are all students of the internet, okay? You know, so-- so that's the-- And-- and-- and the point is that all this edifice, okay, all this sort of uh,
14:16
the information technology that surrounds us, okay, it has changed our lives, okay?
14:24
It's coming from you know, if I really had to men-- if you have to mention two engines, okay, so you know, that drove this, okay? Which would it be? So I'll tell you what my choices are, okay? Uh, one, first of one, first of them is is Moore's Law, okay? The amazing fact that for the past 65 years, you know, in a clockwork precision, computer speed has been, you know, computer capability, let's say, let's pick more generally, has been doubling every year and a half, okay?
15:01
So, and this is not a physical phenomenon. It's not a scientific phenomenon. It is a social phenomenon, more or less, okay? Because somebody predicted it 60 years ago, sorry, 50 years ago. '64. Okay? And since then, sort of, you know, if everybody's business plan is a straight line in log chart, okay? Then then it's, then the competition becomes intense, right? I mean and if you fall behind, you strive not to, okay?
15:41
And then you have to sell it to society, okay? You know, and society will buy it, okay? And so it, you know, it's this amazing triad, sort of, you know, that science, business, and society sort of, you know, they were pulling each other sort of, you know, haphazardly through this amazing race. And-- and even now that we all know that-- that-- that Moore's Law has stopped, okay? Sort of, you know, it's still going, okay? You know, and we'll see, we'll see, we'll see what
16:09
happens in the next years. I mean, I'm sure that there for the, that we'll keep, we'll keep finding amazing sort of, you know, ingenious ways to keep it going. So Moore's Law is, has been fantastic. Without it, you wouldn't have all this, okay?
16:23
What's the second one?
16:26
You may be surprised. The second one is fast algorithms, okay? That-- that without fast algorithms, Moore's Law would be a-- A w-- you know, first of all, it wouldn't continue, okay? I mean it is fast algorithms. Without fast algorithms, you cannot bring to bear Moore's Law, okay? You know, you cannot bring it to applications. Okay? I mean uh, and-- and in other words, what I'm saying is that a dramatic increase in computer speed needs to be coupled with efficient
16:59
algorithms, because without it, there are no gains, okay? If algorithms are exponential, they take zero advantage of Moore's Law, okay? Okay, so this is sort of, you know, And-- and algorithms is what I'm going to tell you about start my talk with. And this is what we do, okay? And let me start with something that we start our courses our algorithms courses with, and that's multiplying 2n by n matrices, okay? You have 2n by n matrices. Think of it as a thousand, you know,
17:34
a thousand by a thousand of, you know, two matrices, and you want to find the product, all right? And we have all done it in algebra courses, right? I mean, we have carried out this computation. And we all know that it takes n cubed operations. Why? Because you have n square results and when I say n cubed, I don't mean exactly n cubed. I mean order of n cubed. All right? I mean, this is a trick that hides constants, or you know, it does this like this. All right?
18:04
I mean, in fact, it's, if you want, the classical algorithm is two n cubed minus n squared. Okay? But who cares? It's n cubed, right? And the question is, I mean, this is what, this is sort of, you know, the most frequently asked questions in computer science: Can you do it faster? Okay? And we ask again and again and again and again. So and do you think it can be done faster? What do you think? Let me know. Uh though there are --You know, many of you know, but --It can,
18:38
but but the fact is that there, there is a, there is a dozen mathematicians who are on record saying that obviously it cannot be done faster than n cubed, and one of these, you know --and soon I'm going to find one day and sit down and prove it. Okay?
18:54
And they were wrong. Okay? And uh, who proved them wrong is Volker Strassen, who probably within uh, 300 yards from here, he was, he was at Berkeley when he did that uh, came up with a ingenious algorithm that runs faster than n cubed. All right? I mean, and this is something that shook the world, shook the world of algorithms, all right? I know that, there is a lot of to be done in this field, okay? I mean, and, I mean, if you are curious, the way he did it is he discovered a clever algo--
19:28
you know, not clever, a stupid algorithm for multiplying two by two matrices, okay? This algorithm was using not two cubed minus two squared, in other words the 12 operations. It was using 15 operations, okay? Except that it used only seven multiplications, all right? I mean, so this stupid algorithm was the basis of, you know -- he used it recursively. In other words, when he looks at a huge matrix, he sees it as a two by two matrix, each of its elements being matrices, okay?
20:06
And then, he recursively applies this, and therefore we have this ingenious algorithm which, people kept asking the same question "Can you do better?" And after that, and in the intervening 50 years, we have more than a dozen improvements. And now we are stuck here. We have been stuck for some time around there, you know, even though small improvements come along.
20:39
Okay, so that's autobiographical. Uh, when I started my, my PhD thesis in 1973 that was, that was soon after Strassen, we were all sort of, you know, we're living with aftershocks from Strassen's algorithm. And my thesis problem was to prove an n squared log n lower bound. Okay? You know, so I'm sort of glad that I abandoned this problem and turned to NP-complete-ness, okay, because this, this, this was proved, but it was proved 30-something years later by Raz and Spilka, okay, you know?
21:08
So in any event, you know, it's a simple proof that we know. And it's simple because it uses randomness, okay? It's basically one of these probabilistic method proofs, okay, you know, that uses randomness, I mean. And randomness is my next topic, because theoretical computer scientists, okay, so, you know, they are quirky folks, okay? You know, but they love randomness. Okay? You know that randomness is sort of, you know, their middle name. Okay? You know, so let me tell you about randomness.
21:44
You know, randomness is our friend. Okay? Really okay? So, you know, we live by randomness, we swear by randomness, we work with randomness. So, you know, we harness randomness, we use randomness, okay? Uh, for example I'm, I'm sure many of you know, but some of the most clever algorithms are randomized algorithms okay?
22:03
Randomization is very important, okay? So, you know, it's sort of absurd, but it's very true, that sometimes the most clever, the most deliberate, okay, the most certain thing you can do is flip a coin. Okay? For example you know Quicksort perhaps, okay? It's what, it's what it's what for example, Excel uses to sort to sort the col-- the, the, the rows of, of a matrix, right?
22:35
Of a table.
22:37
Or a sheet. So how it's done? It's done by randomization. Why is that? Randomization has two --It works in two interesting ways in computer science. Number one it guards against bad inputs, okay? If your input is bad, you know, flipping a coin makes it not so bad. Flipping three coins makes it okay. All right? And we know --and That's what quicksort does. Okay, so in some sense sort of protecting you from a bad adversary. You know, from somebody, you know, a bad guy who feeds you bad inputs.
23:10
All right? Now we know that's what randomness does best, okay? Here is something else that randomness does. By sampling, it helps you test between two competing hypotheses okay? And that's also very important. You know, here is a great application of this last You know, that you all, you have a number, you have a huge number, okay? You have a number that has 190 digits, okay? And the question is, is it a prime or not, okay?
23:47
And I mean, there is no way to see how to solve this, okay? You know, is it a prime number or, you know, and it turns out that the fastest algorithm we have does the following. You take this number and says, "There are two competing hypothesis. This is a prime, this is not a prime." Okay? If it's a prime, we know from Fermat, from Fermat's theorem, that A to the --You know, if you take any number less than A, less than N, and you raise it to the Nth power, you're going to get N--
24:19
sorry, modular N of course, we're going to get A again, okay? That's something that has been known for two and a half centuries, okay, good. So to test if prime, you say that. And so the secret is, and I'm, I'm hiding some details that, that, that, that are not very important. The secret is that if the number is not a prime, then most of these A's will be weaknesses. Okay? In other words, you, you are, you are very likely to discover, you are half-- Uh, you know, your, your chance of discovering
24:55
an A that falsifies pri-- Fermat's Theorem is half, okay? This means that you test an A, it satisfies. If it doesn't, you say, "Oops, got it." Okay? "it's not a prime." Right? But if it does, you say, "Okay, looks good. Let's try again." And the point, you know, if you try 100 times, okay, you know it's not a prime. You know it's a, Sure, you know it's a prime.
25:24
You get it? Okay, so you know now I know that many of you are thinking, "Wait a minute, I thought you guys were engineers." Okay? You know, is it a responsible engineering behavior to say, "Okay, so we know, looks fine, okay, let's assume it's a prime." Right? You know, so okay. I have one number for you, 2 to the minus 100. Okay? 2 to the minus 100, trusting luck for 2 to the minus 100 is not irresponsible. Believe me. Okay? You know 2 to the minus 100 is smaller than the
26:00
probability that your computer will be destroyed by a meteorite at one particular nanosecond of its operation.
26:08
Okay? I, I've done the math. It's true. Okay?
26:12
So you know, if you want to make your algorithm more sure than that, that's irresponsible. Okay? That's a waste of time. Right? So yeah. Yeah, all right. So oh, good. [SHAI] I have a question, I mean, just a comment, that it's not really making your algorithm faster, you're just changing your success criteria. Before, you were talking about worst case, and now you're talking about success with probability. [CHRISTOS PAPADIMITRIOU] I'm, I'm talking about the worst case again. Yeah.
26:39
[SHAI] But success with probability, rather than just-- [CHRISTOS PAPADIMITRIOU] Uh yeah. Good. Thanks for the clarification. But that was my point. Uh, incidentally this algorithm can be solved deterministically, but instead of B squared, B to the, B to the eighth steps, eighth power steps, and that's sort of, you know, an amazing amazing mathematical result by, by three by three uh Indian computer scientists, okay? So good. Incidentally, you know, so randomness is our
27:20
friend and really, random graphs are our friends, okay?
27:26
For example, okay?
27:29
Here is the classical model of random graphs. And I'm not saying that the brain is like this. We know the brain is not like this, or you know, there are probably a few hundred papers in the last five years telling us that the brain does look like this. Okay? But here is the idea. You-- This is, this is the graph, a very ancient source, 60 years old model by two great Hungarian mathematicians, Erdos and Renyi. And basically it says, suppose that you have end points, let's say 2,000 points.
27:58
And if you take any two of these points, what is the chance that there is a line between them? Okay? You can take directed, you can take the undirected. This is two different models, but they're extremely related. They're sort of the same. Let's say undirected.
28:11
The probability, let's say is 1% that there is a line between any two points, and that's independent. You know, if you take any two other, any two pair of points, even if they share a point, that's fine. They're independent. Okay? That you make independent draws. Okay? So to create this graph, you are going to go patiently through every pair of nodes, okay, two million times, and throw a, you know, flip a 1% coin. Right? And then you're going to have a graph. Okay?
28:46
All right. Here's my point. Now this graph is my friend. Okay? So you know, I have intimate detailed knowledge about this graph. [AUDIENCE MEMBER] Okay? [CHRISTOS PAPADIMITRIOU] You know, if you give me a stick with a graph data set it will take me years to understand this data set as much as I understand this graph. Okay? I can tell you anything you want about this graph. Okay? So this graph is going to be connected, okay? I bet my, I bet my house on this, okay? You know, it's going to
29:17
be connected. It's going to be what? It's going to be doubly connected. In other words, any two points are going to have two disjoint paths between them. Uh, I'm pretty sure it's gonna be triply connected, okay? And I'm pretty sure it's not going to be quadruply connected, okay?
29:34
I think it's going to have between 13 and 1400 triangles.
29:40
Okay? Um, it's going to be what? Its diameter, okay, in other words, how many handshakes are two people away, it's not gonna be six degrees of separation. There's gonna be three degrees of separations, okay? Well, maybe four, but not five, okay? You know, it's gonna be at most four degrees of separation.
30:00
Is there going to be four nodes that are all connected?
30:04
I think so.
30:06
Five? Probably not.
30:09
Okay?
30:11
Also, it's going to be what you call an expander, okay? Expander means that you cannot take cheap bites out of it, okay? In order to disconnect a part of this graph, you have to pay a dear price for every node you disconnect. Okay? So, I really know a lot about this graph. All right? And we know, even though I've never seen it. All right. I mean, so that's you know, this is and these graphs, you know, are a big, big part of what we think about. So, let's go back to primality being easy.
30:54
How about factoring, okay? So this is something that I run my algorithm, and I know it's not a prime, okay? So, you know, I found an A, but, I mean, you know, this A does not tell me anything about these factors, okay? So how do you find the factors?
31:08
The amazing thing is that primality is easy and factoring is hard, okay? And if you think about it, you know, the curious fact is that modern, modern cryptography is based on this dichotomy, okay? That primality is easy and factoring is hard. [AUDIENCE MEMBER] All right.
31:23
[CHRISTOS PAPADIMITRIOU] Okay. So we don't know.
31:27
And not only we don't know, but the best mathematicians in the world have worked on this problem for 25 centuries. The fastest known algorithm is exponential in the number of bits, and modern cryptography is based on the assumption that this problem is hard, okay? So this is, these are very interesting facts, I think. All right.
31:44
So incidentally my point here is that we also understand complexity, not just randomness. So complexity, and in fact, it's occasionally our friend, for example, in cryptography, right? I mean, we use it, okay? You can use complexity, you know. Uh Manuel Blum here, so, you know, is one, is one of the mo-- first masters of using complexity this way.
32:09
On the subject of complexity, okay?
32:12
Let me show you, you know, these numbers, right? I mean, let's do some operations on them. Add them. Sure. Multiply them.
32:21
[AUDIENCE MEMBER] Sure.
32:24
[CHRISTOS PAPADIMITRIOU] Okay. Omitted, you know, sorry, it's two lines.
32:28
What else do you want to do then?
32:32
How about this? How about partition them into equal parts, okay?
32:38
Can you cut this cake in half, okay? Okay. These are the balances of bank accounts, you know, to be divided between two twin brothers, right? I mean, you know, how do you do this?
32:58
Okay. I know. I created, you know, there is a hidden-- Yeah, But you don't know, okay? You'll, you won't find out, okay?
33:06
This is a hard problem, all right? Okay.
33:11
How about this one? Matching. Matching boys and girls, okay?
33:20
It turns out that matching boys and girls is can be done, okay? And in fact, the champion algorithm was discovered by two Berkeley graduate students uh uh, al-- almost exactly 40 years ago. Uh uh, Vijay Vazirani was here yesterday, and the other is Silviu Micari at MIT, and can be done in n to the 2.55. Okay, in other words, polynomial still, okay?
33:51
That's good. All right. I mean, it's a very important problem. We've-- We are delighted we can solve it.
33:58
But how about it, we make it a little harder, right? I mean, say that we have to match, you know, there are four boys, four girls and four pets, okay? So, you know, a horse, a boa, a squirrel, a chicken, okay? So, you know, and, and, and you have triangles that tell you that uh, Phil, he likes Bill, then they can also, they can also live with a squirrel, okay?
34:23
And you know, there is a reason why there are not many online sites that match boys, girls and pets, right? I mean, and the reason is that this problem is hard, okay? You know, even though boys and girls is fine, three-way matching is not, okay?
34:42
Okay.
34:44
So we don't know.
34:46
Another one. At Facebook, you know, I've-- --I've read about six degrees of separation. Does it apply to me? Am I six degrees away from everybody, okay?
34:57
You can find the answer in linear time, okay? The hard part here is convincing uh, Facebook to run your algorithm on their, on their network, okay? Right. So right. But how about if I ask this question? Are there 60 people in Facebook who form a clique, who are all friends between each other, okay?
35:16
We don't know. We don't know how to do this.
35:22
The set cover problem, right? I mean imagine that I give you these words, all right?
35:27
And I'm asking you, "Can you cover the alphabet using them,
35:35
using as few words as you can?" Okay. Choose few, as few words as you can to cover the alphabet. [AUDIENCE MEMBER] Okay.
35:44
[CHRISTOS PAPADIMITRIOU] That's difficult.
35:48
Okay, that's a hard problem. That's called set cover.
35:53
So here is an intriguing contrast.
35:56
You have these problems and these problems, right? I mean, they seem to be come from two different worlds. That's sort of, you know, this one can be solved in polynomial time. This, the other ones seem to require exponential time, right? I mean, so what's going on, right? I mean, there seems to be an invisible line between them. What is this line? And this is the line, to discover this line, we have to talk about a special kind of algorithms called reductions, okay?
36:24
So remember the three-way matching, okay? The boys, girls, pets. Remember the number splitting, okay? Numbers numbers, numbers numbers. Can you split them in half, all right? It turns out that if you had an algorithm for number splitting, you would be able to solve three-way matching.
36:40
You had a hypothetical algorithm, which sus-- we suspect it doesn't exist, okay, for uh, for number splitting, you could use it and and sort of, um, The trick is, or you know, if you are interested in-- in thinking about it, is to arithmetize each boy-girl-pet triple by, Uh, in a s-- as a, as a sparse zero-one vector that has all zeros except of three ones, okay? And from these vectors, you can sort of see why it's ver-- you know, if you knew how to split the number into two, you could solve the
37:18
three-way matching problem. Okay?
37:21
So, if you forget about factoring, which is a special case all of these problems seem to require exponential time. They are equivalent, okay? If you can solve one, you can solve all, okay?
37:38
You can reduce it, you want each one to each other, and they're called [AUDIENCE MEMBER] Np-complete. Okay? [CHRISTOS PAPADIMITRIOU] That's what NP-complete means. What does it mean exactly? Np are all the problems that can be solved by exponential exhaustive search, all these problems that I showed you, if you have the patience to go through an exponential number of solutions, you'll find yours, okay? Or decide that it doesn't exist.
38:00
P on the other hand, are all the problems that can be solved in polynomial time, okay? And NP-complete means the hardest problems in NP. And most researchers believe that P is not equal to NP, and I agree, and NP-complete problems are intractable, okay? So, there are thousands of NP-complete problems, one is discovered every day. How do you prove a problem NP-complete? You have to find another NP-complete problem and reduce it to your problem, okay, and that's how you prove it NP-complete.
38:33
But then, this creates a chicken and egg situation, what was the first problem? Well, in 1971, Stephen Cook proved that SAT, satisfiability, the problem in Boolean logic, is NP-complete. How about factoring? Long story. What does hap-- when does NP-completeness mean in practice?
38:52
It doesn't mean that you should never, you should not talk about, or you should not work on this problem. You should you know, maybe you should work hard on it, hard on it, try to approximate it, try to find a heuristic, try to do something, but at least you'll do it with sort of, you know, a light heart, in the following sense: that you are pretty sure that it's unlikely that a clever kid is going to knock on your door tomorrow and say, "Hey, I have this two-line algorithm
39:17
that solve this problem." Right? And you go, or maybe such a clever kid will, but it will be sort of, you know, the most interesting day in your life, because you have you know, it has been established that P equals NP so, you know, and the world will be a different place. Okay? So and when will we know about if P equals NP? Frankly now, not only we are stuck at proving that P is not equal to NP, but we also know why we are stuck. Okay? And then sort of, you know, and this means that the younger
39:54
computer scientists in the audience should tool up and Yeah, go to work. Okay? So I hope you realize what I mean. So you know that-- that-- that-- by sort of, you know, by understanding A Tribe, you start-- start even-- even sort of, you know, penetrating this-- this this alien language, okay? You know, so okay. So, is P equals NP?
40:20
I don't know.
40:24
I don't know. Okay?
40:28
No no. Okay? So, I mean, oh, it's, I think, you know it's one of these problems, right? I mean, no, that-- that if we, you know, that frankly for me, these problems are motivation to extend human life on Earth as long as possible, because we need to solve these problems, right? I mean, oh, Yeah, So okay. Uh, so uh, so let's let's, uh-- Uh, where we are uh, computer science, to brag a little, is the creator and curator of an essential technology,
41:06
it's the founder and head around the most fundamental question in mathematics and arguably, all science: can we do something else? Okay, so, so I'll tell you I'll tell you uh, So here's what lies ahead. Uh, I'm going to tell you about learning algorithms. I'm going to tell you about
41:24
TCS and the science, TCS and evolution in particular, and theoretical computer science and the brain.
41:33
[AUDIENCE MEMBER] Okay.
41:36
[CHRISTOS PAPADIMITRIOU] Are there any questions? So, you know, I've been, I've been uh-- Yeah. [AUDIENCE MEMBER] So my question is suppose I'm interested in algorithms that are not perfect, meaning that I want to divide a set, but, you know, if there is a tolerance, you know? Yeah yeah. Then all this NP-- You are in [CHRISTOS PAPADIMITRIOU] Luck. You are in luck. Yes, so for this particular problem, the splitting problem, you can do it. You know, for other
41:59
problems for the clique problem, you can't do it. Yeah so How do you [AUDIENCE MEMBER] Define NP if-- if I-- I mean, how do you define it in this context that I'm not interested in this topic? So, [CHRISTOS PAPADIMITRIOU] You're right, you're right. So, you're asking an amazing question, okay? It, we know, the P question was asked in '71. Your question was asked in '73.
42:25
It was answered in '91. Okay? So we have a way of defining NP to address the
42:31
approximability problem, okay?
42:35
And so there is a beautiful, you know, it's probably one of the most beautiful theorems in theoretical computer science, it's called the PCP theorem, and it does exactly what you want. Okay? And it classifies, for example clique as something, you know, plus other work that happened in between, as something that cannot be done, whereas splitting, no problem.
43:02
[AUDIENCE MEMBER] I can't resist-- [CHRISTOS PAPADIMITRIOU] Please. [AUDIENCE MEMBER] --asking a-- [CHRISTOS PAPADIMITRIOU] Don't. [AUDIENCE MEMBER] Terrible question. Yeah. Which is, so for life the only algorithm you can afford is some sort of gradient search. And so, the PMT question is just to ask it, you have to come up with a symbol system that allows you to sort of punk away like with some sort of gradient or graduate search, graduate student search. Um, your-- You're just
43:30
doing se-- you, you're getting
43:33
translating it into something that you can do on the cheap. [CHRISTOS PAPADIMITRIOU] Right, right, right. So, you are absolutely right. I mean, so really, you know this theory is not like, a practical guide sort of, you know, that, you know, it's sort of a research methodology whose real goal is not to solve problems, but to identify the right problem. Okay? So, what I'm saying is that computer scientists are interested in exactly the same thing that you are interested. Okay?
44:14
That we want to ask the right algorithmic question, okay, which can be answered within the framework that is available to the particular domain. Okay? So, you know, and, and this is, you know, And but what I'm saying is that when we say, "Is this the right question?" No, no, it's N complete. You know, so you know, it's, you cannot, right? You know, so it cannot be the right question, right? I mean, so what is the right question? And this is something that we have been doing for a
44:44
very long time since this theory was established. Okay? But I mean uh, it's, uh --And I'm going to show you, right? I mean we are interested in life, okay?
44:58
You know, we have worked, you know, computer scientists, I mean, there's computational biology, right? I mean, and a lot of theoretic computer scientists have migrated to that, right? I mean, so a lot of our colleagues are, you know, doing computational biology. I have worked on evolution, okay? And I'm going to show you some things about evolution, where evolution actually does something other than the gradient descent which sort of, you know, I hope, I hope you find interesting. Okay? Good.
45:22
Excellent. So learning, right? I mean, so there are many kinds. Uh, Santos is going to talk next about unsupervised learning. Yes. I'm going to tell you a little about supervised learning. I mean, I'm going to give you a sprinkling of results that we know about s-- supervised learning, and my motivation is the following: That that that uh,
45:45
obviously, the word learning, okay, so you know, is, is, is of interest to everybody here, okay? So I want to show you what we mean in computer science for that, by that. Okay? And what we know. And so we know, we know something. So let me tell you, let me start with a very interesting problem that we call online learning, okay? The expert's problem. So let, you know, bear with me, it's a really fascinating problem. All right? Uh, so every morning, you wake up, and, and
46:15
you read you read you read six columns in The Wall Street Journal, right? And these are six columns are, are, are written by, by six experts in, in, in, in, in --Financial experts, right? And every day, you have to put your money, sort of, you know, you have to pick one of them, and make a small investment, right? I mean, so and then, in the evening news, you see what happened. I mean, that's the story. And then next day, the same. So let's see. So day one, you have to choose an expert, right?
46:52
I mean, so you look, you know, you read the columns, you say, "I, this, this --Today, I'm going to choose this guy." All right? And then in the evening news, you see what happens. I mean it's, you either win up to a dollar or you lose up to a dollar. Right? I mean it's, you know, if you need more money to pique your interest, you know, multiply by a, by a thousand, right? I mean, so okay? So you choose an expert, and he did terribly. All right? I mean, fine.
47:22
The next day you choose another expert.
47:26
And you see what happens. Okay? So, did something better. And so on. All right? And this goes on for 10 years. Every day, you do the same thing.
47:36
So here is our goal.
47:39
By the way, these --You know, it's not like, you know, these things don't come out of distribution. They, you know, this is a distributionless problem. Right? I mean, there's no prior here. Right? I mean, no, none at all. All these experts are very quirky, have a very quirky behavior. Okay? They can be good one day, bad one day, another day, okay? You know that one of these experts can make you rich, [AUDIENCE MEMBER] Okay? [CHRISTOS PAPADIMITRIOU] But you don't know which it is.
48:06
Maybe it's Mickey, even though he didn't well, do well the first day. Okay? But you know that one of these guys are going to make you rich. And the question is, you know, in fact, the outcomes, you can see them as adversarial. By adversarial, I mean, that there is a prankster who is creating the outcomes in such a way so that to prevent you from becoming rich. Okay?
48:30
To embarrass you sort of, you know, to make you make bad choices again and again. Right? And here's the question: Is there a learning strategy that gets you very close to the performance of the best expert after these sort of, you know 3,000 days, to 3,600 days. Okay? So that's the question. Is this -- mean have you internalized enough of it, so you know it's a weird problem. So you know, but in some sense, it turns out it's extremely representative of many situations that come up
49:08
in computer science, in game theory, in many, many, many places, okay? In AI. Okay? So you know. So, [AUDIENCE MEMBER] Can you say again what you mean by adversarial here? [CHRISTOS PAPADIMITRIOU] Adversarial means that it doesn't come from a prior, but you can even assume that somebody's studying the history and wants to screw you. You know, wants to really diminish your chances of doing well. Okay? And so maybe the one you choose sort of, you know, is going to be the worst. Okay?
49:42
You know, will try to do that.
49:45
Okay now-- He [AUDIENCE MEMBER] Cannot change the numbers. Can he [CHRISTOS PAPADIMITRIOU] Change-- Changes the numbers. [AUDIENCE MEMBER] But before he knows what you're gonna --which-- [CHRISTOS PAPADIMITRIOU] Sorry? [AUDIENCE MEMBER] But before he [CHRISTOS PAPADIMITRIOU] Knows-- Right, right, right. Yes yes yes right. I mean, oh, so-- so-- sorry, sorry. Yes right. I mean, changes, yes. Changes the numbers, you know, not after he --no, no. Nice. Yeah yeah. Okay? All right, does it make sense?
50:03
Yes. Yeah. After you know what --right, yeah. Okay good.
50:08
Is this clear?
50:11
Every morning can change your numbers. Okay?
50:16
[AUDIENCE MEMBER] Okay.
50:18
[CHRISTOS PAPADIMITRIOU] And the answer is that yes, such an algorithm exists. Okay? You know, that's a very surprising fact. And it's called Monte Carlo multiplicative weights algorithm. And you know, it's such a simple idea that has been discovered probably five or six times. Okay? It was discovered in the '50s in economics, okay, and was called, so you know, hand consistency. Okay? Then it was discovered in financial economic mathematics by so, you know, and then it was discovered
50:45
in AI under different names. You know, theoreticians were the last to discover it, and we're proud that we have not forgotten about it. Okay? You know, so, and so here is how it works. You start by giving all experts equal probabilities 1/6 to each one of them. And at each step, you update the probabilities by this formula, okay? In other words, you boost a little the experts that did better at the expense of the others, you know, and then you divide by a normalizing constant to keep
51:17
it to probabilities, okay? And that's all there is to it. Right? Nothing, nothing fancy. Just this, and I mean to be really accurate, what you mean, usually mean by multiplicative weights, these, instead of one plus epsilon to the outcome times outcome is E to the epsilon. But it's sort of, you know, if epsilon is small as it always is, you know, here it's going to be like 3%. This is the same. Okay? So in any event, and it turns out that this, uh --And the theorem is the following: That the
51:54
multiplicative weights algorithm is guaranteed to perform in expectation within log n over T of the best expert, okay? Who would have guessed, right? I mean by the way to the young people in the audience, okay, you know, this is c-- He's called Beavis, okay?
52:11
All right. So used to be famous. Okay? So, all right. So, um-- So l-- uh, square root of log n over T, okay? This means that in the example I gave you, you are going to be just three or four cents every day behind the best expert, okay? So you are going to get rich. Okay? That's what it means. Is this clear?
52:43
Okay.
52:45
And it turns out that this QPID algorithm, this very naive algorithm solves so many problems that it's not --it, you know, it shouldn't have aspired to solve, okay? You know, like convex programming, network congestion, many more, okay? So it is used in AI, sort of, you know it's called AdaBoost. Okay? So you know, so it's very accomplished algorithm, right? I mean, so that's this is one of the very interesting extremely simple algorithms that seem to permeate a lot of things. Okay. So you know.
53:26
Are there any questions? You know, I think, I think, I think I'll, I think I'll wrap up here. So any more questions? Any questions on multiplicative weights?
53:38
Okay. So there is --that's not my-- Yeah, from here. Sorry? [AUDIENCE MEMBER] Are there classes of NP besides NP-complete, which people [CHRISTOS PAPADIMITRIOU] Talk about? Oh yeah Yeah. Yeah. Yes yes yes yes. So, you know, yes. I'm glad you asked this question. Okay. So, you know, it's, you know I've spent 40 years of my life in that. Yes yeah Yeah yeah. [SHAI] Yeah, [CHRISTOS PAPADIMITRIOU] Yeah. Yes, there are. Sir. [AUDIENCE MEMBER] You know, you've talked about worst case
54:06
results for lots of problems, some of which probably map rather well onto problems that are of interest in neuroscience.
54:16
But the --that can be somewhat deceiving. I mean, not only your number partitioning problem, not only can it be approximated, but over most of the parameter space, it's actually easy. You can use-- Mm-hmm, mm-hmm. --solving that. [CHRISTOS PAPADIMITRIOU] Absolutely, yeah, yeah. In fact, [AUDIENCE MEMBER] It's sometimes a hard problem to find a hard instance. [CHRISTOS PAPADIMITRIOU] Right, right. Yeah. I agree. I agree with you. Okay. So right. Again I don't see NP-completeness as
54:42
pertaining to practice. [AUDIENCE MEMBER] Okay? [CHRISTOS PAPADIMITRIOU] I see it as pertaining to theory. Okay? So, you know, it's a, you know, intractability is a theoretical tool. Okay. So, you know, it helps us narrow to the right, to the right problem, to the right instances, to the right, okay? So, you know, say that, you know, understand why our problem is easy, because it has to be easy. [AUDIENCE MEMBER] Yes. [CHRISTOS PAPADIMITRIOU] Okay. And we know that, that's the point.
55:08
Yes precisely yeah.
55:11
Okay. Thanks. Excellent question. Bruno. [AUDIENCE MEMBER] I'm curious about the multiplicative weights update procedure. Was that arrived at heuristically And then it was proven after the fact that it was optimal, or did they somehow derive that from some, like, gradient [CHRISTOS PAPADIMITRIOU] So in the domain of game theory and economics, it was proved sort of, you know, the proof is clever, but not difficult. Uh-- And, and it was proved by hand sort of, you know, Well--
55:42
And then it was Tom Cover, sort of, you know, our, our colleague at Stanford, sort of, you know, who left early uh, did it, rediscovered it, so --in '80s. And then a bunch of AI folks discovered it, okay? You know, it was called WINO, it was called you know, and boosting, you know, and then it was implemented as AdaBoost. So, you know, and it's a winner. So, in each case, I believe that they had proofs. Okay? Mm-hmm. And now, we have really simple proofs. Okay?
56:16
So, you know, there is a, there is a very nice paper by Arora et al., sort of, you know, that that is sort of, you know, an archival way of looking, you know. And I mean, oh, and also my notes are not bad, okay? So, [AUDIENCE MEMBER] This is, it's striking and it's just, it just seems so intuitive that-- Exactly. --you might have just come at, come at it that way, and then, you know-- Yeah. --found that it works. [CHRISTOS PAPADIMITRIOU] Yeah, yeah. So finding out it works is-- If it
56:39
[AUDIENCE MEMBER] Happened that way, I mean, it actually sort of happened by somebody actually solving it. [CHRISTOS PAPADIMITRIOU] Absolutely, yes, yes. If you are an AI researcher sort of, thinking about an environment like this, a hostile sort of-- Mm-hmm. Environment which is unknowable in terms of prior you have to come up with this, okay? You know, and they have come up many times with this. You know Tom Cover was working on the finan-- financial markets, so, you know, on, you know,
57:06
portfolio building. I mean, and that's how you build your portfolio. I mean, that's-- [AUDIENCE MEMBER] Mm-hmm. Yeah, once at Michigan, the guy w-- got the MacArthur Prize for a schema on explaining what, how the genome can com-- uh, DNA are competing against, against each other using an algorithm very much like this. [CHRISTOS PAPADIMITRIOU] Really? [AUDIENCE MEMBER] Yeah. Okay. I'm just blocking on the name, but I can find him. [CHRISTOS PAPADIMITRIOU] Um, I'm going, I'm going, I'm going,
57:36
I'm going to talk about that, actually. [AUDIENCE MEMBER] Okay. [CHRISTOS PAPADIMITRIOU] Yeah, so, right. So, you know stick around, you know, in about three-quarters yeah. [SHAI] Absolutely. [CHRISTOS PAPADIMITRIOU] Oh, [SHAI] Yeah. Go ahead. Yes yes sure. My comments, right. Because I, I, I really feel that, I mean, this-- What, like you were saying, the worst case, that's what we can do in theory. But we realize more and more that in some sense, in theory, it's irrelevant to life.
58:01
And now, when we have deep learning, it's very clear that we need a new theory to be able to handle realistic problems, and not just theoretical constructs. And in some sense, I think this is the big challenge. Not solving P versus NP, but coming up with a complexity theory that reflects reality better than worst case. [CHRISTOS PAPADIMITRIOU] Yeah. I beg to differ.
58:31
I think that practice is tremendously important. And because of that you need theory, and you need to resolve the P versus NP problem.
58:42
[AUDIENCE MEMBER] But there are also theoretical attempts to deal with average case complexity by many definitions. [CHRISTOS PAPADIMITRIOU] Absolutely. You're absolutely right, yes. I mean, no-- And, and, and what I'm saying is that, is that NP-completeness-- Okay. Listen, I mean, the caricature-- Uh, I'm not saying that Shai is using-- is, is, is, is he wielding it? Sorry, you know, but the caricature of the theoretician as somebody sort of, you know,
59:03
who pranks you and says, "Ha ha, your problem is NP-complete," or, you know, is completely wrong. I mean, we use NP-completeness as a-- You know, we use the theory as a tool, as a theoretical tool for sorting out problems, sorting out instances, discovering these instances, discovering why for example, okay, so, you know, why protein folding is easy. Okay? You know, why you know, problems of, you know-- well, pattern matching is easy. Okay?
59:35
So, you know, we-- And, and, and and without having uh, so, you know, an incisive theory for carving out things that cannot work, okay, sort of, you know, you, you, you, you, you, you don't make progress.
59:52
[AUDIENCE MEMBER] Yes, but the criterion of worst case performance is not necessarily useful in-- Absolutely. [CHRISTOS PAPADIMITRIOU] Absolutely. In other problems. Absolutely. Totally agree. Yeah. Yes. So, you know, so, I'll, I'll probably-- Yes, so, you know-- So, you will see many, many examples of precise-- uh uh, the kind that you, that you have in mind, sort of, you know, in the second half.
1:00:21
Any more questions?
1:00:26
(applause)
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat