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

Episode Date: June 1, 2026

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-zeroThank 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) OutroWhere to find Avi:• Wikipedia: https://en.wikipedia.org/wiki/Avi_Wigderson• Personal Website: https://www.math.ias.edu/avi/homeWhere 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/@ryanlpetermanReferenced 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

If tomorrow somebody finds even a classical factory algorithm in polynomial time, I think there will be chaos in the world. This is Avi Wigderson, Turing Award and Abel Prize winner, and I interviewed him all about his field. The question of P versus MP 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 does not all they can do it for the whole thing's problem, for problems that are not computable. There's to more somebody finds an efficient algorithm for an NP complete problem. You know, what do you do? Here's the full episode. 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? 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. So we would like to somehow classify those problems that we can solve, to know what we can know. 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. 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 really want to solve, whether we can know everything we want to know. This is basically about the limits of our knowledge. Of course, I have to justify why, you know, these classes which are mathematically defined actually

are captured by this intuitive meanings 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 our problems you see in our apps in our phones, like if there's a navigation app, it means somebody invented an algorithm that's efficient enough to solve any, you know, shortest path problem 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, 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 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? Certainly 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, so that's what you're 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 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, so on. Anyway, if an engineer designed something, whoever gave them their task and looked at it and say, well, you violated some constraints, or no, it's good.

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 we know from detective books, you know, they eventually provide them. So these are examples of very fundamental human endeavors that encompass almost everything I can think of. In all of them, what people are searching for,

have 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, and PR laws that we can solve. Whether they are equal, you know, if they are equal, then everything we want to know, cure for cancer, anything you imagine can be, you know, just the very fact that 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. human knowledge. 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.

I can imagine you could prove that they're equivalent. You could also prove that they're not. If you had to guess when an if a proof comes, which direction would your intuition say it goes and why? I think that my intuition

and that's probably hard 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 are not that's convincing. One is the intuition that most of us have that, you know, finding something is really hard and just checking that it's there. if you lost your keys or your phone and you have no idea what to look, but if somebody points out, oh, you left it on the windowsill or something like this, yes, ah, yeah, I did. 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, 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 people try to solve for completely egocentric reasons to make their company richer or to and there are thousands of these and they have manifest themselves in many different forms and so over the maybe 50 60 70 years people seriously looked for algorithms for these very different

ones and couldn't find any. This may seem like there's 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 large space, like all the possible possible you know, solutions to some system of equations, for example. And somehow, P versus NP is about having a general method for cutting down this exponentially research space into searching over something much smaller in a clever way. And this should 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 an NP-complete problems, using some new idea that nobody ever thought of, you know, what do you do? That would change the world. In software engineering, we use. algorithms all the time and they often have these very satisfying properties where the solution you know 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 Am I understanding that correctly? Yeah, you're understanding perfectly correctly. I think that maybe what you are getting at is that NP-complete problems, a particular NP-complete problem is really a family of instances, right?

I mean, you want to find a Hamiltonian tool, some traveling settlement tools through some map. You know, there's this map and that map, and this network and other network, and 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 corrects on all of them.

In software engineering and many aspects of optimization, in many real-world problems, the instances is a much more restricted set. you know, they come from 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, our 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.

And this kind of optimization problem, one can easily prove, is NPR. And nevertheless, our body faults our proteins all the time, you know, 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, 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, or at least in verification and testing, you often want to check that something meets the specifications. you usually translate it into a satisfiability question of Boulin formulas. The formulas that you get, the instances that you get out of these, have some structure, and maybe for them, various greedy approaches or clever, not just greedy,

but clever but efficient methods work. In other words, it's making it short. Instances that 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. 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 structure that allow this particular algorithm to solve them efficiently. Of course, today we know an algorithm that's efficient for all in our programs, but it's much more complicated and people don't, or I don't know, how much it's used in practice. the simplex muscles is a very simple to run and yeah usually it works you mentioned the protein folding and i mean yeah that's an interesting one because it's it's an np problem but it was solved to an acceptable extent and when i was reading about it it it wasn't solved for a hundred of cases. It provides a solution and a confidence score, but it doesn't give you the answer 100%

accurate, 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? Yeah, it's a very natural and good problem. So in the, in the protein folding you were talking about alpha fold, I guess, which is an algorithm that was learned from existing proteins and is working very well on instances it didn't see, but are still proteins coming from the body. Even if it did perfectly on these, not just, you know, that would still be for in the discussion I mentioned before, because the instances it is striking.

to sort 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 when they cannot solve an optimization problem exactly because it's NP-complete or NP-hard. Maybe I should say NP-complete-n-Hart problems are those problems in N-P that are as hard as all problems in N-P. If you sold 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 salesmen is an example, and putting folding in this framework of energy minimization is one, and bullion's sustainability and so on. Okay, so you want to optimize something, and it's NP-complete or NP-HARD. 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. NP completeness was discovered in the early 70s. In the early 90s, there was a breakthrough called the PCP, The PCPCOM allows you to argue hardness of even approximation problems. So for example, you can show that the satisfiability of Boulin formulas, you know, it's not

just, so you want to, let's say, find an assignment to a bunch of constraints, let's say, Boulin constraints, let's say on three variables for simple. So we want to satisfy all of them. The relaxation would be, okay, I want to satisfy 90% of them or as good a fraction as I can if I cannot get 100% of them. The PCPCO, and one way to phrase it, and certainly one of the consequence, major consequence, is that we know that you cannot even achieve a very good approximation. And to illustrate how 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 constraints. This is because each particular constraint is usually the disjunction of three variables. be true with probabilities and all will be with probability 7.8. So if you're random, if you don't think, don't look at the formula even, you can satisfy 7.8s of them. And the PCPCEO and the significant strengthening by Hustard, J. John Hustad, tells you that if you want to satisfy 7.8 plus epsilon, that's already

the 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 lots and lots of problems, large classes of problems, in particular, constraint optimization problems, you know, of the type of such fabric. So even if you solve just the slightest epsilon, for any trivially small epsilon, it's just as hard as doing the full. It's just as hard as finding the optimum. You mentioned MP hard, NP Complete, NPP. I know there's other complexity classes.

Maybe you could give some more context on kind of the whole space of complexity classes. Yeah. So I just remark that we have a zoo of complexity classes. In fact, there is a website called the Complexity Zoo, which has in it hundreds of, hundreds and hundreds of complexity classes of all types of websites 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 is the point about these classes? 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 the data, there is more data, the instance goes, you'll spend more time. But if it's linear time or quadaltic time or cubic time, you say, let me call it theoretically efficient.

