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

Avi Wigderson is the only person in history to have won both a Turing Award (computer science) and Abel Prize (math). I interviewed him all about his field. • My ergonomic keyboard project I mentioned, you can follow along here: https://read.compose.llc/ Podcast links: • YouTube: https://youtu.be/5GUcvSAJcJw • Apple: https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835 • Transcript: https://www.developing.dev/p/turing-award-winner-p-vs-np-zero Thank you to this episode's sponsor for supporting my work: • WorkOS: makes your app Enterprise Ready with easy to use APIs to add SSO, SCIM, RBAC, and more in just a few lines of code, check them out at https://workos.com/ Timestamps: (00:00) Intro (01:08) P vs NP (14:51) What if you relaxed correctness (25:38) Why NP complete problems are equivalent (30:33) Space vs time complexity (43:06) Why people use SAT solvers (45:53) Randomness is a resource (55:48) Randomness depends on computational power (01:21:20) Zero knowledge proofs and their significance (01:38:30) Quantum computation and why it matters (01:56:24) Math vs computer science (02:08:16) Major breakthroughs and his experience (02:12:31) Advice for his younger self (02:14:48) Outro Where to find Avi: • Wikipedia: https://en.wikipedia.org/wiki/Avi_Wigderson • Personal Website: https://www.math.ias.edu/avi/home Where to find Ryan: • Newsletter: https://www.developing.dev/ • X/Twitter: https://x.com/ryanlpeterman • LinkedIn: https://www.linkedin.com/in/ryanlpeterman/ • Threads: https://www.threads.com/@ryanlpeterman • Instagram: https://www.instagram.com/ryanlpeterman • TikTok: https://www.tiktok.com/@ryanlpeterman Referenced in this episode: • PCP Theorem paper: https://www.cs.umd.edu/~gasarch/TOPICS/pcp/AS.pdf • Paper on SAT approximation hardness: https://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf • Turing's paper: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf • Original paper on NP completeness: https://www.cs.toronto.edu/~sacook/homepage/1971.pdf • Ryan William's breakthrough result on space vs time: https://people.csail.mit.edu/rrw/time-vs-space.pdf • Old result on space vs time: https://www-wjp.cs.uni-saarland.de/publikationen/HPV75.pdf • Paper describing constant space majority solution: https://people.cs.umass.edu/~barring/publications/bwbp.pdf • Fast primality test paper: https://www.sciencedirect.com/science/article/pii/0022314X80900840/pdf?md5=6f748cd82fa8efa1a637efab5f632baa&pid=1-s2.0-0022314X80900840-main.pdf • Deterministic primality test paper: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf • Randomness vs observer paper: https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/How_To_Generate_Cryptographically_Strong_Sequences_Of_Pseudo-Random_Bits.pdf • Hardness vs randomness paper: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf • Erdos original sum vs product paper: https://users.renyi.hu/~p_erdos/1983-18.pdf • Terrence Tao sum vs product paper: https://arxiv.org/pdf/math/0301343 • Seminal interactive proof paper: https://www.cs.miami.edu/home/burt/learning/csc609.221/goldwasser-micali-rackoff-knoweldge-complexity.pdf • Zero knowledge proof paper: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GMW86/GMW86.pdf • Shor's algorithm original paper: https://arxiv.org/pdf/quant-ph/9508027 • Lattice paper (new hard problems): https://dl.acm.org/doi/epdf/10.1145/258533.258604 • MIP* vs RE paper: https://arxiv.org/pdf/2001.04383 • Zero knowledge non-interactive proofs: https://eprint.iacr.org/2025/1296.pdf

Speaker names marked ? are inferred from speaking time and the show’s known hosts — they are not voice-verified.

• 0:00Speaker 00

  If tomorrow, somebody finds even a classical factoring algorithm in polynomial time, I think there will be chaos in the world.

• 0:07Ryan Peterman?

  This is Avi Wigderson, Turing Award and Nobel Prize winner, and I interviewed him all about his field.

• 0:14Speaker 00

  The question of P vs NP is whether we can solve all the problems we really want to solve. The quality of randomness is in the eye of the beholder, or in the computational power of the beholder. How can anybody convince me that they have a proof of P different than NP? And nevertheless, I know absolutely nothing about the way they proved it. And it's just that they can do it for the whole thing problem, for problems that are almost computable. You know, if tomorrow, somebody finds an efficient algorithm for NP complete problem, you know, what do you do?

• 0:49Ryan Peterman?

  Here's the full episode.

• 0:54Ryan Peterman?

  In one of your lectures, you mentioned that P equals NP is philosophically about the fundamental limits of human knowledge. What is P equals NP? And how does it relate to human knowledge?

• 1:08Speaker 00

  Well, in the simplest way, and I will talk at a high level, we are interested in various problems in life, in all sorts of problems, mathematical problems, scientific problems, medical problems, personal problems, intellectual problems. We are in the business in computer science of solving problems by computers. Now, we would like to somehow classify those problems that we can solve, right? To know what we can know, what the problems we can solve are the things we will know, we will understand. So there are all these problems that we want to understand. There are many of them.

• 1:54Speaker 00

  And there are the problems that we can understand, can solve. Okay? In a very basic way, the first class is NP. All the problems we want to solve are really NP problems. So it's a class of problems. A subset of it is the problems we can solve. There are the problems we can currently solve, but we are interested in all the problems we can solve in principle, we can ever, you know, really solve. So, the question of P versus NP is whether we can solve all the problems we want to solve, whether we can know everything we want to know. This is basically about the limits of our knowledge.

• 2:39Speaker 00

  Of course, I have to justify why, you know, these classes, which are mathematically defined, actually are captured by this intuitive, intuitive meaning, if I'm giving them. P is very easy to justify. What we can solve is what we can, you know, solve in our lifetime using whatever we have. Let's say all computers that we have using efficient algorithms. So problems we can solve are problems you see in our apps in our phones, right? If there's a navigation app, it means somebody invented an algorithm that's efficient enough to solve any, you know, shortest path problem

• 3:20Speaker 00

  between any two places in any kind of map. Okay. Why are all the problems we want to solve are NP problems? What is NP? NP is a class of problems, the mathematical definition, are problems so that, you know, whether they are easy or hard to solve, we don't know. But if somebody hands us a solution, then we can easily check that indeed it is a good solution. Now, why are all problems humanity is interested in of this nature? You can think there's no limit to what we may want to know. But I claim that essentially in any human endeavor, the

• 4:07Speaker 00

  If you are embarking on any problem, if you really, seriously want to solve a problem, the least you want to know is that when you hit upon a solution, you'll recognize it as a solution. And why would you ever start on looking for something if you would never recognize it as what you looked for? So you think mathematicians are looking for proofs of theorems? Suddenly, if somebody gives a proof, you know, wrote a paper about it, we can verify. If a scientist wants to explain data, you know, about the planets or about, I don't know, bacteria or whatever, you know, want to develop a theory,

• 4:51Speaker 00

  so that's what you are searching for in this case. And, yeah, we, again, scientists write papers about their theories. They have to be consistent with the data. We have a way of recognizing that this is a good solution. Engineers, you know, are usually tasked with creating something, bridge or phone or, you know, something, under some constraints. It can be monetary constraints, physical constraints, all sorts of, you can use this, but not this, and so on. But anyway, if an engineer designed something, whoever gave them the task can look at it and say, "Well, you violated some constraints." "Oh, no, it's good.

• 5:34Speaker 00

  You really delivered what we were looking for." So I'm giving you examples. I mean, I can give many more. Detectives are supposed to solve crimes and, you know, we know from detective books, you know, they eventually provide it. So these are examples of very fundamental human endeavors that are, you know, encompass almost everything I can think of. In all of them, what people are searching for has the property that when a solution is found, it is easily recognized. So, repeating in the beginning, NP are all problems that we can honestly say we really want to solve. NP are those that we can solve.

• 6:19Speaker 00

  Whether they are equal, you know, if they are equal, then everything we would want to know, cure for cancer, anything you imagine, can be, you know, just the very fact that...

• 6:32Speaker 00

  A solution can be easily recognized would imply that it can be efficiently found. That means that we can know everything we ever want to know. It's a fundamental question about human knowledge.

