Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson

30:34The Peterman Pod Host:You mentioned time complexity and space complexity. And I think intuitively, like in software engineering, we often trade those off for each other. Is there a general theory on that, on how these two trade off? Yeah, yeah. We have, yeah, all these questions are natural questions for complexity theorists. How does two resources relate to each other and whether they can trade off or maybe you can minimize them both at the same time? and it depends on the problem. There are problems for which we know results like multiply time and space. It has to be at least the square of the length of the input.

31:23So you can either do it with very small space like logarithmic space but you need to pay maybe quadratic time. and if you want linear time, you have to pay linear space or close to linear space. There are results of this type in various models of computation. That's another thing you play with. Not all of them are, you know, they are all equivalent in principle, but if you care about exact time or exact space, they are not equivalent. So there are problems for which there is a trade-off. there are problems where you can solve them in linear time and logarithmic space. One very important general result that is the breakthrough from last year is the result of Ryan Williams.

32:13And I'll tell you what it is, but I'll first describe what we knew about time and space. There's a clear inequality, right? If you run in time t, you will never use more than space t because you never visit so many cells or registers in your machine. So space is at most time. Fifty years ago, Dvalian, Paul, and Pipinger improved this a little bit. They said that if you run in time t, there's an equivalent computation that will do this in slightly less space than t, t over log t. That was a big result. The running time, of course, will blow up. It will be very, very expensive time-wise, but at least you can save on space a little bit.

33:02And this was believed almost 50 years to be the best you can do. In fact, we had arguments that in certain models, in certain stylized models of computation, you cannot improve that. I will not describe, you know, this restricted model. but in some way with natural assisted models, you cannot beat this. And what Ryan Williams found out last year is that in fact much better can be done. Any computation that runs in time t can be simulated by another algorithm that uses only square root of t space. Far, far less than, you know, before. and the algorithm is quite sophisticated and used as an earlier result of James Cook, the son of Steve Cook of NP Completeness and Ian Mertz.

34:04That was an essential technical ingredient. But anyway, there's a really interesting way to save space, very, very non-trivial way to save space. Again, this algorithm will run in a lot of time, but at least you have a sense that, yeah, the two parameters are related in a highly non-trivial way.

34:29The Peterman Pod Host:Is this for a general problem? General problem. For Turing machines. Okay. It may not work on random access machines or, yeah. What's the trick? If you could explain intuitively, or is it too deep to explain? It is, you know, really technically explaining it is too deep. But let me give you a much earlier result, which sort of indicates that really mysterious things can be done in small space. Again, it's probably over 40 years ago. People discovered the following. Dave Barrington discovered the following really interesting phenomena. So suppose all you want is to count. I give you a sequence of bits and bits, and you want to count.

35:20Say you want to know whether there are more zeros than ones, like the majority problem. Who wants the vote? Zero or the one? Okay. Well, you can count. You can just add them up, and this takes logarithmic space. And it seems that the best you can do. I mean, we want to count up to n to represent n takes log n bits, right? I mean, whatever n or the sum, any number between one n, it takes log n bits. It seems essential. It turns out that there's an algorithm. I have to define exactly how it works. I will not define that. I will not define exactly how it works. But it solves this problem in constant space.

36:08It seems like you can count arbitrarily high. I mean, all you need is access to whatever bit you like, whenever you like. I want the 17th one. I want the 81st one. If you can have random access to the bits, even if you have constant space, you can tell whether there are more zeros than ones or ones than zeros, regardless how long the input is. The trick is that somehow you use non-commutative algebra. You use something, you know, non-commutative algebra is not there, because everybody's familiar with non-commutative things. I mean, we usually put the cart behind the horse and not in front of the horse.

36:51It matters. Or in software engineering, we do this before that. It's very important. The order of things matter. So you can think about applying permutations one after the other. If I rotate a circle and then take a mirror image, it will give me the... So these are two permutations, right? I mean, say I have endpoints in a circle. I can shift it by one, or I can, you know, let's say flip it around some diameter. There are two permutations, and they don't commute. I mean, if I first flip and then rotate, I'll get something else. If I first rotate it and think of all the points I've colored by. So they don't commute.

37:44But Barrington is using, you know, he's somehow encoding the bits in the input by permutations. Not large permutations, permutations of size 5. And somehow when he sees a 1, he maybe rotates, and when he sees a 0, he flips. And the non-communativity of these operations allows him to carry out a general formula, a formula of N's and O's and N's. Any formula like this, a formula of some size S, it allows him to carry out this computation to really simulate the ends and all the knots in this formula by rotations and flips of this five-sided pentagon. Okay? And so just to remember the configuration of this pentagon, you need, I don't know, five bits.

38:53All right, so you need constant space. How this captures the computation I can tell you one more sentence, maybe it will not be clear to everybody, but these non-commuting things, you can do the following type of operation. Do rotate, do flip, then rotate back and flip back. This is called the commutator, and it can simulate an end gate.

39:36It's too much to describe in words without a board, how it does it. But there's a very famous analogy, which is a riddle, which if nobody... I mean, it's a good riddle to think about, which really captures this end gate problem. You want to hang a painting in the following way. You have a painting. It has a string connecting the two sides, but you want to hang it not on one nail but on two nails. Okay, there are two nails on the wall, and you can do with the string whatever you want. And the purpose you want is that if the two nails are there, It's hanging. Everybody's happy. If you pull out one nail, it doesn't matter which, the picture falls to the floor.

40:32How would you loop the string around these nails so that this happens? Clearly, this is an end gate or an O gate, right? And this has to do, I mean, if anybody finds a solution, they'll realize what non-commutativity I'm talking about. And yeah, it's a nice fiddle. Anyway, so this type of trick where you can really, this type of result, you can really do in small space things you wouldn't imagine possible. It's a striking example. It's really, when I had this result, first time I was a poster, and somebody told me, and I just didn't believe it's possible. I mean, you cannot count arbitrarily high with the, yeah.

41:22So, yeah, so the trick that Cook and Merz have in their algorithm is a solution to a natural problem in much less space than you would think. And it uses some sense tricks of this nature.

41:43The Peterman Pod Host:So if you're counting arbitrarily large, that is information. And you're saying, like, maybe the intuition is that information's encoded in the sequence of operations. It is encoded, yeah. Of course, you are not delivering the final count. You just say whether there are more zeros than ones. If you have to write down, of course, you need, if the answer takes some number of bits long, then you need this number to write it down. If you have a decision problem, say, like, yes or no, like, are there more zeros than ones, then you can do it for any size input in a console space. That's incredible. It's pretty incredible, yeah.

42:30And by the way, this is highly applicable. It's used in cryptography in fundamental ways. it's used for in various places and it's an extremely useful result here by the way unlike the Ryan Williams result if you have a formula of size S you can do it in constant space and the time of this algorithm does not blow up really a lot it's just quadratic so it's quadratic time so this is something actually doable, useful efficient and And yeah, in sort of medica.

43:06The Peterman Pod Host:We talked about the equivalence between these MP-complete problems. And then I know in practice, a lot of people to solve the other problems, they just use SAT solvers. Yeah. I would have thought that would be less efficient, though, because you got to kind of translate it. And then you're doing it in almost like a different problem space. Yeah. You usually also enlarge the instance. Usually in translation, you enlarge the instance. So what your question is, why do people use cell solvers? I would say that there's no problem other than satisfiability that people thought so hard about really optimizing the heuristics that efficiently work on many instances.

43:56There are very, very clever ways in which you can, you know, try, start. I mean, you are not going to guess all the end bits. But you want to start by guessing some bits that seem more pivotal, that if you, like in dominoes, maybe when you set them to one value, they force many other values to be set. And if that happens, you cut down your search space. So there are many heuristics of this type, and also more clever than this, that allow to solve such liability problems if they have such structure. Again, the worst case, it will not help you. There is, in fact, a conjecture. It's much stronger somehow than NP-completeness, NP-completeness problems taking exponential time.