And NB, you classify not the time to solve, 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 many more time functions that are just polynomial and exponential and are doubly exponential and you can go to finite. And one fundamental result starting with the Turing's paper is that there are problems that are simply unsolvable by computers. So really the first complexity class is the class of solving this.

problems, decidable problems, to ensure 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 both from practical 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. problems with several parties you're interested in the amount of communication exchange. 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 a, you know, computation of a problem, if you work on it, not with one computer, but with N computers if your data is of size, then does it allow it to solve it immediately, or maybe it doesn't help at all? So there are complexity classes 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, MP 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 hard. But we do know we have efficient algorithms to translate one into the other. 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 Suduqa problems, not just 3 by 3, but also 4x.

If you had an efficient method to solve Suduco problems, P equals NP, because you can efficiently take an instance of satisfactorily or traveling salesmen or factoring integers or any of these problems, be it from a Sudoku problem, and from the solution of the Sudoku problem, you can translate back and get the best solution for your original, I don't know, traveling settlement too. 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, maybe technology imposes or calls for, and some are naturally arising mathematically because, you know, they are interesting. You mentioned 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 or they kind of bespoke to the problem you're going to and from? 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 Psypithio and before, showing that approximation is all this is 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.

The 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. It's local, I mean that if you think about your computer, your laptop, or any computational device,

usually it manipulate bits by some local operations. You look at these two registers and you add them or you take this two bits and exclusive all them or end them or something. And you will 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 will 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 and in another state, but they change locally. Okay, so if you could guess, and that's the NP part,

I mean, if somebody provided you the table of computation, you could check that it's consistent by writing a bunch of local constraints or some conjunction of very few variables all over this table of computation and write down a certifiability problem. I want this to be true, this to be true and this to be true. For some assignment, and what is the assignment does to satisfy? should be a table like this, all these concerns should be satisfied, you know, should be true,

and it has to be consistent with the input given, right? So some of the input has to match the first times zero content 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 satisfy 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 in some, it's even easier, but the reduction from any NP computation, that's what NP completeness means.

Anything in NP can be translated to certifiability. 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 all you need is to verify it. This verification is local, and that's a source of many simple MP completeness reductions.

Let me give you a really simple example. Why is fact? fracturing integers reducible to certifiability. 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. 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? Yeah, yeah, we have, yeah, all these questions are answer our 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, like logarithmic space, but you need to pay maybe quadratic time. And if you want linear time, you have to pay linear space or close to linear space. There are results of this type in various models of computation. That's another thing you play with. Not all of them are, you know, they are all equivalent in principle,

but if you care about exact time or exact space, they are not equivalent. So there are problems for which there is a trade of, there are problems for, you know, where you can solve them in linear time and logarithmic space. One very important general result that is the breakthrough from last year is a result of Ryan Williams. And I'll tell you what it is, but I 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'll never visit so many cells or registers in your machine.

So space is at most time. Fifty years ago, Vali and Paul and PPDO, 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 locked T. That was a big result. The running time, of course, will blow up. It will be very, very expensive time-wise, but at least you can save on space a little bit.

And this was believed almost 50 years to be the best you can do. In fact, we had arguments that in certain models, in certain stylized models of computation, you cannot improve that. I'll not describe, you know, this restricted models, but in some way, 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 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 empty completeness,

and Ian Merth, 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 you're the sense that yeah there are the two parameters are related in a highly non-trivial way is this for a general problem or general problem and for chewing machines okay they may not work on random-access machines or yeah what's the the trick if you could explain intuitively or is it too deep to

explain and it is it is It's really technically explaining it, it's too deep. But 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 zero than ones, like the majority problem. Who wants the vote? Zero the ones. Okay. Well, you can count, you can just add them up, and this takes logarithmic space. And it seems as best you can do. I mean, you want to count up to n to represent and takes log in bits, right? I mean, whatever N or the sum, any number between one and takes log and b.

It seems essential. It turns out that there's an algorithm. I have to define exactly how it works. I will not define, let me. I'm 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. 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-communitative algebra. You use something, you know,

Non-commutative algebra is not a big thing. Everybody's familiar with non-commutative things. I mean, we usually put the cars behind the horse and not in front of the horse. It matters. Or in software engineering, we do this before that. It's very important. The order of things matter.

So you can think about applying permutations, one after the other, 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 a point in a circle. You 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 that if I first rotated and, yeah, think of all the points

are colored by. Yeah, so they don't commute. Barrington is using, you know, he's somehow encoding the bits in the input by permutations, not large permutations, permutations of size 5. And somehow when he sees a 1,

he maybe rotates and when he sees a 0, he flips. And the non-communativity of this of these operations, allowing to carry out a general formula, a formula of ends and ores and knots. Any formula like this, a formula that, let's say, of some size S,

it allows him to carry out this computation to really simulate the ends and all the knots in this form. formula by rotations and flips of this, you know, five-sided pentagon. So just to remember the configuration of this pentagon, you need, I don't know, five bits. So you need constant space. How this captures the computation, I can tell you know one more sentence, maybe it will not be

clear to everybody, but these non-commuting things, you can do the following type of operation. Do rotate, do flip, then rotate back, and flip back. This is called the commutator, and it can simulate an end gate. It's too much to describe in words without 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 endgade problem. You want to hang a painting in the following way. You have a painting, it says a string.

connecting the two sides, but you want to hang it not on one nail, but on two nails. Okay, there are two nails on the wall, and you can do with the string whatever you want. And the purpose you want is that if the two nails are there, it's hanging, everybody's happy. If you pull out one nail, it doesn't matter which the picture falls to the floor. How would you loop the string around these nails so that this happens? Clearly this is an end gate or an or gate, right? If one, yeah. And this has to do, I mean, if anybody finds a solution that realize what non-communativity

I'm talking about. And yeah, it's a nice feel. Anyway, so this type of trick where you can really, this type of result, you can really do, do in small space things you wouldn't imagine possible. It's a striking example. It's really, when I heard this result, first time I was the poster, somebody told me

and I just didn't believe it's possible. I mean, you cannot count arbitrarily high with the cook. So the trick that Cook and Merits having 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. So if you're counting arbitrarily large, that is information.