• 6:44Ryan Peterman?

  So I know this is one of those millennium prize problems. There's a million dollar prize if you can provide a proof for this. You know, I can imagine you could prove that they're equivalent. You could also prove that they're not. If you had to guess, like, when an if a proof comes, which direction would your intuition say it goes and why?

• 7:07Speaker 00

  I think that my intuition, and this probably holds for almost all members of the theoretical computer science community, is that they are different. I think there are several reasons for that, and I will already tell you now that they, you know, they are not that convincing. One is, I think, intuition that most of us have, that, you know, finding something is really hard than just checking that it's there. If you've lost your keys or your phone and, you know, you have no idea what to look, but, you know, if somebody points out, oh, you left it on the, you know, window sill or something like this, you say, ah, yeah, I did.

• 7:51Speaker 00

  So we have this experience from life that finding is typically a harder task than just checking that it is what we look for. Another is that real NP problems occur all over the place. They occur in optimization, in logic, in other aspects, in mathematics, in verifying that algorithms and protocols and security systems actually work, all sorts of. And in this generality, these optimization problems that are NP problems, maybe NP

• 8:31Speaker 00

  hard problems, people try to solve for completely, you know, egocentric reasons, to make their company richer or to... And there are thousands of these, and they manifest themselves in many different forms. And so over the, maybe...

• 8:52Speaker 00

  Fifty, sixty, seventy years, people seriously looked for algorithms for these very different ones and couldn't find any. This, you know, may seem like there is no such solution. And in a, getting a bit more technical, NP problems, NP complete problems in particular, seem to require search over an exponentially, exponentially large space. Like all the, all the possible, you know, solutions to some system of equations, for example.

• 9:35Speaker 00

  And somehow, NP is about having a general method for cutting down this exponentially search space into searching over something much smaller in a clever way. And this would apply to all these problems. So that would be equal NP, and people don't think that there is such a way. But as I said, you know, these are, yeah, these are intuitions that are, you know, maybe pretty strong. And yeah, I think that's the only... You know, if tomorrow somebody finds an algorithm for, an efficient algorithm for NP complete problems,

• 10:16Speaker 00

  using some new idea that nobody ever thought of, you know, what do you do?

• 10:22Ryan Peterman?

  That would change the world. In software engineering, we, we use algorithms all the time. And they often have these very satisfying properties where the solution, you know, we, we use space or some algorithm that can take something where the brute force is, something much larger, to, down to something that's polynomial time or something very reasonable. But in all these NP problems, it's pretty unsatisfying that the best we could do is brute force. Is, am I understanding that correctly?

• 10:57Speaker 00

  Yeah, you're, yeah, you're understanding it perfectly correctly. I think that maybe what you're getting at is that... NP complete problems are, you know, a particular NP complete problem is really a family of instances, right? I mean, you want to to find a Hamiltonian tour, some traveling settlement tour through some map. You know, there's this map and that map and this network and other network. And, you know, there are many, many instances. When we talk about an algorithm for them, typically we say an algorithm is efficient if it's efficient and correct on all of them. In software engineering and many aspects of, you know,

• 11:42Speaker 00

  many optimization, in many real world problems, the instances is a much more restricted set.

• 11:52Speaker 00

  You know, they come from, you know, trying to verify a particular protocol. Or, I don't know, protein folding, if you want to think about a biological example. The way it is phrased as an NP hard problem is you want to minimize the energy of a system under some various constraints, which have to relate to the chemistry of the various molecules and atoms that appear in the protein.

• 12:25Speaker 00

  And this kind of optimization problem, one can easily prove is NP hard. And nevertheless, our body folds our proteins all the time, you know, in extremely efficiently. Now, why is that? Of course, I don't know really why is that. But it would seem that evolution designed proteins in such a way that this, you know, folding them, only them. We don't have that many proteins. There are not exponentially many proteins in the body. There are only a few that maybe are more prone to efficient energy minimization. So, and more generally, I think in software engineering,

• 13:10Speaker 00

  you're, or at least in verification and testing, you often want to check that something meets the specifications.

• 13:19Speaker 00

  You usually translate it into a satisfiability question of Bula and formulas. The formulas that you get, the instances that you get out of these.

• 13:32Speaker 00

  Have some structure. And maybe for them, various greedy approaches or clever, not just greedy, but clever, but efficient methods work. In other words, making it short, instances that just come up are not the worst-case instances. We have many examples of this that we can actually prove this. For example, early on, it was recognized that the simplex method, which is an algorithm to solve linear programs, on the one hand, requires exponential time for, you know, worst-case system of inequalities.

• 14:16Speaker 00

  But in practice, it seems to run in linear time. So evidently, the sets of linear systems that we tackle in real life are, you know, have some extra structures that allow this particular algorithm to solve them efficiently. Of course, today, we know an algorithm that's efficient for all linear programs, but it's much more complicated. And people don't, or I don't know how much it's used in practice. But the simplex method is very simple to run, and yeah, usually it works.

• 14:51Ryan Peterman?

  You mentioned the protein folding. And I mean, yeah, that's an interesting one because it's an NP problem, but it was solved to an acceptable extent. And when I was reading about it, it wasn't solved for 100% of cases. It provides a solution and a confidence score, but it doesn't give you the answer 100% accurate, you know, fully computed. And so when you think about these NP problems, what if you relaxed the criteria of being correct? Could the asymptotic complexity be less than the exponential that we're talking about?

• 15:33Speaker 00

  Yeah, it's a very natural and good problem. So in the protein folding, you were talking about alpha fold, I guess, which is an algorithm heuristic. That was learned from existing proteins and is working very well on you know, on instances it didn't see but are still proteins coming from the body. Even if it did perfectly on this, not just, you know, that would still be fall in the discussion I mentioned before. Because the instances it is trying to solve come from real life and probably have extra structure that allow efficient solution. But you are right, that's one of the things that people naturally do

• 16:18Speaker 00

  when they cannot solve an optimization problem exactly because it's NP complete or NP hard. Maybe I should say NP complete, NP hard problems are those problems in NP that are as hard as all problems in NP. If you solve one efficiently, you solved all efficiently. If you prove one hard, then you proved all of them hard. So they somehow capture the complexity of the class and traveling salesman is an example and protein folding in this framework of energy minimization is one and Boylan's sustainability and so on. Okay, so you want to optimize something and it's NP complete or NP hard.

• 17:05Speaker 00

  So that's a sign that you shouldn't try to find an algorithm that works always. But one thing you can do is do an approximation. That's a very natural relaxation. You don't want the optimum. You are willing to live with a factor of two from optimum or 10% from optimum or some factor away from optimum.

• 17:27Speaker 00

  NP completeness was discovered in the early 70s. In the early 90s, there was a breakthrough called the PCP theorem. The PCP theorem allows you to argue hardness of even approximation problems. So for example, you can show that satisfiability of Boylan formulas.

• 17:51Speaker 00

  You know, it's not just, so you want to, let's say, find an assignment to a bunch of constraints. Let's say, Boulain constraints, let's say, on three variables, for simplicity. So you want to satisfy all of them. The relaxation would be, okay, I want to satisfy ninety percent of them, or as good a fraction as I can, if I cannot get hundred percent of them. The PCPC theorem, one way to phrase it, and suddenly, one of the consequence, major consequence, is that we know that you cannot even achieve a very good approximation. And to illustrate how, you know,

• 18:36Speaker 00

  tight this understanding is for some problems, is that for the example I gave, when there are only three variables per constraint, if you just guess at random the values to the variables in the assignment, you will satisfy seven eighths of the constraint. This is because each particular constraint is usually the disjunction of three variables, will be true with probability, it's an all of three variables, will be true with probability seven eighths. So if you're random, if you don't think, don't look at the formula even, you can satisfy seven eighths of them. And the PCPC theorem, and the significant strengthening by Hester,

• 19:20Speaker 00

  John Hester, tells you that if you want to satisfy seven eighths plus epsilon, that's already NPR. So we know today to argue the difficulty not only of finding the perfect solution, the optimal solution, but even how close to optimal you can get for.