44:51It says that we don't expect any savings. We expect satisfiability problems to require really true to some constant times N. It's not going to be true to the scrot or N to the log N or something like this. This is really, yeah. So, yeah. But the worst case may be hard, but people optimize attacks on many, many such formulas that somehow have all sorts of structural properties arising maybe in practice. And I think that's the main reason that they are used. It's also convenient. I mean, it's very, you know, people do it for testing specifications that programs, protocols, meet specification, they're usually, these specifications are usually easily translated into simple constraints, and that's almost a susceptibility problem.

45:53The Peterman Pod Host:We talked about all the different types of resources in an algorithm, and in one of your talks you said something where you consider randomness another resource for an algorithm. What do you mean when you say randomness is a resource for an algorithm? In the early 70s, of course, randomized algorithms existed since antiquity, and everybody was tossing coins for lots of reasons. And, of course, statisticians, you know, do sampling and use randomness for... But when algorithmics, you know, designing efficient algorithms became big once we had computers, people realized that it can really enhance all sorts of computation.

46:41For example, we had no idea how to test primality of a number. And in the 70s, both Michael Rabin and Solvig and Strassen found probabilistic algorithms which are fast to test primality. Okay, so what does it mean by probabilistic algorithm? It's an algorithm that's allowed to make random choices. So you can see that there's an internal little person or device inside that tosses coins. Of course, that's not what happens. There's no little person sitting in your laptop. So the question is, where do you get these random bits? But it's very important to stress that in all these probabilistic algorithms, the underlying assumption is that the bits you get are perfect.

47:29They are half-half, each one, and independent of each other. It's like a uniform distribution on all possibilities. Now, where do you get this? I mean, where seriously do you get this? I mean, if you run a probabilistic algorithm of your laptop, since it doesn't have this person inside the tossing coins, it does something. Well, high-quality randomness of this type costs money. like time and like memory. What do I mean by cost money? You can have a very cheap solution. You can just, I don't know, measure the thermal noise in your computer or have one of the Intel chips. You know, you can measure internet traffic and sample it and believe it's random.

48:18And all of these things are used. You can do something mathematical, have some simple procedure that is actually deterministic, like a linear congruence generator, something like this, and believe it's random. Or you can take the digits of pi. It also looks random in some sense. So there are many things you can use, but you don't know they're random. If you want them to be random, one source, even this is not a perfect source, but we have quantum mechanics. People believe it works in life, it seems like. a cool theory of nature. There are all sorts of arguments about it, but let's put them aside.

49:02They predict that if you measure photons coming out from some source and you measure their spin, whether it's up or down, the prediction is that each one is half-half and it's independent of each other. That's very nice, but if you are going to build this device, it's going to cost you a lot of money. and let alone that it will not be perfect, but let's leave this aside. Anyway, since you want high-quality randomness, you have some way of guaranteeing. I mean, you're running it really on your laptop. It's not, you know, okay, the paper was written. We can test primality with a public algorithm.

49:40Now we want to run it. What do you use? So it makes sense to ask lots of questions about randomness, what to guarantee the quality of the randomness, and maybe you can minimize there is the use of randomness. By the way, another issue with randomness is that, you know, the outcome is a random variable and it's not always correct, right? The whole point in most of these algorithms, you just have some small probability of error. If you have a deterministic algorithm, there's no error. So you also don't like the error. So treating it as a resource is simply a convenient, complexity theoretic way of saying, how do we understand, you know, the amount of this resource we have to invest or the number of bits we have to invest, their quality and so on.

50:29So it's, yeah, it's almost automatic if you think like a complexity theorist. How do we minimize for particular algorithm like primarity testing? You know, do you really need this? Do you need them to be independent? Maybe you can generate them in a, you know, maybe you need n-bits, but you can start from scrolled n-bits or from log n-bits that are truly random and make from them in some deterministic way, you know, a sort of pseudo-random sequence, you can call it, which is a good name, actually, that will, for this purpose of this algorithm, will look as if it was random. if you could do that you don't need all this but you can use much fewer and this whole theory of reducing randomness derandomization, removing randomness is a huge feat and people are there are many problems and many ways of doing it and the story with primality is actually fascinating so I mentioned these two algorithms that were invented, and people were wondering about the deterministic algorithm for primality.

51:45It's a problem that has been articulated already by Gauss in the most, you know, complexly theoretic way you can, you know, back in his days, hundreds of years ago, and maybe 150, I don't know. He was asking for an indefatigable calculator. calculator, of course, is a person, but he wanted this to be efficient. That's basically what he was looking for, a primality test for large numbers, because they really wanted to know about numbers, maybe only a few tens of digits they wanted to know whether they were prime or not. There was no efficient algorithm. Anyway, you can wonder about the Solveig-Strauss and O 'Reibin algorithm.

52:33them, maybe you can use less randomness or structural randomness that you can generate from fewer bits. And nobody has any good idea. And then in the early 2000s, Agarwal, Kayan, and Saxena devised a different probabilistic primality test. And it's different, so the analysis of randomness in it is different. And once you understand how randomness is used, you can maybe say, ah, we don't need to be really totally independent bits. It's okay if it has some structure. And then they found using number theoretic ways a method to generate this pseudorandomly, generated from very few bits. And that's how the, so often, I don't know often, but sometimes deterministic versions of probabilistic algorithms are discovered in simply understanding the way in which the algorithm is using the randomness, understanding the analysis of the algorithm.

53:42And saying, okay, it doesn't use all that much.

53:48The Peterman Pod Host:You mentioned a few times the quality of the randomness. Yeah. How do you quantify the quality of random bits? This is basically a question about what pseudorandomness is. And the general answer is that it depends. You want to fool a particular algorithm, let's say for primality. So you want the randomness to fool this. So you want this algorithm not to notice that you switched from perfect randomness to something that's really far less random, has far less entropy. But the analysis works nonetheless. Another algorithm, maybe you need a completely different type of pseudorandomness for it. There is a set of examples of algorithmic problems for which when you look at the analysis, they are much simpler than this primality testing.

54:45When you look at the analysis, it seems to use not the independence of all the n-bits. You really need only every pair of them to be independent or every triple. And spaces of random variables which have this property are much smaller. You can generate them from log N bits. And so you can fool them with this. So the quality of randomness, there's a phrase I like that it's, the quality of randomness is in the eye of the beholder or in the computational power of the beholder. You really need it to be just as good as the tests that are applied to it. You just want to be completely pragmatic. You don't care whether it's random or not.

55:32You just care that an observer of a particular structure or particular computational power will not distinguish the pseudorandom distribution, which may have much less randomness in it, than the perfect one.

55:48The Peterman Pod Host:In one of your lectures, actually, you mentioned that and you gave a good example. I was wondering if you could give the intuitive example of why randomness is a function of the observer's computational power. Yeah, so if you watch this talk, you know what the example I give is the example that's taken from this fundamental paper of Manuel Blum and Silvio Micali. They tell you to consider three experiments. And the experiments go as follows. They're always between you and me. You are the observer. I am the coin tosser. I have a coin on my finger and I toss it and just as it leaves my finger, you are supposed to predict what the value will be when it falls on the floor, like in two seconds.

56:38You have to immediately say heads or tails, okay? Before, you have to predict before it falls. Well, this is the first experiment and, you know, what I ask and what they ask, you know, what do you think is a success, your success? What are your chances of predicting it? And the obvious answer is, you know, one half. You know, how can it help? You know, what can you do? The second is when you sit there, but you have a laptop like you have now. And, yeah, what can you... Yeah, I don't know how fast you type, but the coin will be on the floor in a second. The third experiment is where your laptop is connected to a Kray supercomputer, and the Kray supercomputer is connected to a bunch of sensors and cameras and whatever devices you want.