And you're saying, like, maybe the intuition is that information's encoded in the sequence of operations. It is encoded, yeah. Of course, you are not delivering the final count. You just say whether there are more zeros than ones. If you have to write down, of course you need, if the answer takes some number of bits long, then you need this number to write it down.

If you have a decision problem, say like yes or no, like are there more zero than ones, then you can do it for any size input in a concert space. Yeah. That's incredible. It's pretty incredible, yeah. And by the way, this is a highly applicable result, it's used in cryptography in a fundamental ways.

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 so is magic. We talked about the equivalence between these MP-complete problems. And then I know in practice a lot of people to solve the other problems, they just use SAT solvers. Yeah. I would have thought that would be less efficient, though, because you've got to kind of translate it and then you're doing it in almost like a different problem space. Yeah, you usually also enlarge. the instance, usually in translation, you allow the instance. So what your question is, why do people use cell servers?

I would say that there's no problem other than satisfactorability 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 try, start. I mean, you are not going to guess all the end bits, but you want to start by guessing some bits that seem more pivotal that if you, like in dominoes, maybe when you set them to one value, they force many other values to be set. And if that happens, you cut down your cell space.

So there are many heuristics of this type and also more clever than this that allow to solve such liability problems if they have such structure. Again, the worst case will not help you. There is in fact a conjecture. It's a much stronger some of the NP completeness, you know, NP-complete problems taking exponential time. It says that we don't expect any savings. We expect satisfiability problems to require really true to some constant times end. It's not going to be true to the scrote and or

end to the Logan or something like this. So yeah. So 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 are usually, the specification are usually easily translated into simple

constraints and that's almost a susceptibility problem. We talked about all the different types of resources and an algorithm and in one of your talks you said something where you consider randomness another resource for an algorithm.

What do you mean when you say randomness is a resource for an algorithm? In the early 70s of course randomized algorithms existed since antiquity and everybody was tossing 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 have computers, people realize that it can really enhance all sorts of computation. For example, we had no idea how to test primality of a number. and in the 70s, both Michael Rabin and Solve and Strassen found probabilistic algorithms which are fast to test primality. Okay, so what does it mean a probabilistic algorithm? 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 this 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? I mean, if you run a probabilistic algorithm of your laptop, since it doesn't have this person inside the tossing coins, it does something. Well, high-quality randomness of this type costs money, like time and like memory. What do I mean by cost money? You can have a very cheap solution.

You can just, I don't know, measure the thermal noise in your computer or have one of the Intel chips. you know, you can measure internet traffic and sample it and believe it's random. And all of these things are used. You can do something mathematical. They have some simple procedure that is actually deterministic

like a linear congruence generator, something like this, and believe it's random. Or you can take the digits of pi. It'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 all sorts of 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, The prediction is that each one is half half and it's independent of each other. That's very nice, but if you are going to build this device, it's going to cost you a lot of money. And let alone that it will not be perfect, but let's leave this aside.

Anyway, since you want high-quality randomness, you have some way of guaranteeing. I mean, you're running it really on your laptop. It's not, 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, why it guarantees the quality of the randomness,

and maybe you can minimize there is the use of randomness. By the way, another issue with randomness is that 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 the amount of this resource we have to invest or the number of which we have to invest,

their quality and so on. So it's almost automatic for, if you think like a complexity theory. How do we minimize it? For particular, algorithm like primality testing. You know, do you really need this? Do you need them to be independent?

Maybe you can generate them in a, you know, maybe you can, you need n-bits, but you can start from scrolls n-bits or from log n-bits that are truly random and make from them in some deterministic way, you know, 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 this, but you can use much fewer. And this whole theory of, you know, reducing randomness, de-randomization, removing randomness is a youth field.

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 complex, theoretic way you can, you know, back in his days, hundreds of years ago,

and maybe 150, I don't know, He was asking for an indefatigable calculator. Calculator, of course, is a person, but he wanted this to be efficient. That's basically what he was looking for, a priority test for large numbers, because they really wanted to know about numbers, maybe only a few tens of digits.

They wanted to know whether they were prime or not. There was no efficient algorithm. Anyway, you can wonder about the survey source, or a Raman algorithm, maybe you can use less randomness or structures randomness that you can generate from fewer bits, and nobody has any good idea. And then in the early 2000, Agarwal, Kayaan and Saxana, divides a different probabilistic primality test.

And it's different, so the analysis of randomness in it is different. And once you understand how randomness is used, you can maybe say, ah, we don't need to be really totally independent bits. It's okay if it has some structure. And then they found using number theoretic ways, a method to generate this pseudo-randomly, 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 in which the algorithm is using the randomness, understanding the analysis of the algorithm, and saying, okay, it doesn't use all that much. You mentioned a few times the quality of the randomness. How do you quantify the quality of random bits? This is basically a question about what's through the randomness 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 full this algorithm, you want this algorithm, not to notice that you switch from perfect randomness to something that's really far less randomness, has far less entropy, but the analysis works nonetheless. Another algorithm, maybe you need a completely different type of pseudo-randomeless for it. There are a set of examples of algorithmic problems 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 tripper. And spaces of random variables which have this property are much smaller. You can generate them from log-end bits. And so you can fool them with this.

So the quality of randomness, this is a phrase I like, that 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 test. that are applied to it. 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 particular computational power will not distinguish the pseudo-random distribution, which may have much less randomness in it, than the perfect one. In one of your lectures, actually, you mentioned that and you gave a good example.

And I was wondering if you could give the the intuitive example of why randomness is a function of the observer's computational power? Yeah, so if you watch this talk, you know, the example I give is an example that's taken from this fundamental paper of Manuel Blum and Sylvia Mikali. They tell you to consider three experiments. And the experiments go and follows. They're always between you and me, you are the observer, I am the corner. 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 days, okay? Before, you have to predict before it falls. Well, this is the first experiment and what I ask and what they ask, you know, what do you think is a success, your success, what is. are your chances of predicting it. And the obvious answer is, you know, one half, you know, how can it help? You know, what can you do? The second is when you sit there, but you have a laptop like you have now. And, yeah, what can you, yeah, I don't know 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, a Kray supercomputer, and the Kray 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 certainly is more than enough to calculate all the, you know, angular momentum of the coin and the distance to the floor and the humidity

in the air and whatever parameters that... completely determine its motion, in particular, how it will land in a split second, far less than the time needed to. So the real point in this example is that the experiment, the random coin toss, this coin toss, did not change in all of them. It is the same. You know, masses of people in math and physics and philosophy, and defined randomness in various ways.