• 19:45Speaker 00

  Lots and lots of problems, large classes of problems, in particular constraint optimization problems, you know, of the type of such fabric.

• 19:55Ryan Peterman?

  So even if you solve just the slightest epsilon, for any trivially small epsilon, it's just as hard as doing the full.

• 20:06Speaker 00

  It's as hard as finding the optimum solution.

• 20:09Ryan Peterman?

  You mentioned NP-hard, NP-complete, NP-EP. I know there's other complexity classes. Maybe you could give some more context on kind of the whole space of complexity classes?

• 20:22Speaker 00

  Yeah, so I just remarked that we have a zoo of complexity classes. In fact, there is a website called, you know, the Complexity Zoo, which has in it hundreds of, hundreds and hundreds of complexity classes of all types. Website started by Scott Aronson, once we realized that, he realized. There's a whole zoo out there, we want to know the relationship between these classes. Okay, so what, what is the point about these classes?

• 20:59Speaker 00

  Like P and NP, we want to classify problems by the amount of resources they take. So P, polynomial time, is a class of problems that can be solved in an amount of time that relates polynomially to the size of the data. Of course, you expect that you're, the data, there's more data, the instance grows, you'll spend more time. But if it's, you know, linear time, or quadratic time, or cubic time, you say, let me call it theoretically efficient. And NP, you classify not the time to solve,

• 21:43Speaker 00

  but the time to verify a solution if it was given. You want this to be a polynomial time. So it's a very different. But first of all, there are, you know, many more time functions than just polynomial and exponential and, and, you know, doubly exponential and you can go to finite and.

• 22:08Speaker 00

  You know, one fundamental result, starting with Turing's paper, is that there are problems that are simply unsolvable by computers. So really, the first complexity class is a class of solvable problems, decidable problems. Turing showed that these are not all problems. There are natural problems that are not decidable at all. But time is only one resource. And we are interested, and you know, both from practical and theoretical reasons, in lots of other resources. Memory is a resource, costly resource, and we want to minimize space. The space is invested in a computation. In problems with several parties,

• 22:50Speaker 00

  you are interested in the amount of communication exchanged. So not the internal computational effort that they exert themselves, but how much, you know, if you talk to a satellite, you want to minimize the communication. You can think about energy, you can think about, yeah, there are plenty of your parallel time, how much can you speed up, you know, the computation of a problem if you work on it not with one computer, but with N computers if your data is of size then? You know, does it, you know, allow it to solve it immediately? Or maybe it doesn't help at all? So there are complexity classes,

• 23:32Speaker 00

  classify problems according to how much resources they need, and there are many of these. And one important part of, so that's a major theme in the methodology of complexity theory. And coming with it is attempts to understand complexity classes as problems that relate to each other, even if you don't know their complexity. So, for example, NP is a class, and we don't know the complexity of all problems in this, or NP complete problems. We don't know whether they are all easy or all hard. But we do know we have efficient algorithms to translate one into the other.

• 24:18Speaker 00

  So it's not obvious that if you want to solve a satisfiability problem, you don't know how, but you have an algorithm to solve Sudoko problems. Not just three by three, but also four by five. If you have an efficient method to solve Sudoko problems, P equals NP, because you can efficiently take an instance of satisfiability or solving salesman or factoring integers or any of these problems, build from it a Sudoko problem. And from the solution of the Sudoko problem, you can translate back and get the best solution

• 25:00Speaker 00

  for your original, I don't know, traveling salesman tool. So we are interested in efficient reductions between problems whose complexity we don't know, but we want to relate them to each other. We build some kind of partial order of the hardness of different problems. So there are, yeah, really, you don't want to know how many problems. We have summarized for constraints that the real world, there may be technology imposes or calls for, and some are naturally arising mathematically because, you know, they are interesting.

• 25:38Ryan Peterman?

  You mentioned that these NP-complete problems, they kind of are all equivalent in some way. What's the proof to equate a SAT-solving problem to like a graph coloring problem or something like that? Are they all similar in nature? Are they kind of bespoke to the problem you're going to and from?

• 25:58Speaker 00

  It's a very good question. And you will find that in most of these, they call them reductions, algorithms to translate one problem to another. Most of them are relatively simple. And not all, and I talked about the P. Cipriano and before, they're showing that approximation is always very highly not trivial. But most NP-completes as proof, like between coloring and satisfiability. And it goes both ways, they are both complete, so it goes both ways. It is simple and... The first one was the satisfiability problem.

• 26:40Speaker 00

  There, you know, original papers of Cook and Levin defining NP completeness and proving that NP complete problems exist. They both, the first problem they proved complete was satisfiability. Why is this? So why can all these other problems be reduced to satisfiability? The reason is really that computation is local.

• 27:09Speaker 00

  Computation is local. I mean that if you think about your computer, your laptop, or any, any computational device, usually it manipulates bits

• 27:20Speaker 00

  by some local operations. You look at this, these two registers and you add them, or you take these two bits and exclusive or them, or end them, or something. And you do a sequence of this, sequence of simple operations, and you arrive at a conclusion. This locality can be translated to a bunch of constraints, or what would be consistent sequence of states of your machine. If you look at the time evolution of any computation, you know, memory is in some states, then in another state, and, but they change locally. Okay, so if you had the, if you could guess, and that's the NP part, I mean, if somebody provided you the table of computation,

• 28:05Speaker 00

  you could check that it's consistent by writing a bunch of local constraints, or, you know, some conjunction of very few variables

• 28:17Speaker 00

  on, all over this table of computation, and write down a satisfiability problem. I want this to be true, and this to be true, and this to be true. For some assignment, and what does the assignment as to satisfy? It should be a table like this. All these constraints should be satisfied, you know, should be true. And...

• 28:40Speaker 00

  It has to be consistent with the input given, right? So some of the inputs has to match the first time zero content of the of the machine. So this locality allows for many of these translations. If you realize this, you will quickly find a reduction from coloring to satisfability. It's also, I mean, it's not clear why coloring is an evolution of computation, but it starts already by local constraints. You want a few colors and that every... So some, in some, it's even easier. But the reduction from any NP computation,

• 29:23Speaker 00

  that's what NP completeness means. Anything in NP can be translated to satisfability. NP is just a computation of a Turing machine, say, only that you don't know what is the computation. If somebody guessed it or showed it to you, then you, all you need is to verify it. This verification is local, and that's a source of many simple NP completeness reductions. Let me, let me give you a really simple example. Why is factoring integers reducible to satisfability?

• 30:06Speaker 00

  Because if I gave you factors of an integer, you could just multiply them and check that they equal the input. This multiplication is a simple algorithm, right? I mean, we know how to do it from second grade or something. You write down the computation of multiplication in this local way. And all you need is that somebody will guess for you really the factors.

• 30:35Ryan Peterman?

  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 like general theory on that, on how these two trade off?

• 30:50Speaker 00

  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. So you can either do it with very small space, like logarithmic space, but you need to pay maybe quadratic time.

• 31:32Speaker 00

  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 for, you know, where you can solve them in linear time and logarithmic space. One very important general result that is a breakthrough from last year is a result of Ryan Williams.

• 32:13Speaker 00

  And 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 will never visit so many cells or registers in your machine. So space is a small thing. Fifty years ago, Valiant, Paul and Pipindro improved this a little bit. They said that if you run in time T, there is an equivalent computation that will do this in slightly less space than T. T over log T. This was a big result. The running time, of course, will blow up.

• 32:56Speaker 00

  It will be very, very expensive time-wise, but at least you can save on space a little bit. And this was believed almost fifty 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'll not describe, you know, this restricted model. But in natural restricted 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

• 33:41Speaker 00

  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 uses an earlier result of James Cook, the son of Steve Cook of NP completeness, and Ian Mertes, that was, you know, an essential technical ingredient. But anyway, you can, you know, 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,

• 34:25Speaker 00

  yeah, the two parameters are related in a highly non-trivial way.

• 34:29Ryan Peterman?

  Is this for a general problem?

• 34:31Speaker 00

  General problem, for Turing machines.

• 34:34Ryan Peterman?

  Okay.