57:33They are all trained on my finger. Okay? And so as it leaves my finger, the coin, this apparatus certainly is more than enough to calculate all the angular momentum of the coin and the distance to the floor and the humidity in the air and whatever parameters that completely determine its motion, in particular how it will land in a split second, far less than the time needed to. So the real point in this example is that the experiment, the random cointos, this cointos, did not change in all of them. It is the same. What, you know. And masses of people in math and physics and philosophy and, you know, defined randomness in various ways.

58:28There are many definitions of randomness. And they all focus on this event, on the chronitosis or sequence of chronitosis. We in complexity theory, starting from this paper, don't care about this event. I mean, the event stays the same in all. It focuses on the observer, and the only thing that changed in these three experiments is the computational power. So we want to know how much entropy is in the coin. If you don't have enough computational power, it seems to be full entropy. It's half-half, right? You don't know what it will be. If you have enough computational power, you can predict it completely, and then it's a zero entropy.

59:12So what changed is the observer. So the observer is this algorithm we talked about before, and any test that's applied to a distribution to test the quality of randomness, depending on the test, you want to just make sure you want to use this little true randomness in a way that the observer will not notice. And this is a source of many of the important theorems that show that you can remove randomness or reduce randomness in probabilistic algorithms with or without assumptions and really are behind this understanding that we have today. Randomness in algorithms is not as powerful as we thought it is.

1:00:04Like if you know that something like P is different than NP, or you have a hardware, traveling salesman is exponentially hard or survivability. If you know that, then in fact, I can give you a pseudorandom generator that will derandomize any probabilistic algorithms. We know that under this assumption, we have what we call P equals BPP. Anything that has an efficient probabilistic algorithm also has an efficient deterministic algorithm. You just need to know that there is a hard function somewhere. Under what assumptions do we know P equals BPP? The assumption is very natural. is that one of these NPR problems, or in fact, even problems in higher classes, requires a lot of hardware, requires exponential size circuits to solve.

1:01:03Okay, we believe that. It's like P versus NP strength, and you cannot cut down the exponential search space.

1:01:15and so maybe people are you know happier with this assumption but this assumption about time complexity it has no randomness in it it's sort of at first it's shocking that it's actually related to the problem of removing randomness from algorithms so that's one fundamental connection, this hardness versus randomness paradigm. But we know even more. We know that it goes both ways. We know that if you are trying to remove randomness from some algorithms, if you can do that, then you found the hard function. So there's really an almost, it's not an exact if and only if, but again, and there are many variants of this, and some variants is if and only if it's stronger.

1:02:15But we really know that it's really one or the other. And since it's hard to believe that all these hard problems are easy, or the seemingly hard problems like p equals NP, we tend much more to believe the other alternative, namely that randomness in algorithms is weak and you can remove it.

1:02:33The Peterman Pod Host:OpenAI, Anthropic, Cursor, and Vercel all use this product to make their lives better. And the problem it solves is when you're building SaaS or an AI product and you want to sell to other companies, there's all these requirements you need to meet. There's SSO, there's SCIM, there's RBAC, there's audit logs. These are all things that take time to integrate, but aren't the main focus of your app. WorkOS is an API layer that lets you meet all of these requirements in just a few lines of code. So let's say you have a new SaaS product and you want to sell to other companies. WorkOS will solve all of these critical feature gaps for you.

1:03:10The Peterman Pod Host:You can check them out at workos.com to learn more and get started. And I appreciate them for supporting my work and sponsoring this podcast. Is there an intuitive explanation for the relationship between problem hardness and randomness? Yeah. Yeah, there's almost always an intuitive explanation for it. Yeah, so what's a hard problem? I give you the input. You are a limited computer. You are a polynomial time algorithm. I give you the input. Let's say it's a traveling segment problem. You don't know the answer. So there's some entropy in the answer, right? It's in the same sense we discussed before.

1:03:53There's some entropy, a tiny entropy, maybe exponentially small entropy because maybe the input is random. Maybe only few instances are hard and all the others you can solve. But at least you see a hint of a relationship between hardness and entropy. This, of course, is not satisfactory because we want that for you the answer will be like a coin toss, not like a very biased coin toss. So we need to find ways to amplify this uncertainty for you, amplify the hardness. We want not just that some instances will be hard, but that the random instance, whether the answer is yes or no for a polynomial time observer will be half-half.

1:04:46You will not be able to gain an epsilon advantage over a random guess. So for this, we developed all sorts of methods that amplify randomness. Now, this doesn't solve the problem at all, because I managed to take n-bits, a random instance of a problem, and manufacture one bit. That's hard for you to guess. but I could have taken the first random bit I picked for there. So I generate for many a few, one. What you want to do is the opposite. You want a method that will take a few and will generate many. That's a pseudo-random generator. So the random generator starts for a few, truly random bits and generates many.

1:05:35And for this we need other tools. is something that I developed with non-Nissan, called today the NW generator. I like to say that, you know, people say that making the first million dollars is easy and afterwards you can make many more millions. You can think of it this way. The hardness, in the way I describe it, allows you to make one million dollars. But once you can make one, there are methods to make many more. And in fact, more than the number of bits you started with. But still, their quality depends on the hardness of the function you use. We still use this. And your limitation of being running polynomial time.

1:06:27So you cannot solve this hard instance. You build many, many instances from a short seed. You start from maybe a logarithmically long seed. You take many subsets of this, like N. You need N of them. And I ask you for the value of the solution to each one. Each one is hard, but you want to say that they are simultaneously hard. You cannot tell them apart. There is no correlation you can detect between them, even though they are extremely correlated. So, yeah, so we have methods to do that as well. So that's the connection. Having a hard problem to a limited observer means there's some uncertainty about the answer.

1:07:12That's the key. That's the starting point.

1:07:14The Peterman Pod Host:So when you say that the quality of the randomness is a function of the computational power of the observer, one thought that comes to mind is, imagine I have maybe infinite compute. Then nothing is truly random. Is that accurate to say? Like, you know, if I had infinite compute, the weather is not random. Nothing is random. Okay. So it points to the fact that you have to really be careful about what question you are asking about the randomness. If you want to apply this to probabilistic algorithms, then it's really important that you are limitless computationally. So if you have infinite compute times, you will be able to distinguish a distribution with full entropy, and one with coming from a generator, one with low entropy.

1:08:19So you could do that. But one thing you cannot do with infinite compute is something that's information theoretic. So there are many other things we need to do with random bits than just run probabilistic algorithms. For example, we want to generate passwords for our security systems. The very demand is that they are random, right? I mean, Shannon's theorem tells you, you know, the quality of your pastures is as good as the entropy in it. So the notion of a secret rests on the randomness, the true randomness of the... So if I just ask you to produce a random bit, or you ask me to produce a random bit, you Whether you have infinite computational power or not, it doesn't matter.

1:09:20I mean, to generate this random bit, it has to be random. I mean, your demand is not that it will succeed in some test. You really want the probability of heads to be half, tails to be half. Then this definition or this task of producing randomness is not related to your computational power. And so, you know, lucky or unlucky, I don't know, for us, many times we do have implicit or explicit tests for this randomness. You say, I can break this, you know, I can break this system or something, and then you can maybe use pseudo-randomness. But if your very demand is to have a random event, then you need to produce a random event.

1:10:07The Peterman Pod Host:I saw when I was doing my research that there are ways to create higher quality randomness by aggregating weaker sources. Yeah. How does that work? Well, it's another theory. I talked before about the theory of pseudorandomness. There's a whole different theory. They are related in non-trivial ways, but it's called the theory of randomness extraction. or randomness purification, maybe. And this is exactly what you asked about. We imagine that the world maybe does not give us perfect randomness, but we have all these events we cannot predict, like the weather or various quantum phenomena or sunspots, or we cannot predict the, you know, stock prices, right?