There are many definitions of randomness. And they all focus on this event, on the chronicles or a sequence of chronotosis. We in complexity theory, starting from this paper, don't care about this event. 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 it completely,

and then it has 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 distribution, to test the quality of randomness, depending on the test, you want to just make sure you want to use this little true randomness in a way that the observer will not notice.

And this is a source of many of the important theorems that show that you can remove randomness or reduce randomness. in probabilistic algorithms with or without assumptions and really are behind this understanding that we have today. Randomness in algorithms is not as powerful as we thought it is. Like if you know that something like P is different than NP

or you have a hardware, traveling salesman is exponentially hard or satisfibrative, if you know that, then in fact I can give you a pseudo-random generator or that will de-randomize any probabilistic algorithms. We know that under this assumption, we have what we call P equals BPP. Anything that has an efficient probabilistic algorithm also has an efficient deterministic algorithm.

You just need to know that there is a hard function somewhere. Under what assumptions do we know P equals BPP? The assumption, the very nice, is that one of these NPR problems, or in fact even problems in higher classes, requires a lot of hardware, require exponential size circuits to solve. We believe that. It's like P versus NPR strength and you can not cut down the exponential search space. And so maybe people are, you know, happy.

with this assumption, but this assumption about time complexity, it has no randomness in it. It's sort of, as first, it's shocking that it's actually related to the problem of removing randomness from algorithms. So that's one fundamental connection, this hardness versus randomness paradigm. But we know even more. We know that it goes both ways. We know that if you're trying to remove randomness for some algorithms, if you can do that, then you found the hard function.

So there's really an almost, it's not an exact if or if, but again, and there are many variants of this in some variants, if an only if it's stronger. But we really know that it's really one of the other. And since it's hard to believe that all these hard problems are easy or the similely hard problem like p equals np, we tend much more to believe the other alternative, namely that randomness in algorithms is weak and you can remove it. Open AI, 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 ARBAC, 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. And I appreciate them for supporting my work and sponsoring this podcast. Is there an intuitive explanation for the relationship between problem hardness and randomness? Yeah. Yeah, there's almost always an intuitive explanation. Yeah. So what's a hard problem?

I give you the input. You are a limited computer. You are a polynomial time algorithm. I give you the input, let's say it's a traveling settlement problem. You don't know the answer. So there is some entropy in the answer, right? It says in the same sense we discussed before. There's some entropy, tiny entropy, maybe exponentially small entropy because maybe the input is random, maybe only few instances are hard and all the others you can solve. But at least you see a hint of a relationship between hardness and entropy. This, of course, is not a fact story because we want the, you know,

we want that for you, the answer will be like a corintose, not like a very biased corinthos. So we need to find ways to amplify this uncertainty for you. They amplify the hardness. We want not just that some instances will be hard, but since the random instance, whether the answer is yes or no,

for a polynomial time observer, will be half-half. It will not be able to gain an epsilon advantage over a random guess. So for this, there we developed all sorts of methods that amplify randomness. Now, this doesn't solve the problem at all because I managed to take, you know, NB,

it's a random instance of a problem and manufacture one beat, that's hard for you to guess. Well, I could have taken the first random bit I picked for there. So I generate for many, a few, one. What you want to do is the opposite. You want a method that will take a few and will generate many. That's just through the random generator. Through the random generator starts with you,

truly random bits and generates many. For this we need other tools. This is something that I developed with non-Nissan, because today the NW generator. I like to say that people say that making the first million dollars is easy and afterwards you can make many more millions. You can think of it this way. The hardness in the way I described is allow you to make $1 million.

dollars. But once you can make one, there are methods to make many more, and in fact, more than the number of bits you started with. But still, their quality depends on the hardness of the function you use. We still use this. And your limitation of being running in polynomial time. So you cannot solve this hard instance. You build many, many instances from a short seed. You start from maybe a logarithmically long seed. You take many subsets of this, like N, you need N of them. And I ask you for the value of the solution to each one.

Each one is hard, but you want to say that they are simultaneously hard. You cannot tell them apart. There is no correlation you can detect between them, even though they are extremely correlated. So, yeah, so we have methods to do that as well. So that's the connection. You embed, having a hard problem to a limited observer means there's some uncertainty about the answer.

That's the key. That's a starting point. So when you say that the quality of the randomness is a function of the computational power of the observer, one thought that comes to mind is, imagine I have maybe infinite compute, then nothing is truly random. Is that accurate to say?

If I had infinite compute, the weather is not random, nothing is random. Okay. So it points to the fact that you have to really be careful about what question you're asking about the randomness. If you want to apply this to probabilistic algorithms, then it's really important that you are limitless computationally. So if you have infinite compute times, you will be able to distinguish a distribution with full entropy to the randomness, and one is coming from a generator, one with low entropy.

So you could do that, but one thing you cannot do with infinite compute is something that's information theoretic. So there are many other things we need to do with the random. bits than just run probabilistic algorithms. For example, we want to generate passwords for our, you know, crypto-s, you know, for security systems. The very demand is that they are random, right? I mean, Shannon's theorem tells you, you know,

the quality of your passports is as good as the entropy in it. So, the notion of a secret rests on the... randomness, the true randomness of the... So if I just ask you to produce a random beat, or you ask me to produce a random bit, 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 tests. You really want the probability of heads to be half, It tells to be half. This, you know, then this definition or this task of producing randomness is not related to your computational power. So, you know, lucky or unlucky, I don't know, for us, many times we do have implicit or explicit tests for this randomness. You say, I can break this, you know, I can break this system or something, and then you can,

maybe use pseudo-randomness. But if your very demand is to have a random event, then you need to produce a random event. I saw when I was doing my research that there are ways to create higher-quality randomness by aggregating weaker sources. How does that work? Well, it's another theory.

I talked before about the theory of pseudo-randomness. There's a whole different theory. They are related in non-trivial ways, but it's called the theory of randomness extraction or randomness purification maybe. And this is exactly what 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 stock prices, right?

Otherwise the market will be. But these are not, even though these are unpredictable events, they are somewhat predictable. I mean the weather tomorrow is more likely to be similar to the weather today than the opposite of the world. So there are correlations. If you sample this weather, for example. There are also biases. I mean, sometimes you know, in the spring it's more.