• 34:34Speaker 00

  It may not work on random access machines or...

• 34:37Ryan Peterman?

  What's the trick? If you could explain intuitively, or is it too deep to explain?

• 34:45Speaker 00

  It is, you know, really technically explaining it is too deep. But let me, I'll 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. You say you want to know whether there are more zeros than ones, like the majority problem. Who won the vote, zeros or ones? Okay.

• 35:29Speaker 00

  Well, you can count, you can just add them up, and this takes logarithmic space.

• 35:36Speaker 00

  And it seems that the best you can do, I mean, you want to count up to n, to represent n, takes log n bits, right? I mean, whatever n or the sum, any number between 1 and n, takes log n bits. It seems essential.

• 35:51Speaker 00

  It turns out that there's an algorithm. I have to define exactly how it works.

• 36:00Speaker 00

  I will not define, let me. I will not define exactly how it works. But it solved this problem in constant space. It 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, I want... 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 a... Because everybody is familiar with non-commutative things.

• 36:45Speaker 00

  I mean, we usually put the cart behind the horse and not in front of the horse. It matters. Or in software engineering, we do this before that, or... It's very important, the order of things matter.

• 37:01Speaker 00

  So you can think about...

• 37:06Speaker 00

  Applying permutations one after the other, you know. 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, yeah. Think of all the points as colored by... Yeah, so they don't commute. Baryton is using, you know,

• 37:48Speaker 00

  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-commutativity of this... of these operations allowing to carry out a general formula, a formula of ends and all the knots, you know. Any formula like this, a formula that, let's say, of some size S, it allows him to carry out this computation

• 38:31Speaker 00

  to really simulate the ends and all the knots in this formula by rotations and flips of this, you know, five-sided pentagon. Okay? And so just to remember the configuration of this pentagon, you need, I don't know, 5 bits, right? So you need constant space. How this captures, you know, the computation? I can tell you, you know, one more sentence. Maybe it will not be clear to...

• 39:09Speaker 00

  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. You know, I can... It's too much to describe in words without the bore 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.

• 39:53Speaker 00

  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, doesn't matter which, the picture falls to the floor. How would you loop the string around these nails so that, you know, this happens?

• 40:37Speaker 00

  Clearly, this is an end gate or an all gate, right? If one... yeah. And this has to do... I mean, if anybody finds a solution that realizes what non-commutativity I'm talking about. And yeah, it's a nice riddle. 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, it was a poster. And somebody told me, and I just didn't believe it's possible. I mean, you cannot count how it's already high with it. Yeah.

• 41:22Speaker 00

  So, yeah, so the trick that Cook and Mertz 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:44Ryan Peterman?

  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.

• 41:55Speaker 00

  It is encoded, yeah. Of course, you are not, 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, 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, any size input in constant space. Yeah.

• 42:26Ryan Peterman?

  That's incredible.

• 42:27Speaker 00

  It's pretty, pretty incredible, yeah. And by the way, this is a highly applicable result, using cryptography in a fundamental way. It's useful, yeah, it's used in various places and it's, yeah, 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 yeah, in terms of magic.

• 43:06Ryan Peterman?

  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.

• 43:17Speaker 00

  Yeah.

• 43:18Ryan Peterman?

  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.

• 43:25Speaker 00

  Yeah, you usually also enlarge the instance, usually in translation, you enlarge the instance. So what your question is, why do people use SAT 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. There are very, very clever ways in which you can.

• 44:02Speaker 00

  You know, try, start, I mean, you are not going to guess all the n 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 satisfiability problems if they have such structure. Again, the worst case, it will not help you. There is in fact a conjecture, this is much stronger somehow than NP completeness,

• 44:48Speaker 00

  NP complete problems taking exponential time. It says that we don't expect any savings. We expect satisfiability problems to require really 2 to some constant times n. It's not going to be 2 to the square of n or n to the log n or something like this.

• 45:12Speaker 00

  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, the specifications are usually easily translated into simple constraints, and that's almost a satisfiability problem.

• 45:53Ryan Peterman?

  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?

• 46:10Speaker 00

  In the early 70s,

• 46:14Speaker 00

  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. For example, we had an idea how to test primality of a number. And in the seventies, both Michael Rubin and Solvay and Strassen found probabilistic algorithms which are fast to test primality. Okay, so what does it mean a probabilistic algorithm?

• 46:59Speaker 00

  It's an algorithm that's allowed to make random choices. So you can think that there's an internal, you know, 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. They 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?

• 47:42Speaker 00

  I mean, if you run a probabilistic algorithm of your laptop, since it doesn't have this person inside tossing coins, it does something. Well, high-quality randomness of this type costs money, like time and like memory. What do I mean by costs 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. And all of these things are used. You can do something mathematical, have some simple procedure that is actually deterministic.

• 48:27Speaker 00

  Like a linear congruence generator, something like this, and believe it's random. Or you can take the digits of pi. It's also, you know, looks random in some sense. So there are many things you can use, but you don't know they are random. If you want them to be random, you know, one source, even this is not a perfect source, but we have quantum mechanics. People believe, you know, people believe it works in life. It seems like a cool theory of nature. There are also some arguments about it, but let's put them aside. They predict if you measure photons coming out from some source and you measure their spin, whether it's up or down,

• 49:11Speaker 00

  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 or you have some way of guaranteeing, I mean, you're running it really on your laptop. You're, it's not, you know, okay, the paper was written. We can test primality with a probabilistic algorithm. Now we want to run it, what do you use? So it makes sense to ask lots of questions about randomness, what guarantees the quality of the randomness? And maybe you can minimize the use of randomness. By the way, another issue with randomness

• 49:56Speaker 00

  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. So it's, yeah, it's almost automatic for, if you think like a complexity theorist. How do we minimize for particular algorithm like primality testing?

• 50:42Speaker 00

  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 can... You need N bits, but you can start from square 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, we look as if it was random. If you could do that, you don't need all these bits. You can use much fewer. And this whole theory of, you know, reducing randomness, de-randomization, removing randomness is a huge feat.

• 51:25Speaker 00

  And people are, you know, 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. It'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,

• 52:09Speaker 00

  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 are prime or not. There was no efficient algorithm. Anyway, you can wonder about this Solvay-Sarsen or Aiden algorithm. Maybe you can use less randomness or structures of randomness that you can generate from fewer bits. And nobody has any good idea. And then, in the early 2000s, Agarwal K. Allen Sacksen devised a different probabilistic primality test.

• 52:54Speaker 00

  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 pseudorandom, to generate it 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

• 53:37Speaker 00

  in which the algorithm is using the randomness, understanding the analysis of the algorithm, and saying, okay, it doesn't use all that much.

• 53:48Ryan Peterman?

  You mentioned a few times the quality of the randomness.

• 53:52Speaker 00

  Yeah.

• 53:52Ryan Peterman?

  How do you quantify the quality of random bits?

• 53:56Speaker 00

  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 the, 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 are a set of examples of algorithmic problems

• 54:40Speaker 00

  for which, when you look at the analysis, they are much simpler than this primality testing. When 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

• 54:58Speaker 00

  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 know, you just want to be completely pragmatic. You don't care whether it's random or not. You just care that an observer of a particular structure or a particular computational power will not distinguish the pseudo-random distribution,

• 55:43Speaker 00

  which may have less, much less randomness in it than the perfect one.

• 55:48Ryan Peterman?

  In one of your lectures, actually, you mentioned that and you gave a good example. And I was wondering if you could give the intuitive example of why randomness is a function of the observer's computational power?

• 56:00Speaker 00

  Yeah, so if you watch this talk, you know what. The example I give is an example that's taken from this fundamental paper of Manuel Blum and Sivia Michali. 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. You have to immediately say heads or tails, okay? Before, you have to predict before it falls.

• 56:46Speaker 00

  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 your best answer is, you know, one half, you know, what, how can it help, you know, what can you do?

• 57:05Speaker 00

  The second is when you sit there, but you have a laptop like you have now. And yeah, what can you use? Yeah, I don't know that you can, 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 crazy supercomputer, and the crazy supercomputer is connected to a bunch of sensors and cameras and whatever devices you want. They are all trained on my finger. Okay? And so as it leaves my finger the coin, this apparatus suddenly is more than enough to calculate all the, you know, angular momentum of the coin and the distance to the floor