1:11:01Otherwise the market will be... But these are not, you know, even though these are unpredictable events, they are somewhat predictable. I mean, the weather tomorrow is more likely to be similar to the weather today than the opposite of the world. So there are correlations. If you sample this weather, for example, there are also biases. I mean, sometimes, you know, in the spring it's more, or in the summer it's more likely to be hot than cold. so there are biases correlations these are called weak random sources and there's a mathematical quantification of how weak they are basically talk about the amount of entropy in them you have n bits potentially you can have entropy n but maybe they were generated from a generator or they came from some source so it has some entropy in it but you have no idea where.

1:12:02I mean, maybe half of them are fixed and half of them are coin tosses, and you don't know which half. Maybe they are each, you know, half, you know, three quarters, zero, and one quarter, you know, heads or tails have a bias. That also has lots of entropy, but not full. And maybe the correlations are even more complicated. So you can imagine all sorts of situations like this, and you mathematically model it by saying, okay, there are n bits, it's a probability distribution of n bits which has some entropy, let's say square root of n. You don't know where. And you want to use it in a probabilistic algorithm.

1:12:45So it's a basic question. Can we use physical events, weak sources coming from nature maybe, in probabilistic algorithms? And it's certainly not obvious. I mean, just feeding them to the algorithm as is, is not going to work. They are very easy to find simple algorithms that will fail, that will succeed on perfect randomness and will fail on, will always make an error lately. But the theory of randomness purification wants to take this sample of n bits with some amount of entropy which is not full. And someone massage it, create from it maybe a shorter string, which is of higher quality. Ideally, it would be perfect random bits.

1:13:42So ideally, you can imagine that if I have n random bits and I have entropy root n, maybe I can massage out of there square root n or maybe just the fourth root of n bits that will be essentially uniformly distributed. Then if I have an algorithm that just needs this amount, that's what I feel it. It turns out that you cannot do that. It's impossible. But what you can do is not produce one string of length, let's say, square root n, but you can produce n to the hundred of them. Okay? And what you are guaranteed, So this is this randomness purification device. It's an efficient algorithm that takes any distribution with entropy in it, and you produce many blocks, polynomially many blocks, of the length roughly the entropy, what you would hope to be perfect.

1:14:43And what you are guaranteed is that 99 % of them are truly perfect. So you have many. 99 % of them are as good as perfect. And there's 1 % which is bad. You don't know which it is. But that already solves your problem. Because run your algorithm on each one of them. Take a majority vote. Doing this is extremely complicated. There are many ways of doing it. There are variants of various assumptions you can make about the entropy. Maybe you have several weak sources that are not related to each other. There are various variants, and this theory is very well developed. But we know that the statement I made essentially is accurate.

1:15:40If you have one source with some entropy in it, you can generate polynomially many samples of the length of almost the entropy, and most of them will be perfect.

1:15:52The Peterman Pod Host:So that's as useful as having one, yeah. I vaguely remember skimming a bunch of papers and one of the papers had this figure where it was a two-dimensional array of numbers and I think they were drawing rectangles or something like that. Is that one of the ideas? So it's a notion of pseudorandomness which is related to one particular variant of this extraction problem where you have several weak sources, not one. One is the hardest because that's, yeah. But maybe you have a few that are independent and each of them has some entropy in it. And I think what you are referring to is this some products here and this, yeah, I cannot draw the pictures of that, but you don't really need to.

1:16:45So let's just think about this problem. you have three sources of randomness. They are each weak, so each has just a little bit of entropy in it. And all you want to produce is one source with somewhat larger entropy. So you are losing the number of sources, but you are gaining entropy. If you can repeat this, you eventually get to full entropy. So that's the idea. So what combination of weak sources would you take? It's not obvious. And the solution, yeah, this is, certainly there is, maybe you mean this one, there's a paper I have with Barak and Impagliato about this particular problem, and we are using a result in what's called the arithmetic combinatorics, and I can explain it very simply.

1:17:39I think that we learn about addition in second grade and about multiplication, third grade maybe. And, you know, the only motivation for multiplication is that it's a way to shortcut repeated addition. And that's what we talk about. Then if you go to college, you learn that, you know, sum and products are the basic operations of fields. You can do it with integers, you can do it with rational numbers, complex numbers, finite fields, and So you remember, these are the basic, but how do they relate to each other? It's not clear. Maybe there are many ways to ask this question. But one way to ask this question that was suggested by Erdős and was solved the first time by Erdős and Semeradi, and then in a much more, in a form we really need by Bougen, Katz, and Tao, say the following.

1:18:38Just think of a set of integers and add all pairs. So you start with, let's say, k integers. Add all pairs. How many new integers do you get? This you should think of as entropy increase. If you get many more, somehow. So you have k integers. Well, it depends what they are. I mean, if they are the first k integers and you add all pairs up, you get the number between 1 and 2k. That's not much larger. That's a factor too larger. If you want to increase an entropy, you want to get some power of k bigger than 1. Of course, if you take a random set of integers, you'll get k squared. They will all be distinct.

1:19:26You get k squared integers. So somehow you want to say, I mean, it would be great if for any set, when you take all pairs, you group. But it's not true. by this example of the interval? Well, you can not take sums. You can take products. Okay, but also products don't always increase. If you take, you know, 1, 2, 4, 8, you take a geometric progression, you multiply all pairs, you just get just twice as many as you start from. So that's also not good. And the magic in the sum-product theorem is that sums and products are orthogonal to each other. Somehow, if one of them fails to grow a set, then the other will grow this set.

1:20:20And so this is an amazing result. And the way you use it in this context, you think of the outcome of your sources as numbers. You, let's say, multiply the first pair and add them to the third. You mix the summary product. So this guarantees, even this is not obvious, but if you do this, it guarantees that you grow. The number of different values you get is significantly more than K. Maybe it's K to the 1.5 or something. Entropy does increase, and that's the source of... You need to prove it distributionally. It's not just the size. The entropy is not just size. along the side. It's more than that.

1:21:08But anyway, this is behind one solution to one of the problems about purification. It does not solve the one source problem. This, you need other tools.

1:21:20The Peterman Pod Host:I saw that you had done some work in zero-knowledge proofs. I was wondering if you could explain, you know, what is a zero-knowledge proof? Maybe we talk about its significance. Sure, yeah. Zero-knowledge proof, it's pretty amazing that became a household world. I mean, it was in the domain of theorists for a long time. The original definition of zero-knowledge proof came in a paper, a seminar paper of Goldwasser, Mikali, and Rakoff, which also contained the definition of interactive proof. So even before zero-knowledge, they conceived of the notion that proofs don't have to be written down like in mathematical papers.

1:22:06People can have a discussion, a randomized discussion, in which I try to convince you of something. I want to prove to you something, like I know the proof of the Riemann hypothesis, or I can solve this Sudoku puzzle. We can do it interactively. We are randomized, in particular you, the verifier of my claim. are allowed to be randomized. So it's like in randomized algorithms, but now the prover, there's a prover. It's not just an algorithm. It's a prover like in NP, someone who knows the solution. But the convincing has this interactive form. So this model was suggested in this paper and also in a paper of Babay, parallel in the same time from different motivations.

1:22:57basically it offers a generalization of the notion of NP. NP is just when I send you a message and it convinces you, you verify it and it convinces you. Now we allow an interaction and we allow a small chance because you are randomized, we allow a small chance that I will convince you of a false claim. But this error can be reduced, like in probabilistic algorithms, can be reduced arbitrarily. You want one in a billion, you can get one in a billion, whatever. Anyway, so there's the notion of an interactive proof. And then in the Goldwasser-Micali-Rakoff paper, they suggested another notion of interactive proof, which is more restricted.