Or in the summer, it's more likely to be hot than caught. So there are biases correlations. These are called weak random sources, and there's a mathematical quantification of how a week 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, you know. 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 coronetosis, and you don't know which half. Maybe there are each, you know, half, three quarters, zero and one quarter of, you know, head 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 or n-bits which has some entropy, let's say, square out of n. You don't know well. And you want to use it in a probabilistic algorithm. So it's a basic question. Can we use physical events, which sources coming from nature maybe, in probabilistic algorithms? And certainly not obvious. I mean, just feeding them to the algorithm as is, it's 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. We'll always make an error lately. But the theory of randomness purification wants to take this sample of n-bits with some amount of entropy, which is not full. And someone massage it, create from it maybe a shorter string, which is, you know, of higher quality. Ideally, it will be perfect random bits.

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, bits that will be essentially uniformly distributed. Then if I have an algorithm that just need this amount, that's what I feel it. It turns out you cannot do that.

It's impossible. But what you can do is not produce one string of length, let's say, square of ten, but you can produce n to the hundred of them. Okay? And what you are guaranteed, so this is this randomness purification device. It's an efficient algorithm that takes any distribution with entropy in it, and you produce many blocks, polynomially many blocks,

of the length roughly the entropy, what you would hope to be perfect, and what you are guaranteed is that 99% of them are truly perfect. perfect. So you have many. Ninety-nine percent of them are as good as perfect, and there's one percent 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

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. I vaguely remember skimming a bunch of papers, and one of the papers I had this figure where it was two-dimensional array of numbers, and I think they were drawing rectangles or something like that. Is that like one of the ideas? So it's a notion of pseudo-randomness,

which is related to one particular variant of this extraction problem where you have several weak sources, not one. One is the hardest because that's, yeah. But maybe you have a few that are independent and each of them has some entropy in it.

And I think what you are referring to is this some products here on this, yeah, I cannot draw the pictures of there, but you don't really need to. So let's just think about this problem. and you have three sources of randomness. There are each week, so each has just a little bit of entropy in it. And all you want to produce is one source with somewhat larger entropy.

So you are losing the number of sources, but you are gaining entropy. If you can repeat this, you eventually get to full entropy. So that's the idea. So what combination of which sources would you take? It's not obvious. And the solution, yeah, this is, suddenly there is, maybe you mean this one, there's a paper I have with Barak and Impaliato

about this particular problem, 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, third grade maybe. maybe, and the only motivation for multiplication is that it's a way to shortcut, a repeated addition.

And that's all we talk about. Then if you go to college, you learn that sum and products are the basic operations of fields. You can do it with integers, you can do it with rational numbers, complex numbers, finite fields, and so. So you remember, these are the basic operations. How do they relate to each other? It's not clear. Maybe there are many ways to ask this question.

But one way to ask this question that was suggested by Erdash and was solved the first time by Erdash and Semarady and then in a much more in a form we really need by Bougain-Catentau say 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.

So you have K integers. Well, it depends what they are. I mean, if there are the first K integers and you add all pairs up, you get the number between 1 and 2K. That's not much louder. That's a factor too louder. If you want to increase in entropy, you want to go. get, you know, some power of K bigger than one.

Of course, if you take a random set of integers, you'll get k-square. They'll all be distinct. You get k-square integers. So somehow you want to say, I mean, it would be great if for any set, when you take all pairs, you grew. But it's not true by this example of the interval. Well, you can not take sums. You can take products.

Okay, but also products don't always increase. If you take, you know, one, two, four, eight, you take a geometric progression, you multiply all pairs, you just get just twice as many as you start. So that's also not good. And the magic in the sum products here, I mean, 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.

And so this is an amazing result. And the way you use it in this context, you think of the outcome of your sources and numbers. You, let's say, multiply the first pair and add them to the third. You mix the sum in product. So this guarantees, even this is not obvious, but. If you do this, it guarantees that you grow the number of different values you get is significantly more than K, maybe it's K to the 1.5 or something. Entropy does increase, and that's the source of, you need to prove it distributionally,

it's not just the size, the entropy is not just size. Lower the size, it's more than that. But anyway, this is behind one solution to one of the problem. about clarification, it does not solve the one-source problem. This, you need other tools. I saw that you had done some work in zero-knowledge proofs. I just wonder if you could explain, you know, what is a zero-knowledge proof?

Maybe we talk about its significance. Sure, yeah. Zero-knowledge-proof, it's pretty amazing that it became a household world. I mean, it was in the domain of theorists for a long time. The original definition of zero-knowledge proof came in a paper, a seminal paper of Goldwasser, Mikali, and Rakoff, which also contained the definition of interactive proof. So even before zero-knowledge, they conceived of the notion that proofs don't have to be written down like in mathematical papers.

People can have a discussion, a randomized discussion in which I try to convince you of something. I want to prove to you something like I know the proof of the Riemann hypothesis or I can solve this Sudoku puzzle. We can do it interactively with the random. We are randomized, in particular you, the verifier of my claim are allowed to be randomized. So it's like in randomized algorithms, but now the proofer is a proofer. It's not just an algorithm. It's a provver like in NPR, 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 Babai, parallel in the same time from different motivations. Basically it offers a generalization of the notion of NP. NP is just when I send you a message and it convinces you, you verify it and it convinces you. Now we allow an interaction and we allow, 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 arrow can be reduced, like in probabilistic algorithms, can be reduced arbitrarily. You want one in a billion, you can get one in a billion, whatever. Anyway, so there's a notion of an interactive proof. And then in the Golwasser Mikali-Rakshi, of paper, they suggested another notion of interactive proof, which is more restricted. 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 knowledge, any new things they didn't know. Say, what are you talking about? Such proofs don't exist for anything. There's no zero knowledge for anything. They were not thinking about convincing someone of political opinion.

They were thinking about cryptography, of course. They have created the foundation of cryptography in many other papers. But they are imagining cryptographic protocols in which you have secrets, and you use these secrets in your computation, and you have, you know, the protocol tells you to do things that if you don't, then, you know, you're violating the protocol, so the others don't want you to cheat. They want to make sure you perform the right operations on your secrets. For example, you are supposed to pick a public key by multiplying two prime numbers.

If you multiply three or something else, then you are violating the protocol and maybe security is not guaranteed. 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. And you can think about lots of other cryptographic protocols where people are doing it. things like multipartic computation, very complex things, they are confusing with their secrets,

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