• 57:50Speaker 00

  and the humidity in the air and whatever parameters that completely determine its motion and 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 coin toss, this coin toss did not change in all of them. It is the same. What, you know,

• 58:21Speaker 00

  masses of people in math and physics and philosophy and, you know, defined randomness in various ways. There are many definitions of randomness, and they all focus on this event, on the coin toss or sequence of coin tosses. We in complexity theory, starting from this paper,

• 58:41Speaker 00

  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 this 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 this completely, and then it's a zero entropy. So what changed is the observer. So the observer is this algorithm we talked about before. And any test that's applied to, you know, to a set of, you know, to a distribution,

• 59:25Speaker 00

  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 the source of many of the important theorems that, you know, show that you can remove, 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. Like if, if you know that something like P is different than NP, or you have a hardware, traveling salesman

• 1:00:10Speaker 00

  is exponentially hard or suscribable. If you know that, then in fact, I can give you a pseudo-random generator that will derandomize any probabilistic algorithm. We know that under this assumption, we have what we call P equals BPP. Anything that has an efficient probabilistic algorithm also has a probabilistic, an efficient deterministic algorithm. You just need to know that there is a hard function somewhere. Under what assumptions do we know P equals the BPP? The assumption, very natural, is that one of these NPR problems,

• 1:00:53Speaker 00

  or in fact, even problems in higher classes, requires a lot of hardware, require exponential size circuits to solve. Okay, we believe that. It's like P versus NP strength. And, you know, you cannot count down the exponential search space. And 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.

• 1:01:37Speaker 00

  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 for some algorithms, if you can do that, then you found a 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 is stronger. But we really know that it's really one of the other.

• 1:02:18Speaker 00

  And since it's hard to believe that all these hard problems are easy, or the similar to the hard problem, like P equals NP, we tend much more to believe the other alternative name is that randomness in algorithms is weak and you can remove it.

• 1:02:33Ryan Peterman?

  OpenAI, Anthropic, Cursor, and Versal 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. You can check them out at workos.com to learn more and get started.

• 1:03:15Ryan Peterman?

  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?

• 1:03:25Speaker 00

  Yeah. Yeah, there is almost always an intuitive explanation for. Yeah, so what's a hard, 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 travelling salesman problem. You don't know the answer, so you, there is some entropy in the answer, right? It's in the same sense we discussed before. There's some entropy, a tiny entropy, maybe exponentially small entropy, because maybe the, you know, if the input is random, maybe only few instances are hard and all the others you can solve.

• 1:04:06Speaker 00

  But at least you see a hint of a relationship between hardness and entropy. This, of course, is not satisfactory, because we want half, we want the, you know, 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. To amplify the hardness. We want not just that some instances will be hard, but that the random instance,

• 1:04:39Speaker 00

  whether the answer is yes or no, for a polynomial time observer, will be half-half. You will not be able to gain an epsilon advantage over a random guess. So for this, there we developed also sort of methods that amplify, amplify randomness. Now, this doesn't solve the problem at all, because I managed to take, you know, 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 from many, a few, one. What you want to do is the opposite.

• 1:05:22Speaker 00

  You want a method that will take a few and will generate many.

• 1:05:28Speaker 00

  Right, that's a pseudo-random generator. Pseudorandom generator starts with a few truly random bits and generates many. And for this, we need, we need other tools. Uh, this is something, uh, that I developed with Norman Son. Uh, it's called today the NW generator. I like to say that, uh, you know, people, uh, 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, allow you to make one million dollars. But once you can make one, there are methods to make many more.

• 1:06:10Speaker 00

  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, uh, your, your limit, uh, you know, limitation of, you know, being running polynomial time. So you cannot solve this hard instance. You build many, many instances from a short seed. You, you start from maybe a logarithmically, uh, long seed. You take many subsets of this, like, N, you will need N of them. And I ask you for the value of the solution to each one. Each one is hard, but we want to say that they are simultaneously hard. You cannot tell them apart.

• 1:06:55Speaker 00

  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. You embed, having a hard problem to a limited observer means that some uncertainty about the answer. That's the key, that's the starting point.

• 1:07:14Ryan Peterman?

  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, uh, maybe infinite compute. Then, then nothing is truly random. Is that, is that accurate to say? Like, you know, if I had infinite compute, I, the weather is not random. Nothing is random?

• 1:07:41Speaker 00

  Uh, okay, so.

• 1:07:44Speaker 00

  It points to the fact that you have to really be careful about what question you are asking about the randomness. If you want, you know, to apply this to probabilistic algorithms, then it's really important that you are limited computationally. So if you have infinite compute times, you will be able to distinguish a distribution with full entropy to the randomness, and one with coming from a generator, or one with low entropy. So you could do that. But one thing you cannot do with the infinite compute is something that's information theoretic.

• 1:08:27Speaker 00

  So there are many other things we need to do with the random bits than just run probabilistic algorithms. For example, we want to generate passwords for our, you know, crypto, you know, for security systems. There, the very demand is that they are random, right? I mean, Shannon theorem tells you, you know, the quality of your password is as good as the entropy in it. So the notion of a secret rests on the randomness, on the true randomness of the... So if I just ask you to produce a random bit,

• 1:09:10Speaker 00

  or you ask me to produce a random bit, you know, whether you have a computational, infinite computational power or not, doesn't matter. I 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. This, you know, then this definition or this task of producing randomness is not related to your computational power.

• 1:09:45Speaker 00

  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 pseudorandomness. But if your very demand is to have a random event, then you need to produce a random event.

• 1:10:08Ryan Peterman?

  I saw in, when I was doing my research, that there are ways to create higher-quality randomness by aggregating weaker sources.

• 1:10:19Speaker 00

  Yeah.

• 1:10:20Ryan Peterman?

  How does that work?

• 1:10:22Speaker 00

  Well, it's another theory. I talked before about the theory of pseudorandomness. It's a whole different theory. They are related in nontrivial ways, but it's called the theory of randomness extraction and/or randomness purification, maybe. And this is exactly what we 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? Otherwise, the market will be... But these are not, you know,

• 1:11:06Speaker 00

  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 likely, more likely to be hot than cold.

• 1:11:33Speaker 00

  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 of, we don't know.

• 1:11:59Speaker 00

  So it has some entropy in it, but you have no idea where. I 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.

• 1:12:41Speaker 00

  And you want to use it in a probabilistic algorithm. So 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 this 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, let's say.

• 1:13:14Speaker 00

  But the theory of randomness purification wants to take this,

• 1:13:21Speaker 00

  this sample of n bits resolved with some amount of entropy which is not full, and someone massages it, create from it maybe a shorter string, which is, you know, of higher quality. Ideally, it would be perfect random bit. So 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.

• 1:13:55Speaker 00

  Bits that will be essentially uniformly distributed. Then if I have an algorithm that just needs this amount, that's what I feed it. It's not easy, you cannot do that. It's impossible. But what you can do is not produce one string of length, let's say square of 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 any distribution with entropy in it. And you produce many blocks, polynomially many blocks,

• 1:14:39Speaker 00

  of the length roughly the entropy, what you would hope to be perfect. And 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's already solved 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, you know, various assumptions you can make about the entropy. Maybe you have several weak sources

• 1:15:23Speaker 00

  that are not related to each other. There are various, yeah, the various variants. And this theory is very well developed. But we know that the statement I made essentially is accurate. If 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. So that's as useful as having one, yeah.

• 1:15:56Ryan Peterman?

  I vaguely remember skimming a bunch of papers. And one of the papers, it had this, had this figure where it was two dimensional array of numbers. And I think they were like drawing rectangles or something like that. Is that like one of the ideas?

• 1:16:11Speaker 00

  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're referring to is this sum product theorem, this.

• 1:16:40Speaker 00

  Yeah, I cannot draw the pictures of there, but you don't really need to. So let's just think about this problem. You have