1:23:46You want to prove something, but the zero knowledge means that you want the verifier to learn nothing, absolutely nothing about the proof except that it's true. Now this sounds really totally ridiculous. I mean, if you think about the last time you convinced somebody to change their mind about anything without providing them any knowledge, any new things they didn't know, say, what are you talking about? such proofs don't exist for anything. There's no zero knowledge for anything. They were not thinking about convincing someone of political opinion. They were thinking about cryptography, of course.

1:24:34They've created the foundation of cryptography in many other papers. But they are imagining cryptographic protocols in which you have secrets, and you use these secrets in your computation, and you have, you know, the protocol tells you to do things that if you don't, then, you know, you're violating the protocol, so the others don't want you to cheat. They want to make sure you perform the right operations on your secrets. For example, you are supposed to pick a public key by multiplying two prime numbers. If you multiply three or something else, then you are violating the protocol and maybe security is not guaranteed.

1:25:25So I would like to convince you that the number I give you is actually a product of two primes. I certainly don't want to give you the two primes. So what I really want to convince you of is that I computed this number by multiplying two primes. and you learn from this interaction absolutely nothing except you are convinced with very high probability that I did multiply two primes and not any other number and I didn't do anything else that I shouldn't have. And you can think about lots of other cryptographic protocols where people are doing things like multi-party computation, very complex things.

1:26:06They are computing with their secrets and they don't want to reveal them whereas the others want to make sure that they did what they should. So there are any number of applications to this idea. The only problem is it sounds ridiculous because it sounds impossible. In mathematics terms, if somebody came here and said that P, they proved P different than NP, I would want to see the proof and then tell me, okay, I'll prove it to you in zero. How can anybody convince me that they have a proof of P different than NP? And I come out, you know, congratulating them and, you know, amazed by them. And nevertheless, I know absolutely nothing about the way they proved it.

1:26:57I just know that they did. This story really sounds ridiculous. and yeah certainly one of my favorite papers, maybe my favorite is the zero knowledge paper which came a year later, this joint with Odell Goldreich and Silvio Micali, where we showed that it's not only not ridiculous it's universal namely, anything which has a proof, a mathematical proof also has a zero knowledge interactive proof, anything like p different than mp or that I multiply two points or anything that you can prove revealing your secret, you can prove without revealing your secret and convince beyond any reasonable doubt.

1:27:45So that's possible.

1:27:46The Peterman Pod Host:What's the intuition behind that? Like, let's say I have a proof for p equals mp and we want to convert it to a zero-knowledge proof. How does that work? How does this work? First of all, it assumes cryptography. So we assume we have some one-way functions. We assume that some problem like factor integers or this logarithm or any number of one-way believed one-way functions exists. So one-way functions, if people don't know, are functions that are easy to compute in one way but are hard to invert. For example, multiplying numbers is easy. Finally, the factors of a number, which is the inverse problem.

1:28:28the prime factor, is believed to be hard. Of course, we never, we can never, we don't know any hard problem. That's a P versus NP question. We don't know. But we believe about many problems, and the belief is actually the whole world believe, because the whole world is using cryptographic systems which rest on this, all electronic commerce assumes this. So we assume this. So assume we have one-way functions. When we functions allow you to create basically garbled message commitments, I can, you know, I have a number in my head. I don't want to tell you what the number is. The number is between 1 and 100.

1:29:16I can write down another number, which looks like a random number to you. and on the one hand, you have no idea. I claim this and call it my secret. And this commitment scheme, which is built very simply for moronary functions, guarantees two properties. A, you cannot tell what is my secret, even though you can see this number, this other number I gave you. And on the other hand, I cannot change my mind about my secret. It really commits me to that. So I can later provide you with a certificate that I was thinking about 17. And I can only do it for 17. I cannot do it for any other number. Okay?

1:30:09In fact, a very simple example is really using factoring. In some sense, the product of two primes, this number, you know, it's easy. this number commits to its factors it uniquely defines its factors the only problem with this is not exactly random products of primes but you can do so you can do this now commitments are possible that's very important so I'm describing very high level I'm hiding lots of things and even the definition of zero knowledge The formal definition is quite intricate. It's not, the intuition is obvious and I said it, but actually formally defining is non-trivial. But at a high level, I'll give you some idea about how a zero-nose proof looks like.

1:31:06Now we have to think about what theorems am I proving to you. And it was very important to us to figure out what problem to think about, even though today you can do it for others, but we were thinking about theorems of the type, here's the graph, we can color it in three colors. It's also a formal mathematical statement, either it's doable or not, right? And we simply focus on proving in zero-knowledge claims of this type. The graph we both know, I claim I can color it with three colors. You don't believe me, you want to be convinced of this fact. and you don't want me to cheat you, you don't want me to be able to, you should be an interactive proof and moreover, I want it to be zero knowledge.

1:31:58I don't want you to have the slightest idea of what my coloring is or what anything you didn't know before is. Okay, so roughly the way it works, zero knowledge proof for this particular set of claims that are certainly not all claims. They are very structured claims. We look like the following. We iteratively repeat the following procedure. I put commitments for the coloring on every vertex. I don't tell you it's green, red, or blue, but I put a commitment to one of them on each vertex. You will choose at random an edge of the graph. and ask me to open these two envelopes, to decommit. And you will check that the colors you see, first of all, are in this set.

1:32:57They are not gray or orange. They are either red, green, or blue, and that they are different. This should give you some maybe slight advantage or slight support to the belief that maybe I'm not cheating you. Of course, it's a very limited one because I can cheat you in some corner. So we have to establish two things. We will repeat this again and again. We have to establish that it's a proof, it's an interactive proof, that I cannot cheat you. And we have to argue the zero knowledge part. Okay, so let's do one at a time.

1:33:41to do the correctness that I cannot fool you. It's very simple. It's the following. If the graph is not three-colorable, whatever I commit for, there's one place which is an arrow. Either it has the wrong color and not a loud color, or two colors are equal. You have some non-trivial chance of catching this with your random guess, right? I mean, it's one over the number of edges. It's not so small. If you see a graph with 100 edges, it's one in 100. If we repeat it not 1 ,000 but 10 ,000 times, the probability that you don't catch me in any of them drops exponentially to zero. Right, so, of course, there's a...

1:34:31Okay, so this establishes that I cannot fool you. The zero noise is a more serious problem because if I keep using the same coloring, you will ask me about this edge and this edge and eventually you'll know the coloring of all colors. Here's something that's really special to the coloring that is being used. If I have one coloring of the graph, I really have six because I can promote the names, that I can replace red and green, and it's another valid coloring. So what I do really in each one of these iterations is not using the same coloring, but using a random one of these possible six. They are all legal, and I just use one of these six.

1:35:20What's the advantage of this? When you open a pair of vertices under this distribution, one of the six, what you will see, if I do have a coloring, and that's the only, I want to stress, we only have to establish zero knowledge if I really can prove the theorem. So if I do know the solution, the proof, I want to protect my knowledge. What happens when I reveal to you two of these colors on the adjacent vertices of the graph? It will be true. In this distribution, when you are 60 to two vertices, it would simply be two different random colors. Right? This is what you get by all permutations, the six permutations.

1:36:04What did you learn from this? Nothing. You could have picked two random different colors. You didn't need me for that. So you didn't learn anything. So in each iteration, you learn nothing. So this is the idea of the proof. Well, this is the end of the proof that I can, showing that there are zero knowledge proofs for all graph coloring, three coloring problems. What about all the Riemann hypothesis and the p-versus NP and factoring and all these other things I want to claim to you and prove it's zero knowledge. Here, it's very simple. You use NP completeness. This is an NP-complete problem. Anything that can be proved is really something in NP.