And nevertheless, I know absolutely nothing about the way they proved it. I just know that they did. This story really sounds ridiculous. And, yeah, certainly one of my favorite papers, maybe my favorite, is a zero-knowledge paper, which came a year later, this joint with Odellar, and Sylvia Mikali, 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-nology entire. actually proof, anything, like P different than NMP, or that I multiply two points, or anything that you can prove revealing your secret, you can prove without revealing your secrets, and convinced beyond any reasonable doubt. So that's possible. 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? How does this work? First of all, it assumes cryptography. We assume we have some one-way functions. We assume that some problem like factor integers or this with 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 the inverse problem, the primary. factor is believed to be hard. Of course, we don't know any hard problems. That's a P-1-NP question. We don't know.

But we believe about many problems. The belief is actually the whole world belief, 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. The only 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 100. I can write down another number, which looks like a random number to you. And on the one hand, you have no idea. I claim this encodes my secret. And this commitment scheme, which is built very simply for more than re-functiones, 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.

I cannot do it for any other number. In fact, a very simple example is really using factoring. In some sense, the product of two primes, this number, you know, it's easy. This number commits. to its factors, it uniquely defines its factors. The only problem is this is not exactly random products of prime. But you can do, so you can do this. Okay.

So now that we have to take commitments are possible. That's very important. So I'm describing very high level. I'm hiding lots of things. And even the definition of zero knowledge, the formal definition is quite intricate. The intuition is obvious, and I said it, but actually formally defining is not trivial. But at a high level, I'll give you some idea about how a zero-nose 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 the graph, we can color it in three colors. It's also a formal mathematical statement, either it's doable or not, right? And we simply focus on proving in zero knowledge claims of this type. 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... should be an interactive proof, and moreover, I wanted 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, zero-knowledge proof for this particular set of claims that are certainly not all claims. They are very structured claims. We look like the following. we iteratively repeat the following procedure. I put commitments for the coloring on every vertex. I don't tell you it's green, red, or blue,

but I put a commitment to one of them on each vertex. You will choose that random and edge of the graph and ask me to open these two envelopes. to decommit. And you will check that the colors you see, first of all are in this set, they are not gray or orange, they are either red, green, or blue,

and that they are different. This should give you some, maybe slight advantage or slight support to the belief that maybe I'm not cheating you. Of course, it's a very limited one because I can cheat you in some corner, other, yeah.

So we have to establish two things. We will repeat this again and again. We have to establish that it's a proof, it's an interactive proof, that I cannot cheat you, and we have to argue that zero knowledge part. Okay, so let's do one at the time. To do the correctness that I cannot fool you is very simple, it's the following.

If the graph is not three-colourable, whatever I commit for, there is one place which is an arrow. Either it has a wrong color and not a loud color or two colors are equal. You have some non-trivial chance of catching this with your random guess, right? I mean, it's one over the number of edges. It's not so small. You should a graph with 100 edges, it's one in 100, if thousands and something. If we repeat it not 1,000 but 10,000 times, the probability that you don't catch me in any of them

drops exponentially to zero. Right. So, of course, there's a... 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 eventually you'll know the coloring of all colors.

Here's something that's really special to the coloring that is being used. If I have one coloring of the graph, I really have six, because I can per-bute the name that I can replace red and green, and it's another valid coloring. So what I do really in each one of these iterations is not using the same coloring, but using a random one of this possible six. 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 zero. So if I do know the solution, the proof, I want to protect my knowledge. What happens when I revealed to you two of these colors on adjacent vertices of the graph? It will be true. In this distribution, when you were 60 to two vertices, it would simply be two different random colors.

This is what you guess by all permutations, this is six permutation. 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 that there are zero knowledge proofs for all graph coloring, three coloring problems. What about all the Riemann hypothesis and the P-VAS MPN, factoring, all these other things I want to claim to you and prove with zero-narrulage? 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. This is the definition. So you reduce it to three-calorie. Prove it in zero knowledge. And the main point about reductions in NP is that they don't only convert the yes-no answer

in a consistent way, that if this is solvable, this is solvable. But actually, if you have a witness, if you have a proof for, I don't know, whatever, 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 translation not just between the instances, but also between the proof.

So NP-completeness theory gives you for free that if you solve the problem for graph, Graph coloring, instance, as you solve it for any, you can prove anything in zero knowledge. So with the zero knowledge proofs, you can never be 100% sure. No, no. Okay, but practically, I mean, exponentially approaching. You can make the completeness 100%, namely if I do have a proof, you will be, yeah, there'll be no error in your... But there is a slight possibility that the graph is not three coloring. It's not the caliber and you will not catch me.

You can make this exponentially small. You cannot make it zero. When I think of cryptography, one-way functions, there's this idea of quantum computation that's kind of changed complexity theory a bit. And... A big time, yeah. 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? Okay, 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 according to the rules of quantum mechanics. And really strange things happen in quantum mechanics, I'm sure many people know, because there are all these interference patterns. It seems that you can... Basically, you are working with probability theory with negative numbers. Events cannot aggregate only.

They can cancel each other. And okay, so it's a model of computation. It's a generalization of during machines. In fact, the generalization of randomized tool 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. You measure them, this is what I mentioned about the photons in the beginning. If you have some basic superposition on, I mean, 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 80s, Feynman and Manin and others suggested, you know, letting algorithms use this quantum mechanical operations, mainly originally for just simulating quantum systems rather than building bigger apparatus to, yeah, like we simulate other things, turbulent, I don't know. What's the power of quantum algorithms? Again, let's say running in polynomial time. or efficient quantum algorithms?

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 1994, Peter Shaw sort of, created an earthquake or an avalanche. He found quantum,

algorithms that are efficient, there's fractal integers, and also compute discrete logarithm. The two most basic underpinnings of all security systems that exist. And this sets the world on fire, right? So lots of people try to do a lot of things. Of course, you know, people want to have them. These algorithms they implement, 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 a lot of people trying to build the technological infrastructure. And this is extremely complicated.

Holding beats in superposition is extremely complicated. There's things that are called the noise. I mean, when people build classical computers like von 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, it built a nice theory of 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, I think, error correction in them. Hardware is very reliable. When you move to quantum, there is this decoherence 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. There are quantum error correcting codes, and that's part of the solutions.

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, forget quantum computers. If tomorrow, I mean really tomorrow, somebody, find even a classical factoring algorithms in polynomial time, I think there will be chaos