• 1:16:50Speaker 00

  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 in 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, how, what combination of weak sources would you take? It's not obvious. And the solution, yeah, this is the, certainly there is, maybe you mean this one. There's a paper I have with Barak and Impariato about this particular problem.

• 1:17:31Speaker 00

  And we are using a result in what's called the arithmetic combinatorics. And I can explain it very simply. I think that we learn about addition in second grade and about multiplication in third grade, maybe. And, you know, the only motivation for multiplication is that it's a way to shortcut repeated addition. And that's all we talk about. Then if you go to college, you, you learn that, you know, sum and product 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 on. So you remember, these are the basic operations. But how do they relate to each other?

• 1:18:18Speaker 00

  It's not clear. It's not... Maybe there are many ways to ask this question. But one way to ask this question that was suggested by Erdes and was solved the first time by Erdes and Semeride, and then in a much more... in the form we really need by Bourguen, Katzen, Tao, says the following: "Just 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. Yeah. So you have k integers. Well, it depends what they are. I mean, if they are the first k integers,

• 1:19:03Speaker 00

  and you add all pairs up, you get just the number between 1 and 2k. That's not much larger. That's a factor of 2 larger. If you want to increase in entropy, you want to get, you know, 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. You 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 grow. 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.

• 1:19:48Speaker 00

  If you take, you know, 1, 2, 4, 8, you take a geometric progression, you multiply all pairs, you will just get just twice as many as you start from. So that's also not good. And the magic in this 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:21Speaker 00

  And 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 sum and 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 a source of. You need to prove it distributionally. It's not just the size. The entropy is not just size.

• 1:21:06Speaker 00

  Over the size, it's more than that. But 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:20Ryan Peterman?

  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? And maybe we talk about its significance.

• 1:21:30Speaker 00

  Sure, yeah. Zero knowledge proof, it's pretty amazing that it became a household word. 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 Gold, Vassar, Michali and Rakoff, which also contains 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. People can have a discussion, a randomized discussion in which I try to convince you of something.

• 1:22:12Speaker 00

  I want to prove to you something like I know the, you know, the proof of the Riemann hypothesis, or I can solve this Sudoku puzzle. We can do it interactively with the random. We are randomized, in particular, are 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. There is 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 Baba, parallel in the same time from different motivations.

• 1:22:57Speaker 00

  Basically, it offers a generalization of the notion of NP.

• 1:23:03Speaker 00

  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, you know, a small chance, because you are randomized, we allow a small chance that you will, you know, 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. Yeah, anyway, so there's a notion of an interactive proof. And then, in the Gold, Wasser, Michalij, Rakov paper, they suggested another notion of interactive proof, which is more restricted.

• 1:23:46Speaker 00

  You 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 any knowledge, any new thing they didn't know. Say, what are you talking about? This, such proofs don't exist for anything. There's no zero knowledge for anything.

• 1:24:24Speaker 00

  They were not thinking about, you know, convincing someone of, you know, political opinion. They were thinking about cryptography, of course. You know, they've created the foundation of cryptography in many, in many other papers.

• 1:24:41Speaker 00

  But they are imagining cryptographic protocols in which you have secrets and you, 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, a public key by multiplying two prime numbers. If you multiply three... Or something else. Then you're violating the protocol and maybe security is not guaranteed.

• 1:25:25Speaker 00

  So 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 multipurpose computation, very complex things.

• 1:26:06Speaker 00

  They are competing 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, you know, applications to this idea. The only problem is that it sounds ridiculous because it sounds impossible. In mathematics terms, if, you know, somebody came here and said that P, you know, they proved P different than NP, you know, I would want to see the proof. And then they 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,

• 1:26:51Speaker 00

  amazed by them. And nevertheless, I know absolutely nothing about the way they proved it. I just know that they did. This story, it really sounds ridiculous. And, yeah, certainly one of my favorite papers, maybe my favorite, is this zero knowledge paper which came a year later. It's joined with Odette Goldreich and Silvio Micheli, 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 NP, or that I multiply two primes,

• 1:27:35Speaker 00

  or anything that you can prove, revealing your secret, you can prove without revealing your secret and convinced beyond any reasonable doubt. So that's possible.

• 1:27:46Ryan Peterman?

  What's the intuition behind that? Like, let's say I have a proof for P equals NP and we want to convert it to a zero-knowledge proof. How does that work?

• 1:27:55Speaker 00

  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 factors or integers, or this bit logarithm, or any number of one-way, believed one-way functions exist. 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 an inverse problem, the prime factor, is believed to be hard. Of course, we never, we can never, we don't know any hard problems. That's a previous NP question. We don't know.

• 1:28:39Speaker 00

  But we believe about many problems and the belief is actually, the whole world believes, 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. One-way 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. I can write down another number.

• 1:29:21Speaker 00

  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. Okay. And this commitment scheme, which is built very simply for one-way 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 the... So I can later provide you with a certificate that I was thinking about 17. And I can only do it for 17.

• 1:30:05Speaker 00

  I cannot do it for any other number. Okay. In fact, a very simple example is really using factoring. In some sense, the product of two primes, this number,

• 1:30:20Speaker 00

  you know, it's easy. Yeah. This number commits to its factors. It uniquely defines its factors. Right? The only problem is this is not exactly random product of primes. Yeah, but you can do it, so you can do this. Okay. So now, that we have to take commitments are possible. That's very important.

• 1:30:45Speaker 00

  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 the high level, I'll give you some idea about how a zero-knowledge proof looks like. Now, 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 a graph. We can color it in three colors.

• 1:31:28Speaker 00

  It's also a formal mathematical statement, either it's doable or not, right? And we want, we simply focus on proving in zero-knowledge claims of this type. Okay? 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. Yeah, it should be an interactive proof. And moreover, we want it. I want it to be zero knowledge. I don't want you to have a slightest idea of what my coloring is or what anything you didn't know before is. Okay, so roughly the way it works.

• 1:32:10Speaker 00

  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 tell you, you know, I don't tell you it's green or red or blue, but I put a commitment to one of them on each vertex. You will choose a random and edge of the graph and ask me to open these two envelopes to decommit.

• 1:32:53Speaker 00

  And you will check that the colors you see, first of all, are in this set. They are not gray or orange. They are either red, green, or blue, and that they are different.

• 1:33:04Speaker 00

  This should give you some, maybe slight, you know, 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 or other. Yeah. So we have to establish two things. We will repeat this again and again. We have to establish that it's, you know, that it's a proof. It's an interactive proof that I cannot cheat you. And we have to argue that zero knowledge part. Okay, so let's do one at a time.

• 1:33:42Speaker 00

  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 is one place which is an arrow. Either it has the wrong color, and not allowed 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 your graph on, you know, with hundreds of edges, it's one in a hundred, if thousands, it's a... If we repeat it not thousand, but 10,000 times, the probability that you don't catch me in any of them drops exponentially to zero.

• 1:34:26Speaker 00

  Right, so, of course, there's a... Okay, so this establishes that I cannot fool you. The zero knowledge is a more serious problem, because if I keep using the same coloring, you will ask me about this edge and this edge, and then eventually you'll know the coloring of all colors. Here is something that's really special to the coloring that is being used. If I have one coloring of the graph, I already have six, because I can produce the names, 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,

• 1:35:11Speaker 00

  but using a random one of these possible six. They are legal, they are all legal, and I just use one of these six. What'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.

• 1:35:43Speaker 00

  What happens when I reveal to you two of these colors on adjacent vertices of the graph? It will be true, in this distribution, when you are restricted to two vertices, it will simply be two different random colors, right? This is what you get by all permutations, this six permutations. What 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, that showing you that there are zero knowledge proofs

• 1:36:27Speaker 00

  for all graph coloring, three coloring problems. What about all the Riemann hypothesis and the P-VS NP and factoring, all these other things I want to claim to you and prove with 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, right? This is the definition. So you reduce it to three coloring, 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,

• 1:37:11Speaker 00

  but actually, if you have a witness, if you have a proof for, I don't know, whatever, 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 instance, as you solve it for any, you can prove anything in zero knowledge.

• 1:37:47Ryan Peterman?

  So with the zero knowledge proofs, you can never be 100% sure?

• 1:37:53Speaker 00

  No, no.