1:36:51This is the definition. So you reduce it to three-calorie, prove it in zero knowledge. And the main point about reductions in NP is that they don't only convert the yes-no answer in a consistent way, that if this is solvable, this is solvable. But actually, if you have a witness, if you have a proof for, I don't know, whatever, However, it will become a legal three-coloring of the graph you generate. So if you have a proof, you can also have the three-coloring. It's very important. The reduction also provides a translation not just between the instances, but also between the proofs. So NP-completeness theory gives you for free that if you solve the problem for graph-coloring instances, you solve it for any.

1:37:45You can prove anything is zero knowledge.

1:37:47The Peterman Pod Host:So with the zero knowledge proof, you can never be 100 % sure. No, no. Okay, but practically, I mean exponentially approaching. You can make the completeness 100%. Namely, if I do have a proof, you will be, yeah, there will be no error. But there is a slight possibility that the graph is not three-colourable, and you will not catch me. You can make this exponentially small. You cannot make it zero. When I think of cryptography, one-way functions, there's this idea of quantum computation that's kind of changed complexity theory a bit. A bit, yeah, big time, yeah. Yeah, and I wanted to ask your thoughts on how quantum computation or that model of computation is changing complexity theory.

1:38:40The Peterman Pod Host:What are the big takeaways? Okay, let me say what it is, first of all. I mean, quantum mechanics is a theory of nature that everybody believes and accepts. So, like with randomness, we can ask why not enhance computers with this physical knowledge. We allow our computers to operate in the way that quantum mechanics dictates, namely manipulate bits in superposition using unitary operations, whatever this means, but according to the rules of quantum mechanics. and really strange things happen in quantum mechanics. I'm sure many people know because there are all these interference patterns. It seems that you can...

1:39:37Basically, you are working with probability theory with negative numbers. Events cannot aggregate only. They can cancel each other. and okay so it's a model of computation it's a generalization of Turing machines in fact it's a generalization of randomized Turing machines. It's very easy to see that a quantum computer is at least as strong as a probabilistic computer How do you see it? You just measure the quantum bits before you start You measure them this is what I mentioned about the photons in the beginning if you have some basic superposition. I mean, a quantum bit, if you measure it, you get a random bit.

1:40:22So because of that, quantum computers are at least as strong as probabilistic computers. Okay, so it's a model of computation, and it was suggested in the 80s. Feynman and Manning and others suggested, you know, letting algorithms use these quantum mechanical operations, mainly originally for just simulating quantum systems rather than building big apparatus, yeah, like we simulate other things, turbulence, I don't know. What's the power of quantum algorithms? Again, let's say running in polynomial time or efficient ones, can they do more than efficient classical ones, deterministic or probabilistic?

1:41:13And it wasn't clear for a while, and there were a few examples that were very stylized, but not for concrete natural problems we care about. And then in 1994, Peter Shaw sort of created an earthquake or an avalanche. But he found quantum algorithms that are efficient, that factor integers, and also compute discrete logarithms, the two most basic underpinnings of all security systems that exist. And this set the world on fire, right? So lots of people try to do a lot of things. Of course, you know, people want to have them. These algorithms they implement. and maybe they want to break or other people skip the system.

1:42:05So as you know, since then, billions were invested by companies, by governments, by lots of people trying to build the technological infrastructure. And this is extremely complicated. Holding bits in superposition is extremely complicated. There's things that are called the noise. I mean, when people build classical computers, like for Neumann here in the building next door, you know, noise was one of the serious problems because the bits were really in vacuum tubes. And they had to contend, and in fact, he built a nice theory of classical computers that have errors. Noise, they have to cope with errors.

1:42:55Some of their components can be faulty. But today's hardware has no errors to speak of. I mean, there are error-correction mechanisms, but we don't need them for classical computing. Intel chips don't have, I think, error-correction in them. Hardware is very reliable. When you move to quantum, there is this decoherence noise. In quantum mechanics, everything depends on everything. The world can influence the computation in your laptop. And protecting from this is very hard. There are quantum error correcting codes, and that's part of the solution. That's only one of the problems. Just holding bits in superposition is hard.

1:43:42And there are many hard technological issues, and there's focus on that. So this is one line of huge investment. The other line comes from cryptography because, of course, everybody should be worried, right? I mean, you know, forget quantum computers. If tomorrow, I mean really tomorrow, somebody finds even a classical factory algorithm in polynomial time, I think there will be chaos in the world because nobody can do any transactions because most security systems still rely on factory. And so, of course, we want to change the underlying assumptions of security. We want to rely. The whole revolution in cryptography was that we rest cryptography on computationally hard assumptions.

1:44:37And with this we build all the wonderful public key systems and all the magical things you can do by assuming that players are computationally limited. But now if the adversaries are quantum computers, suddenly they can break this assumption. You want to find other mathematical problems, computational problems, which are somehow hard even to quantum computers. So that's the whole field. This change, complexity theory and cryptography. There is an army of people who are just trying to invent problems. I maybe should stress. One way functions are easy to find. I mean, most problems you... Most processes in nature are not easily reversible.

1:45:34You make an omelet from an egg, you know, reversing this is... Doesn't take the same amount of time. That's a usual example of a physical one refunction. But trapdoor functions like factoring, problems from which you can build public key systems, and that's the most really basic thing for electronic commerce, are few. We don't know many, so we know this. I mentioned factoring discrete log. In the 90s, ITAI and Dwork created another type of step or function from problems on lattices in high dimensions. I will not describe it, but it's another problem that people refined and got a few more similar of similar nature.

1:46:24And it turned out when Peter Scholl discovered this, people immediately tried to solve other problems with quantum computers. In fact, even today we cannot solve too many other problems with quantum computers. These are special. The special thing about them is that somehow you can reduce them to finding periods in a signal, and periods is like Fourier transform. A Fourier transform turns out to an exponential space. But Fourier transform you can do somehow with quantum computers, with interference. The latest problems, and problems related to it, some called learning with errors and similar, you know, to this day, nobody found an efficient quantum algorithm for them.

1:47:12So there's no even theory. Forget building quantum computers. We don't know how to solve them. And so what the world is, it's not just complexity theory, the whole physical world of security systems and also governments like the NSA is supporting or asking the world to produce assumptions that may be resilient to quantum attacks. And so this is a huge change. There's a major change in the interaction between computer scientists and physicists, which grew tremendously since this discovery. And it's rich in many, many ways that are not... The influence of the algorithmic thinking on physical theories, including today theories in quantum gravity, black holes, is immense.

1:48:12And we have new sources of problems and new models and new complexity classes, etc., etc. And there's a fantastic, fantastic interaction. And it's also an enriched complexity theory in that it turns out that you can discover quantum algorithms and maybe then de-quantize them. In special cases, like I mentioned factoring before. The randomizing. And so sometimes it's a way, it's a road to discover new algorithms. It reveals connections between problems. It's extremely rich. But one of the maybe most amazing consequences is that people, I mean, we, being what we are, we make up models and study them.

1:49:05And the interactive proofs I mentioned before, it turns out that even before quantum, they were generalized to interactive proofs, not with one prover, but with many provers, which seem to be weird, but turns out to be very important in itself because it led to this PCP theorem. Then people said, OK, let's allow quantum verifiers, quantum provers, and see what they can. So one amazing result, which is about five years ago, is the acronyms. Of course, we have acronyms for all these complexity classes. It's MIP star equal RE. You may have seen it. Maybe you didn't. And it looks weird, but I'll tell you what it says, really.