in the world because nobody can do any transactions because most security systems still rely on factoring. And so, of course, we want to change the underlying assumptions of security. We want to rely. The whole revolution in cryptography was the that we arrest cryptography on computationally hard assumptions. And with this, we build all the wonderful public key systems and all the magical things you can do with the... by assuming that players are computational limited. But now if the adversaries are quantum computers,

suddenly they can break this assumption. You want to find other mathematical problems, computational problems, which are somehow hard even to quantum computers. So that's 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, you know, doesn't take the same amount of time. That's the usual example of a physical one function. But trapdoor functions like factoring, problems from which you can build public key systems, and that's the most really basic thing for electronic commerce, are for few. We don't know many, so we know this, I mentioned, fact, in Discrete Log. In the 90s, ITI and work created this another type of structural function from problems on lattes in high

dimensions. I will not describe it, but it's another problem and that people refined and got a few more similar of similar nature. And it turned out when Peter Scholl discovered this, people immediately try 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 in exponential space,

but Fourier transform you can do somehow with quantum computers, with interference. The lattice 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. So there's no even theory. Forget building random 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 is supporting or asking the world to produce assumptions that may be resilient to quantum attacks. And so this is a huge change.

This is a major change in the interaction between computer scientists and physicists, which grew tremendously since its discovery. and it's rich in many, many ways that are not, the influence of the algorithmic thinking on physical theories, including today theories in quantum gravity, black holes and so, is immense. And we have new sources of problems, a new models, a new complexity class, et cetera, et cetera. And there's a fantastic interaction. And it's also in rich complexity theory in that it turns out that you can discover quantum algorithms

and maybe then de quantize them. In special cases, like I mentioned factoring before, de-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, it turns out that even before quantum,

they were generalized to interactive proofs, not with one pover, but with many povers, which seem to be weird, but turns out to be very important. itself because it led to this PCP theorem. Then people said, okay, let's allow quantum verifiers, quantum provers, and see what they can. So one amazing result, which is about five years ago, is the acronyms. Of course, we have acronyms for all these complexity classes. It's MIP star equal RE. You may have seen it, maybe you didn't.

And it looks weird, but I'll tell you what it says, really. It says that there is a weird, really weird, proof system with quantum proofers that, you know, are trying to convince verifiers, an efficient verifier. And it turns out, you know, you ask for which problems can they do it? Forget the only, just convince. And it turns out they can do it for the halting problem, for problems that are not computable. Things that are not computable are verifiable by efficient verifiers if the proofers 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 classical curriculum are verifiable in this interactive probabilistic sense by efficient verifier. 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 theories, you play in your sandbox and you build all these sandcasters and make up all these models that have nothing to do with anything just because you can and you get, once you 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 math and physics. It turns out that it implies, and this was already done in the initial paper, it implies resolution of well-known conjectures in math and physics. It turns out that, you know, weird as it is, it's a new mathematical technique to solve problems that nobody had any idea. They're 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 questions.

You see, the impact is many generations over for different motivations and developments. But all of them following the methodology of complexity theory, of understanding the power of computational models, proof systems, and so on, has magically led to such a consequence. And this is just the, we are in the beginning of this, right? This type of proof technique is now being explored and used, and there are more results using this type of techniques to long-standing problems.

Pretty amazing. That's incredible, yeah. I mean, in complexity theory, there's these, what do you call them, I guess like Venn diagrams of all possible problems. And, you know, the implicit assumption in this picture is that these are, these are decidable problems. Yeah, yeah, yeah, yeah, yeah. In some of these diagrams, there's a little, in the corner,

there's a undecidable ones. Unreachable, yeah. Right, and it's just, I can't. I don't even understand how you could verify an undecidable. It's a 200-page paper. It builds on 10 years of understanding, which is both a lot of development in the quantum algorithms and quantum proof systems sphere,

but also relying on techniques from classical proof systems, which have to do with coding theory and various algebraic stuff that is used to prove, for example, the PCP C.O.m. As I mentioned, it's a huge body of work. And on top of this, all this 200-paced paper, in which they have to develop many more tools. And, yeah, there you have it. Wow. I mean, when someone produces 200 pages of such complicated work that makes such an outrageous claim, how does that get verified by people?

It's a very good question. This tool for any mathematical result that is complicated. And of course you know that, of course, proofs of Pivas and P. and Riemann hypotheses are generated very frequently, but some of them were generated by very serious people and took a long time to refute in these two cases. But others like the Perlman proof of the Poncarre conjecture, one of the clay millennium problem, a million dollar problem, was another one like that,

and this took several years to verify and fix small bucks in and books exposing this proof were written and eventually. This particular paper is for some reason still in the referring stages in the annals of mathematics, now probably almost six years. 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 and stronger statements in order to resolve other mathematical conjecture. But yeah, it's a serious thing, and in fact the original paper had the bug, like the original paper with Fermat by Wiles.

from us last year, and also had a bug and it was fixed. And this was fixed. This was very early on, just when it came out very quickly fixed. So it's, any mathematical claim, you know, your question is very important for. In general, mathematics is a mathematical truth, is a social construct. It's what mathematicians believe. Maybe we are moving into a world in which we have linked. 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. In complexity theory, it's very mathematical in nature when I read the papers, but obviously it has implications in computer science. What's the relationship between math and computer science to you? Well, I think the theory of computer science, my field, complexity theory algorithms, 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. 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, partly 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.

In analysis, you are trying to understand, very generally speaking, inequalities and continuous spaces. So there are these notions you are trying to understand. Computation is one of these notions. You are trying to understand what can you produce by an evolution of simple local steps to a given environment, the input. This can be a sequence of bits, or it can be the DNA of a person, which is being, you know, from which you produce proteins using computation, or you produce a new baby using the evolution of, you know, fertilized egg,

or the weather, or, you know, so computation is sort of everywhere. and we are trying to understand it in ways that are different. We care about resources, how much resources are exerted in any such computation and trying to model it, try to understand the algorithms that they underline natural phenomena. 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,

we have the rigorous side coming from, and the aesthetic side, I would say, you know, like creating models of proof systems because they are nice, because they are interesting, because, yeah, not because they are implementable necessarily. So this, living in these two spaces, you know, is extremely beneficial to this theory of composition. 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. Okay, so let me say one thing about your, So 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. There are models of adversely and distributors computation. There are many, I think modeling, just asking questions, is, you know, and creating, making definitions, is a very central part of the field. And it happens more than in mathematics, maybe because they are more ancient than maybe definitions happen earlier.