• 1:37:53Ryan Peterman?

  Okay, but... Practically, I mean exponentially approaching.

• 1:37:57Speaker 00

  You can make the completeness 100%, namely, if I do have a proof, you will be, yeah, there will be no error in your. But there is a slight possibility that the graph is not three-coloring, not three-colorable, and you will not catch me. You can make this exponentially small. You cannot make it zero.

• 1:38:18Ryan Peterman?

  When I think of cryptography, one-way functions, there's this idea of quantum computation that's kind of changed complexity theory a bit.

• 1:38:28Speaker 00

  A bit, yeah, big time, yeah.

• 1:38:30Ryan Peterman?

  Yeah, and I wanted to ask your thoughts on, you know, how quantum computation or that model of computation is changing complexity theory? Like, what are the big takeaways?

• 1:38:42Speaker 00

  OK, let me say what it is first of all. I mean, yeah, quantum mechanics is a theory of nature that, you know, seems to be, everybody believes and accepts. So like with randomness, we can ask why not enhance computers with, you know, this physical knowledge? We allow our computers to operate in the, you know, ways that quantum mechanics dictates, namely manipulate bits in superposition using unitary operations, whatever this means, but, you know, according to the rules of quantum mechanics. And really strange things happen in quantum mechanics.

• 1:39:25Speaker 00

  I'm sure many, many people know because, you know, you can, there are all these interference patterns. Yeah, it seems that, you know, you can, you know, basically you are working with probability theory with negative numbers. Events cannot, you know, aggregate only, they can cancel each other. And, OK, so it's a model of computation. It's a generalization of Turing machines. In fact, it's a generalization of randomized Turing machine. 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.

• 1:40:10Speaker 00

  You measure them, this is what I mentioned about the photons in the beginning. If you have some basic superposition on, I mean, a quantum, quantum bit, if you measure it, you get a random bit. So 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 eighties, Feynman and Mannin and others suggested, you know, letting algorithms use these quantum mechanical operations, mainly originally for just simulating

• 1:40:52Speaker 00

  quantum systems, rather than building big apparatus to, 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 quantum algorithm. Can they do more than efficient classical ones, deterministic or probabilistic? And 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 ninety-four, Peter Shaw sort of, yeah, created an earthquake or an avalanche.

• 1:41:33Speaker 00

  He found quantum algorithms that are efficient, that factor integers, and also compute discrete logarithms, the two most basic underpinnings of our security systems that exist. And this set the world on fire, right? So lots of people tried to do a lot of things. Of course, you know, people want to have them, these algorithms they implement, maybe they want to break or other people skip the system. So as you know, since then, billions were invested by companies, by governments, by lots of people trying to, to build the technological infrastructure.

• 1:42:18Speaker 00

  And this is extremely complicated. Holding bits in superposition is extremely complicated. There's things that are called the, there's 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

• 1:42:51Speaker 00

  classical computers that have errors, noise, that have to cope with errors. Some of their components can be faulty. But this today's hardware, you know, has no errors to speak of. We don't, I mean, there are error correcting mechanisms, but we don't need them for classical computing. Intel chips don't have, you know, I think, error correction in them. Hardware is very reliable. When you move to quantum, there is the coherence noise. It's in quantum mechanics, everything depends on everything. The world can influence the computation in your laptop. And protecting from this is very hard.

• 1:43:33Speaker 00

  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 and there are many hard technological issues and there's progress 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 factoring algorithms in algorithm in polynomial time, I think there'll be chaos in the world. Because nobody, nobody can do any transactions. Because most security systems still rely on factoring.

• 1:44:20Speaker 00

  And so, of course, we want to change this, we want to change the underlying assumptions of security. We want to rely. The whole revolution in cryptography was that we rescue cryptography on computationally hard assumptions. And with this, we build all the wonderful public key systems and Yeah, all the magical things you can do with the under by assuming that players are computationally limited. But now if the adversaries are quantum computers, certainly they can break this assumption.

• 1:45:01Speaker 00

  You want to find other mathematical problems, computational problems, which are somehow hard even to quantum computers. So that's a 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. You make an omelet from an egg, you know, reversing this is, yeah, doesn't take the same amount of time.

• 1:45:44Speaker 00

  That's a usual example of a physical one-way function. But treptal 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, ITI and Wark created this, another type of treptal function from problems on lattices in high dimensions. I will not describe it, but it's another problem and the people refined and got a few more similar of similar nature. And it turned out, when Peter Shaw discovered this,

• 1:46:28Speaker 00

  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 in exponential space. But Fourier transform you can do somehow with quantum computers, with interferons. 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:13Speaker 00

  So there is no even theory. Forget building quantum computers, we don't know how to solve them. And so, what the world is not just complexity theory, the whole physical world of, you know, security systems, and also governments like the NSA, you know, is, you know, supporting or, you know, asking the world to produce assumptions that may be resilient to quantum attacks. And so this is a huge change. There is a major change in the interaction between computer scientists and physicists, which grew tremendously since this discovery.

• 1:47:56Speaker 00

  And it's reached in many, many ways that are not, the influence of the algorithmic thinking of, on, on physical theories, including today, theories in quantum gravity, black holes, and so, is immense. And, you know, we have new sources of problems, a new model, a new complexity classes, et cetera, et cetera. And there is a fantastic, fantastic interaction. And it's also enriched complexity theory in that it turns out that you can discover quantum algorithms and maybe then de-quantize them.

• 1:48:38Speaker 00

  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. And the interactive proofs I mentioned before, turns out that even before quantum, they were generalized to interactive proofs, not with one proverb, but with many provers, which seem to be, you know, weird,

• 1:49:21Speaker 00

  but turns out to be very important in itself because it led to this PCP theorem. Then people said, okay, let's allow quantum verifies, 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. M I P star equal R E. You may have seen it, maybe you didn't. And it looks weird, but I'll tell you what it says, really. It says that there is a weird, really weird proof system with quantum provers that, you know, trying to convince verifies, an efficient verifier.

• 1:50:06Speaker 00

  And it turns out, you know, you ask for which problems can they do it? Forget the order, just convince. And it turns out they can do it for the whole thing 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, you know, ridiculous. Things that are uncomputable by any, any classifiable algorithm are verifiable in this interactive probabilistic sense by efficient verifier.

• 1:50:51Speaker 00

  So 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 complexity theorists, 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 you get, once you're weird enough, you get weird enough, you know, consequences. So one message, which I think is very powerful, is that this result has absolutely fundamental impact on mathematics.

• 1:51:30Speaker 00

  It turns out that it implies, and this was already done in the initial paper, it implies resolution of well-known conjectures in mathematics. It 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, you see, the impact is many generations over with, for different motivations and developments,

• 1:52:15Speaker 00

  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? This type of proof technique is now being explored and used, and there are more results, you know, using this type of techniques to longstanding problems. Pretty amazing.

• 1:52:45Ryan Peterman?

  That's incredible, yeah. I mean, in complexity theory, you know, there's these... What do you call them? I guess like Venn diagrams of all possible problems. And you know, the implicit assumption in this picture is that these are these are decidable problems.

• 1:53:02Speaker 00

  Yeah, yeah, yeah, yeah.

• 1:53:03Ryan Peterman?

  In some of these diagrams, there's a little in the corner, there's a

• 1:53:07Speaker 00

  Undecidable.

• 1:53:08Ryan Peterman?

  Undecidable ones.

• 1:53:09Speaker 00

  Unreachable, yeah.

• 1:53:10Ryan Peterman?

  Right, and it's just, I can't, I don't even understand how you could verify an undecidable.

• 1:53:19Speaker 00

  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. It's, you know, it's a huge body of work. And on top of this, all this 200-page paper, in which they have to develop many more tools. And yeah, there you have it.

• 1:53:59Ryan Peterman?

  I mean, when someone produces 200 pages of such complicated work that makes such an outrageous claim, how, how does that get verified by people?

• 1:54:12Speaker 00

  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 P-verse NP and the Riemann hypothesis 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:42Speaker 00

  And but others like, you know, the Perlman proof of the Poncaré conjecture, one of the Clay millennium problem, million dollar problem, was another one like that. And this took several years to verify and fix small bugs in and, you know, books exposing this proof were written and eventually. This particular paper is, for some reason, still in the referring stages in the analysis 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 statement