1:49:53It says that there is a weird, really weird proof system with quantum provers that, you know, are trying to convince verifiers, an efficient verifier. And it turns out, you know, you ask for which problems can they do it. Forget the wrong knowledge, just convince. And it turns out they can do it for the halting problem, for problems that are not computable. Things that are not computable are verifiable by efficient verifiers if the provers are quantum and they are entangled and whatever. but it's a weird proof system, very weird, but it does something that looks totally ridiculous. Things that are uncomputable by any classical computer are verifiable in this interactive probabilistic sense by efficient verifier.

1:50:51So what I like to say in talking about this is that it seems that the best reaction, best hypothetical reaction of anybody who hears this. Okay, you're a complexity theorist. You play in your sandbox and you build all these sandcastles and make up all these models that have nothing to do with anything just because you can. And once you're weird enough, you get weird enough consequences. So one message which I think is very powerful is that this result has absolutely fundamental impact on math and physics. It turns out that it implies, and this was already done in the initial paper, it implies resolution of well-known conjectures in math and physics.

1:51:45It turns out that, you know, weird as it is, It's a new mathematical technique to solve problems that nobody had any idea. Famous problems, important problems that fields were dedicated to, are resolved by this result, by the techniques of this result. So you ask the impact of quantum... You see, the impact is many generations over for different motivations and developments, but all of them following the methodology of complexity theory, of understanding the power of, you know, computational models, proof systems, and so on, has magically led to such a consequence. And this is just, we are in the beginning of this, right?

1:52:34This type of proof technique is now being explored and used and there are more results, you know, using this type of techniques to long-standing problems. Pretty amazing.

1:52:45The Peterman Pod Host:That's incredible, yeah. I mean, in complexity theory, there's these, what do you call them? I guess like Venn diagrams of all possible problems. And the implicit assumption in this picture is that these are decidable problems. Yeah, yeah, yeah, yeah. In some of these diagrams, there's a little, in the corner, there's a... Undecidable. Undecidable ones. Yeah, unreachable, yeah. Right. And it's just, I can't, I don't even understand how you could verify an undecidable. It's a 200-page paper. It builds on 10 years of understanding, which is both a lot of development in the quantum algorithms and quantum proof systems sphere, but also relying on techniques from classical proof systems, which have to do with coding theory and various algebraic stuff that is used to prove, for example, the PCP theorem, as I mentioned.

1:53:46It's, you know, it's a huge body of work. And on top of this, they wrote this 200-page paper in which they had to develop many more tools.

1:53:56The Peterman Pod Host:And yeah, there you have it. Wow. I mean, when someone produces 200 pages of such complicated work that makes such an outrageous claim, how does that get verified by people? It's a very good question. This tool for any mathematical result that is complicated. And, of course, you know that, of course, proofs of PIVAS, NP, and Riemann hypotheses are generated very frequently, but some of them were generated by very serious people and took a long time to refute in these two cases.

1:54:43but others like the Perlman proof of the Poincare conjecture, one of the clay million dollar problems was another one like that and this took several years to verify and fix small vaccine and books expositing this proof were written and eventually this particular paper is for some reason still in the referring stages in the Annals of mathematics now probably almost six years. It will be done. It's robust in the sense that already new papers were written with this type of tools, in fact, giving somewhat alternative proofs of the same statements and stronger statements in order to resolve other mathematical conjectures.

1:55:29But yeah, it's a serious thing. And in fact, the original paper had the bug. Like the original paper with Fermat by Wiles, Fermat's last year, also had a bug and it was fixed. And this was fixed. This was very early on, just when it came out very quickly fixed. So any mathematical claim, your question is very important for. In general, mathematics and mathematical truth is a social construct. So it's what mathematicians believe. Maybe we are moving into a world in which we have lean proofs of, you know, we have a formal way of writing proofs and you can maybe formally verify them. But anyway, I think that this community is quite certain about, yeah.

1:56:25The Peterman Pod Host:In complexity theory, it's very mathematical in nature when I read the papers, but obviously it has implications in computer science. What's the relationship between math and computer science to you? Well, I think the theory of computer science, my field, complexity theory, algorithms, theoretical side, is really lucky to have these two parents. It lives in both spaces. It is a mathematical field in the sense that most of what we generate are theorems and proofs in the mathematics sense. On the other hand, it's related to computation because the kind of questions we ask ourselves, the problems we are trying to solve, are motivated, partially motivated, by trying to understand computation.

1:57:18So you can think of theoretical computer science very much like you can think about analysis and algebra and topology. There are notions, you know, in algebra you are trying to understand equations or systems of equations. And in analysis, you are trying to understand, very generally speaking, inequalities and continuous spaces. So there are these notions you are trying to understand. Computation is one of these notions. You are trying to understand what can you produce by an evolution of simple local steps to a given environment, the input. And this can be a sequence of bits, or it can be the DNA of a person from which you produce proteins using computation, or you produce a new baby using the evolution of a fertilized egg, or the weather.

1:58:23or, you know, so computation is sort of everywhere. And we are trying to understand it in ways that are different, right? We care about resources, how much resources are exerted in any such computation and, you know, trying to model it, trying to understand the algorithms that are underlying natural phenomena. So we live in both spaces. We have a lot of input of problems and models from industry, technology, systems, and so on. And we have all the mathematics. We have the rigorous side coming from, and the aesthetic side, I would say, like creating models of proof systems because they are nice, because they are interesting, not because they are implementable necessarily.

1:59:20So living in these two spaces is extremely beneficial to this theory of composition.

1:59:31The Peterman Pod Host:You mentioned earlier that some people might have the perspective of complexity theory that it's kind of solving problems for problem's sake. I read in another interview you did that you were never motivated by application? And then my natural thought was, what motivates you to solve all these really tricky, complicated problems? Okay, so let me say one thing about your, the beginning of your question says about solving problems. I think that what we do more, much more, is modeling things. I mean, modeling things then give rise to problems that you want to understand. So I think the modeling part in the theory of computation, modeling various forms of computation is a large part of theoretical computer science manifests itself in particular in cryptography.

2:00:23Well, there are models of, you know, adverse and distributed computation. There are many. I think modeling, just asking questions, is, you know, and creating, making definitions, is a very central part of the field. and it happens more than in mathematics, maybe because they are more ancient than maybe definitions happened earlier. But I want to stress this. That's a very important thing. For example, we discussed randomness and our definition of randomness is totally different and it gives rise to very surprising and interesting, practically, theorems. Okay, now that we settled that, what motivates me or what motivates other people.

2:01:13Of course, everybody has their own motivation. I am a product of computer science education. All my undergrad and grad school and postdoc and everything were in computer science. So I think that I certainly am sorry that I didn't take many more math courses because then I wouldn't have to learn things later in life. But that aside, I think that the focus on computation, which is what computer science education gives you, different systems and different issues, there are, of course, algorithms in databases and algorithms in programming languages and, in fact, famous algorithms. In other fields, there are models and algorithms.

2:02:04So computation is something that I'm interested in intrinsically. I'm more interested. Over the years, realizing that computation, the field expanded to interact with all the sciences and that computation happened everywhere in various forms, in physics and biology and so on, makes it a fundamental object of study. And for me, given the way I was brought up, I guess, the particular is fascinating in itself. I know from just experience that lots of the theorems we prove, not many, but probably with much higher proportions than in other areas of mass, are impactful in the world, in real systems, in security systems, in blockchains, in the real world.

2:02:54But this side, this particular side of seeing exactly how you translate your algorithm into a system or your zero-knowledge proof, I predicted when we came up with the zero-knowledge proof that it will never be implemented. Because the protocol that I described more or less to you is very costly. I mean, you want to prove that I'm producing a product of two primes and I convert it to a map and then I do all this complicated procedure many times.