But I want to stress this. That's a very important thing. For example, we discussed randomness, and our definition of randomness is totally different, and it gives rise to very surprising and interesting practically theorems. Okay, now that we sell that, what motivates me or what motivates other people, of course, everybody has their own motivation. I am a product of computer science education. all my undergrad and grad school and post-talk and everything were in computer science.

So I think that 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 programming languages and, in fact, famous algorithms.

In other fields, the models and algorithms. So computation is something that I'm interested intrinsically. I'm more interested, over the years, realizing that computation, you know, the field expanded to interact with all the sciences and that computation happen everywhere in various forms, in physics and biology and so on, makes it a fundamental object of study.

And for me, given the way I was brought up, I guess, a particular is fascinating in itself. I know from just experience that a lot of the CRMs, we prove, not many, but probably with much higher proportions than in other areas of mass, are impactful in, you know, in the world, in real systems, in security systems, in blockchain, in the real world.

But this side, this particular side of seeing exactly how you translate your algorithm into a system or your zero-knowledge proof. I predicted when we came up with the zero-knowledge proof that it will never be implemented. Because the protocol that I described more or less to you is very, very, costly. I mean, you want to prove that I'm producing a product of two primes and I convert it to a map and then I do all this complicated procedure many times. So it doesn't seem that anybody would ever use such a thing. But I was wrong. I mean, I didn't realize how motivated people can be and how important applications of their

knowledge can be in the real world, not in theory of protocol design. And they did simplify, Maybe are they using more assumptions, different assumptions. There's a recent breakthrough of a postdoc here, Raoul, Ilango, you may have heard because it gets some publicity in front and so on. Well, he introduced into the assumptions of cryptography, not just hard computational problems, but also things of the nature of Geller's theorem, that something is unprovable in some, you know, mathematics, a proof system like Ceramello-Frank, whatever mathematicians use. Someone 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 45 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. And young, brilliant minds are entering the field all the time, but it's also very lively and interactive and collaborative. And, you know, just, yeah, many of my best friends are also colleagues.

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, Shores work on quantum algorithms, you can say, why do that? there are no quantum computers. Maybe let's wait if somebody built once and we understand why, you know.

So no, the answer is no. No, you should try to understand whatever is natural for you to understand. This field has already, you know, maybe it was not clear 40 years ago, but something clear now that all, you know, that lots of theoretical understanding is not just positive,

of mathematical results, but because it is about computation, it is meaningful and often enough or whatever in the real world. There are many, many other examples besides crypto and quantum, including theory and the field's revolutionized coding theory mainly because of the PCP theorem, tools needed for. So, you know, there are lots of examples, and this eventually went into systems, you know, for memory schemes or whatever. Look, I'm interested in P versus NP. This is a question about impossibility, right?

This is a problem. We still didn't get closer in this, at least. The years I've been at it, we are not much closer to showing hardness for anything. We don't know that multiplication is harder than a difference. It's a basic question. So this kind of question by itself is certainly not practical. I mean, it's not clear. Well, it is a little clear because if you find out of functions,

maybe you can substantiate cryptography on a theorem rather than on assumption. But anyway, there are questions in the field that don't directly relate and will not directly relate to implementations of any system. But they are all parts of trying to understand what efficient computation can do and what it cannot, or when can you minimize

resources of some type, and when you cannot, and how do different problems relate to each other. 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 competition. You mentioned a few times in this conversation, some people made a major discovery

and then it kind of broke some assumption that was maybe 50 years ago and 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, you know, where you make a major. Because a lot of people's careers,

like maybe if you're just the end, engineer, you just, you got your shipping projects every year. But in your case, like, let's say you, imagine you discovered p equals NP or something like that. How do you feel when you make those discoveries, those sparse discoveries in your career? Well, it's great. Yeah, it happens. The big ones happen rarely. I think of science. I mean, realistically, science and math is, a community of ants work. I mean, most progress, we have these conferences,

theory conferences, stock and folks, and then we have all sorts of, you know, satellite conferences, and there are hundreds of papers in them. Cell light, I mean, focused on concrete area on learning theory, crypto,

I don't know, online algorithms. There are many, many, there are thousands researchers working in this, I don't know, maybe. And they are produced, using many papers a year. And most papers, 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, abound 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 send this shockwave to everybody learns them and uses them.

But, of course, you know, those bigger understanding, it doesn't have to be a resolution of 50 years of paper. It can be something that, you know, when Barrington discovered his algorithm for counting, that I mentioned, he was trying to actually prove that it's impossible. 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 is a phenomenal result. It's rare. I tell all my students and postdocs that, you know, you don't work for the million dollars. A million dollars is nothing, of course, for some of these problems. But yeah, you work because you enjoy the practice of it. You enjoy thinking about this problem.

In fact, most days in the life of my life, mathematician's life, is unlike a system's 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, 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 wasted day. There's something that you gain from me 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 even if it's small, sometimes it's very successful. Last question for you, and I think people in the field might be curious because you have so much experience is, you know, if you could go back to the beginning of your career when you just started, you know, becoming a researcher, is there any advice that you'd give yourself? I think I was lucky enough not to think that I would change anything. I think I was lucky enough. And many people are lucky in this field because the field is so accommodating to young people. There's, it's completely levered. There's no hierarchies. People would go to conferences and meet the... I remember my first conference meeting,

DeKalp, who was, you know, goes in the field and invented that, you know, did all these un-p-complete things. I was a first graduate student, and somebody introduced me to him, and he immediately asked me what I'm doing. And I said I proved that some problem was NP-complete, and he was actually interested.

It amazed me. I was lucky to have phenomenal mentors as an undergrad as a graduate student. I was lucky to have unbelievable collaborators over the years. And, you know, you learn from all this. So it's not a very informative advice to people to tell them to be lucky. I think this environment exists. I think that one piece of advice I give everybody is that in early stages is to work on things they enjoy the most.

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'll, you know, but maybe that's not your problems. Maybe it's not your affinity to them. You have to experiment with the type of problems. It's good to have a variety of areas and papers to read in these areas or problems to understand. It's always good to start with a few to sort of better understand your capabilities. And often what you like most is what you are better. Thank you so much for

your time, Avi. I really appreciate it. Yeah. 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 Eliskov, Mike Stonebreaker, Mark Brooker. These were all people that I brought on because someone left a comment. On another note, aside from the podcast, I'm working on building the ergonomic keyboard that I wish existed. Here's a glance at the prototype. It's a split keyboard. So there's two sides. 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. 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.