• 1:55:24Speaker 00

  and stronger statements in order to resolve other mathematical conjectures. But yeah, it's a serious thing. And in fact, the original paper had a bug. Like the original paper with Fermat by Weil's Fermat's last theorem also had a bug and was fixed. And this was fixed. This was very early on, just when it came out very quickly fixed. So it's any mathematical claim, you know, your question is very important for. In general, mathematics and mathematical truth is a social construct. It was mathematicians' belief.

• 1:56:06Speaker 00

  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:25Ryan Peterman?

  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?

• 1:56:39Speaker 00

  Well, I think the theory of computer science, my field, complexity theory, algorithms, this 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.

• 1:57:06Speaker 00

  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. So 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

• 1:57:42Speaker 00

  and continuous spaces, right? 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, you know? And this can be, you know, a sequence of bits, or it can be, you know, the DNA of a person, which is being, you know, you know, from which you produce proteins using computation, or you produce a new baby using the evolution of, you know, a fertilized egg, or the weather, or, you know, so computation is sort of everywhere.

• 1:58:27Speaker 00

  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, you know, understand the algorithms that are underlying natural phenomena, so. So we live in both spaces. We have a lot of input of problems and models from, you know, industry, technology, systems, and so on. And we have all the mathematics that is, you know, so we have the rigorous side coming from, and the aesthetic side, I would say, you know, like creating models

• 1:59:12Speaker 00

  or proof systems, because they are nice, because they are interesting, because, you know, not because they are implementable necessarily. So this, living in these two spaces,

• 1:59:26Speaker 00

  you know, is extremely beneficial to this theory of computation.

• 1:59:32Ryan Peterman?

  You mentioned earlier that some people might have the perspective of complexity theory, that it's kind of solving problems for problems' 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?

• 1:59:54Speaker 00

  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, where there are models of, you know, adversarial distributed computation. There are many... I think modeling, just asking questions, is, you know, and creating, making definitions,

• 2:00:38Speaker 00

  is a very central part of the field. And it happens more than in mathematics, maybe because they are more ancient than maybe definitions happen earlier. But I want to stress this, that's a very important thing. For example, we discuss randomness, and our definition of randomness is totally different, and it gives rise to, you know, very, you know, surprising and interesting, practically, theories. Okay, now that we said that, what motivates me, or what motivates other people? Of course, everybody has their own motivation. I am a product of computer science education. I...

• 2:01:21Speaker 00

  all my undergrad and grad school and postdoc and everything were in computer science. So I think that I... I suddenly 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, you know, different systems and different issues. There are, of course, algorithms in databases and algorithms in, you know, programming languages and, in fact, famous algorithms. In other, other fields, there are models and algorithms.

• 2:02:05Speaker 00

  So computation is something that I am interested intrinsically. I'm more, over the years, realizing this computation, you know, the field expanded to interact with all the sciences and that computation happened everywhere in various forms, in physics and biology and so on. You know, 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.

• 2:02:34Speaker 00

  I know from just experience that lots of the CRM's we prove, not many, but probably with much higher proportions than in other areas of math, are impactful in, you know, in the world, in real systems, in security systems, in blockchains, in the real world. But that, this side, this particular side of

• 2:03:00Speaker 00

  seeing exactly how you translate your algorithm into, you know, into a system or your, you know, the zero knowledge proof. I, 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, 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, so on. Doesn't seem that anybody would ever use such a thing. But, yeah, I was wrong. I mean, I, yeah, I didn't realize how motivated people can be and how important applications of zero knowledge

• 2:03:42Speaker 00

  can be in the real world, not in theory of protocol design. And they did simplify, maybe other, using more assumptions, uh, different assumptions. There's a recent breakthrough of a postdoc here, I was, Elango, 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 gather theorem, that something is unprovable in some.

• 2:04:17Speaker 00

  Yeah, mathematical proof system like Thoreau-Frank, whatever mathematicians use. Somehow using that, they can get zero knowledge that's non-interactive. You can get, 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 forty-five years of experience of this, working in this field, which have been fascinating. 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

• 2:05:01Speaker 00

  and young brilliant minds are entering the field all the time, but also very lively and interactive and collaborative and, you know, just, yeah, many of my best friends are also colleagues, so 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, Shaw's work on quantum algorithms, you can say, "Why do that?

• 2:05:45Speaker 00

  There are no quantum computers. Maybe that's why somebody built ones 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 forty years ago, but suddenly clear now, that all, you know, that...

• 2:06:11Speaker 00

  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. There are many, many other examples besides crypton and quantum, including theory and, you know, the field of revolutionized coding theory, mainly because of the PC PC or tools needed for. So, you know, there are lots of examples and this eventually went into systems, you know, for memory schemes or whatever.

• 2:06:54Speaker 00

  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, in the years that have been at it. We are not much closer to showing howness for anything. We don't know that multiplication is harder than addition. It's a basic question.

• 2:07:19Speaker 00

  So, this kind of question by itself is certainly not practical. I mean, it's not clear, but 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.

• 2:08:04Speaker 00

  This basic methodology of the field that created some wonderful edifice. And I would say that we are still in the embryo stage of understanding computation.

• 2:08:16Ryan Peterman?

  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.

• 2:08:38Speaker 00

  Yeah.

• 2:08:38Ryan Peterman?

  You know, where you make a major.

• 2:08:39Speaker 00

  Sometimes.

• 2:08:40Ryan Peterman?

  Because a lot of people's careers, like maybe, you know, if you're just the engineer, you just, you got your shipping projects every year. But in your case, like, let's say you, imagine you discovered P equals F P or something like that. Yeah, like, how do you feel when you make those discoveries, those sparse discoveries in your career?

• 2:09:02Speaker 00

  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 ants work. I mean, most progress, we have these conferences, theory conferences, Stock and Fox, and then we have all sorts of, you know, satellite conferences, and there are hundreds of papers in them. Satellite, I mean, focused on a concrete area and learning theory, crypto, I don't know, online algorithms. You see, 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:47Speaker 00

  And 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 problem. 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 the bigger understandings come more rarely. And they suddenly, you know, they, they send this shockwave to everybody, learns them and, and uses them. But of course, you know, those bigger understandings, it doesn't have to be a resolution of 50 years old paper, it can be something that.

• 2:10:29Speaker 00

  You know, when Barington discovered his algorithm for counting that I mentioned, he was trying to actually prove that it's impossible. And it was not like somebody asked this question. 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.

• 2:11:12Speaker 00

  But yeah, 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. You go in the morning, you come back in the evening, and you fail to do what you wanted to do. You just couldn't, you just thought more and yeah. And I think that it's really important. So it's not for everybody. Clearly, it's not satisfying if you, you know, this happens every day and every week and, you know. It's not for everybody, but you know,

• 2:11:55Speaker 00

  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. So unless you enjoy this activity, maybe this field is not for you. And yeah, and then you see something, and that's even if it's small, sometimes it's very satisfactory.

• 2:12:31Ryan Peterman?

  Last question for you, and I think, you know, people in the field might be curious because you have so much experience. If you could go back to the beginning of your career, when you just started, you know, becoming a researcher, is there any advice that you'd give yourself?

• 2:12:48Speaker 00

  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, you know, there's no hierarchies. People would go to conferences and meet... I remember my first conference meeting, Dickapu was, you know, he goes in the field and invented, you know, did all these NP complete things. I was a first year graduate student, and somebody introduced me to him, and immediately asked me what I'm doing.

• 2:13:30Speaker 00

  And I said I proved that some problem was NP complete, and he was actually interested. He 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 early stages is to work on things they enjoy the most.

• 2:14:15Speaker 00

  So when you are discovering your talents as a researcher, one direction may be, you know, these are all problems, if you solve them, then you... But maybe that's not your problem. 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. 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:48Ryan Peterman?

  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 Liskoff, Mike Stonebreaker, Mark Booker, 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. This is in the case. 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.

• 2:15:31Ryan Peterman?

  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.