2:03:29The Peterman Pod Host:So it doesn't seem that anybody would ever use such a thing. But I was wrong. I mean, I didn't realize how motivated people can be and how important applications of their knowledge can be in the real world, not in theory of protocol design. And they did simplify, maybe using more assumptions, different assumptions. There's a recent breakthrough of a postdoc here, Raoul Ilango, you may have heard because it got some publicity in front and so on, where he introduced into the assumptions of cryptography not just hard computational problems, but also things of the nature of Gether's theorem, that something is unprovable in some mathematical proof system, like St.

2:04:20Mello-Francki, whatever mathematicians use. Somehow using that, they can get zero knowledge that's non-interactive. Yeah, it's an amazing thing. It gets, you know, things get richer. What I want to say is that, again, from experience, I have 45 years of experience. of this working in this field, which have been fascinating. And, you know, I mentioned to you in the email, you know, there's extra benefits to this field. I think the community is amazing, not just that it has so many brilliant minds and young, brilliant minds are entering the field all the time, but it's also very lively and interactive and collaborative and, you know, just, yeah, many of my best friends are also colleagues.

2:05:16So it's fantastic. But the understanding that, the theoretical understanding of many things that we maybe ask ourselves for aesthetical reasons that are mathematical, that we generalize something for generalization's sake, which may not have a counterpart in industry. In fact, show us work on quantum algorithms. You can say, why do that? There are no quantum computers. Maybe let's wait until somebody built once and we understand why, you know. So no, the answer is no. No, you should try to understand whatever is natural for you to understand. This field has already, you know, maybe it was not clear 40 years ago, but it's certainly clear now that all, you know, that lots of theoretical understanding is not just productions of mathematical results, but because it is about computation, it is meaningful, I don't know, often enough or whatever in the real world.

2:06:31There are many, many other examples besides kryptonite quantum, recording theory and the first revolutionized coding theory mainly because of the PCP theorem, tools needed for. So, you know, there are lots of examples, and this eventually went into systems, you know, for memory schemes or whatever. Look, I'm interested in P versus NP. This is a question about impossibility, right? This is a problem. We still didn't get closer in this, at least suddenly the years I've been at it. We are not much closer to showing hardness for anything. We don't know that multiplication is harder than addition. It's a basic question.

2:07:20So this kind of question by itself is certainly not practical. I mean, it's not clear. Well, it is a little clear because if you find out of functions, maybe you can substantiate cryptography on a theorem rather than on assumption. But anyway, there are questions in the field that don't directly relate and will not directly relate to implementations of any system. But they are all parts of trying to understand what efficient computation can do and what it cannot. Or when can you minimize resources of some type and when you cannot and how do different problems relate to each other. So this basic methodology of the field that created some wonderful edifice.

2:08:09And I would say that we are still in the embryo stage of understanding computation.

2:08:16The Peterman Pod Host:You mentioned a few times in this conversation, you know, some people made a major discovery and then it, you know, kind of broke some assumption that was maybe 50 years ago. And, you know, researchers make these advances. And I know in your career, you've made a few as well and the time space between payouts is sometimes decades yeah you know where you make a major sometimes because a lot of people's careers like maybe you know if you're just an engineer you just you know you got your shipping projects every year um but in in your case like let's say you imagine you discovered p equals mp or something like that yeah like how do you feel when you make those discoveries, those sparse discoveries in your career?

2:09:02The Peterman Pod Host:Well, it's great. Yeah, it happens. The big ones happen rarely. I think of science, I mean, realistically, science and math is, you know, a community of arts work. I mean, most progress, we have these conferences, COE conferences, Stock and Forks, and then And we have all sorts of, you know, satellite conferences. And there are hundreds of papers in them. Satellite, I mean, focused on concrete area and learning theory, crypto, I don't know, online algorithms. There are many, many, there are thousands of researchers working in this. I don't know, maybe. And they are producing many papers a year.

2:09:47And most papers are, and most of my papers are, you know, we make a little progress in understanding something. Usually it's not a big reason. You know, we discover a variant of a technique or we can strengthen a bound on some. And I find this essential. I think this is true in science in general. And bigger understandings come more early. and they suddenly, you know, they send this shockwave to everybody, learn them and uses them. But, of course, you know, those bigger understandings, it doesn't have to be a resolution of 50 years of paper. It can be something that, you know, when Barrington discovered his algorithm for counting that I mentioned, he was trying to actually prove that it's impossible.

2:10:39And it was not like somebody asked this question. And the answer was obvious, it's impossible, right? So when you have an insight of this type, it's amazing. So whenever you realize something really new for you and for the community, it's a phenomenal result. It's rare. I tell all my students and postdocs that, yeah, it's not, you know, you don't work for the million dollar. A million dollar is nothing, of course, for some of these problems. But you work because you enjoy the practice of it. You enjoy thinking about these problems. In fact, most days in the life of my life, mathematician's life, is unlike a systems person.

2:11:29You go in the morning, you come back in the evening, and you fail to do what you want to do. You just couldn't. You just thought more. And I think that it's really important. So it's not for everybody. Clearly, it's not satisfying. This happens every day and every week. It's not for everybody, but it's for the people for whom this activity of trying to think, of throwing ideas, of failing but learning from the failures, people don't realize that often you learn. I mean, the fact that you failed is not just a wasted day. There is something that you gain from it, maybe subconsciously, that will help you later.

2:12:17So unless you enjoy this activity, maybe this field is not for you. And yeah, and then you see something, and even if it's small, sometimes it's very satisfying.

2:12:30The Peterman Pod Host:Last question for you, and I think people in the field might be curious because you have so much experience is, you know, if you could go back to the beginning of your career when you just started becoming a researcher, is there any advice that you'd give yourself? I think I was lucky enough not to think that I would change anything. I think I was lucky enough, and many people are lucky in this field because the field is so accommodating to young people. It's completely leveled. There's no hierarchies. People would go to conferences and meet. I remember my first conference meeting Dick Carp, who was a god in the field and invented and did all these NP-complete things.

2:13:24I was a first graduate student, and somebody introduced me to him, and he immediately asked me what I'm doing. And I said I proved that some problem was NP-complete, and it was actually interesting. It amazed me. I was lucky to have phenomenal mentors as an undergrad, as a graduate student. I was lucky to have unbelievable collaborators over the years. And, you know, you learn from all this. So it's not a very informative advice to people to tell them to be lucky. I think this environment exists. I think that one piece of advice I give everybody is that in the early stages is to work on things they enjoy the most.

2:14:15So when you are discovering your talents as a researcher, one direction may be, you know, these are hot problems. If you solve them, then you... But maybe that's not your problems. Maybe it's not your affinity to them. You have to experiment with the type of problems. It's good to have a variety of areas and papers to read in these areas or problems to understand. It's always good to start with a few to sort of better understand your capabilities. And often what you like most is what you are better at.

2:14:47The Peterman Pod Host:Thank you so much for your time, Avi. I really appreciate it. Hey, thank you for watching this podcast. If you liked it and you want to see the show grow, please support with a comment or a like. Also, if you have any recommendations for people you want me to bring on, please drop a comment. Guests like Barbara Liskov, Mike Stonebreaker, Mark Brooker, these were all people that I brought on because someone left a comment. On another note, aside from the podcast, I'm working on building the ergonomic keyboard that I wish existed. Here's a glance at the prototype. It's a split keyboard. So there's two sides.

2:15:22This is in the case.

2:15:23The Peterman Pod Host:But yeah, we launched on Kickstarter and we hit our goal within eight hours of launching. I really appreciate it if you were one of the people who grabbed one of the early units. We're now working on the long journey of building the tooling now. And so if you still want to pick one up, I've left the late pledges open on Kickstarter. So you can grab one there. I'll put a link in the description. Thank you again for watching the podcast and I'll see you in the next episode.