P, NP and mathematics - a computational complexity perspective
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 33 | |
| Author | ||
| License | CC Attribution 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/15981 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
| |
| Keywords |
1
4
7
8
9
11
12
13
14
15
16
17
20
21
22
24
26
32
00:00
DeterminantDeterminismExpected valueSequenceRandomizationErgodentheorieLengthPseudozufallszahlenPoint (geometry)Theory of relativityMathematicsMultiplication sign2 (number)Proof theoryFunctional (mathematics)PolynomialPower (physics)Numerical digitPerspective (visual)MultiplicationRootInverse elementMathematical objectPotenz <Mathematik>AreaResultantGraph (mathematics)MereologyIntegerDescriptive statisticsNumerical analysisExistencePhysical systemTheoremDegree (graph theory)Observational studyGreatest elementObject (grammar)OvalOperator (mathematics)Axiom of choiceHypothesisComputability theorySheaf (mathematics)Matching (graph theory)Proper mapState of matterAmenable groupDichotomyPhysical lawLecture/Conference
09:14
Population densityNumerical analysisIntegerPrime numberTheoremNumerical digitRule of inferencePolynomialRange (statistics)Multiplication signPotenz <Mathematik>Statistical hypothesis testingProduct (business)Different (Kate Ryan album)Variable (mathematics)DeterminantRandomizationCoefficientProof theoryState of matterFundamental theorem of algebraComputer programmingAreaMatrix (mathematics)Decision theoryIndependence (probability theory)SubsetProcess (computing)Standard errorGoodness of fitParameter (computer programming)Point (geometry)MeasurementSampling (statistics)Power (physics)Randomized algorithmPrime idealKörper <Algebra>DivisorResultantDegree (graph theory)Stress (mechanics)Object (grammar)Open setGleichverteilungIdentical particlesSpecial unitary groupSign (mathematics)ExplosionDirection (geometry)Greatest elementSimilarity (geometry)Ocean currentLine (geometry)Lecture/Conference
18:28
Plane (geometry)ExplosionVolume (thermodynamics)1 (number)Right angleGeometryMultiplication signGame theoryAnnihilator (ring theory)ApproximationObject (grammar)Computer programmingDirected graphNumerical analysisCountingKontraktion <Mathematik>ReliefGaussian eliminationUniformer RaumPoint (geometry)Connected spacePotenz <Mathematik>ChainOrder (biology)Thermal conductivityWeightEvent horizonLie groupGroup actionObservational studyLimit of a functionDirection (geometry)CoefficientFunctional (mathematics)Well-formed formulaKörper <Algebra>Grothendieck topologyCartesian coordinate systemSampling (statistics)Randomized algorithmProof theoryAbelsche GruppeRandom walkPolynomialLattice (group)RandomizationSet theoryFunction (mathematics)Statistical mechanics2 (number)Group theoryFundamental theorem of algebraGraph coloringConvex setPolytopDimensional analysisSlide ruleEvoluteHyperplaneEstimatorResultantPseudozufallszahlenSpacetimeCanonical ensembleMathematical analysisMany-sorted logicBound statePerfect groupParametrische ErregungInequality (mathematics)Independence (probability theory)TheoremLecture/Conference
27:41
Expected valueUniformer RaumDistribution (mathematics)Process (computing)GleichverteilungMany-sorted logicCondition numberFundamental theorem of algebraNumerical analysisPhysical lawReflection (mathematics)ModulformGroup actionIndependence (probability theory)Focus (optics)FrequencyFunctional (mathematics)Beat (acoustics)RandomizationLogarithmConnected spaceArithmetic meanPoint (geometry)PseudozufallszahlenDeterminismLecture/Conference
32:11
Functional (mathematics)Formal power seriesLine (geometry)Power (physics)Randomized algorithmRandomizationPoint (geometry)PseudozufallszahlenVotingLecture/Conference
34:02
RandomizationOpticsPrimality testPrime numberPseudozufallszahlenDeterminismDeterminantMatrix (mathematics)Sign (mathematics)Functional (mathematics)PermanentProof theoryPhysical systemInfinityRecursive setParameter (computer programming)Random walkComplete metric spacePower (physics)MathematicsRandomized algorithmRiemann hypothesisTheoremAffine spaceGoodness of fitConnected spaceResultantApproximation algorithmCompact operatorCombinatorial optimizationFactorizationStandard errorString theorySet theoryArithmetic progressionMultiplication signGraph (mathematics)Glattheit <Mathematik>Natural numberGame theoryPredicate (grammar)Sampling (statistics)Expandierender GraphSpacetimeCategory of being1 (number)Graph (mathematics)Cartesian coordinate systemProduct (business)Content (media)Point (geometry)Many-sorted logicDifferent (Kate Ryan album)AreaArithmetic meanTerm (mathematics)PolynomialTheory of relativityMathematicianBound stateNumerical analysisFundamental theorem of algebraHypothesisPhysical lawWaveBuildingModulformMereologySelectivity (electronic)Hand fanSummierbarkeitSubstitute goodSequenceObservational studyReal numberProjective planeForcing (mathematics)Model theoryVolume (thermodynamics)RectifierTournament (medieval)Matching (graph theory)Mass flow rateAnalogyCoefficient of determinationMathematical optimizationApproximationGreatest elementState of matterStandard deviationVotingLimit (category theory)FamilyComputer programmingLecture/Conference
Transcript: English(auto-generated)
00:01
Ladies and gentlemen, it is with great pleasure that I introduce our next speaker, Avi Wigderson.
00:26
He obtained his bachelor degree from the Technion in 1980 and his PhD from Princeton University in 1983.
00:41
Among his awards, I would like to mention Justin Avandina Prize, which he received in 1994. Avi has many outstanding results in the theory of computing, in graph theory,
01:05
and in other areas around theoretical computer science. But besides these outstanding results, what I think is the most important aspect of his mathematical personality
01:27
is his extremely broad knowledge and his extremely broad view about what is going on anytime you have any question about what this or that area is really about,
01:46
Avi will give you a fantastic description going to the depth that you would think that maybe only somebody, a special person in that area could give.
02:06
Avi considers theoretical computer science as a key part of mathematics with a view which I share, and he has been thinking about and working on some of these extremely difficult questions,
02:27
which many of which can be summarized as a simple dichotomy, like determinism versus non-determinism, or what is the relationship between parallel repetition of an algorithm or protocol versus
02:48
sequencer repetition of an algorithm or protocol, or what is the relationship between a randomized computation, a computation using randomness versus deterministic computation.
03:06
It is with great expectation that I am looking forward to this talk where he will summarize his thoughts on P and P and mathematics from the perspective of computational complexity. So, Avi.
03:32
Thank you. Do you hear me? Thank you very much. I've written something like,
03:41
I exceeded the page length they gave me at the proceedings by a lot, and I've written 50-some pages on my thoughts on this very broad subject, and then I had to pick a topic for the talk. I could pick several one-hour lectures from this paper I wrote, and what I decided to
04:04
do is talk about randomness. So, let's see if this works. This is the talk I'll give today. I was going to say that randomness, of course, occupies many, many thoughts and
04:21
bodies of mathematics and probability, statistics, ergodic theory, information theory. There are many views of randomness in mathematics, but if you just came to the last talk of Terry, he mentioned randomness and pseudo-randomness so much that I don't have to go on. Here is point of view of randomness, again, from computational complexity when you are short on
04:43
time or short on any other resource, and you wonder how powerful this is. Okay, so I'll tell you what we have understood in the last 20 or so years about this question. So that's a highlight of the summary of the talk. I'll have to give you some background in computational
05:06
complexity, and I'll explain what I mean by efficient algorithms, hard and easy problems, and the P versus NP problem I'll have to mention because it will be essentially related, as Terry speculated in his talk, it will be essentially related to the question of randomness, as we'll
05:22
see. So then, in two parts, first I'll demonstrate the power of randomness in computation with examples from mathematical problems, and then I'll tell you why actually this power may not be what it seems, and this will get us into understanding a definition of randomness,
05:42
pseudo-randomness, and the relation between computational difficulty and randomness. And then, we'll see with time, I want to talk about randomness in other settings, in saving space, and in understanding proofs, mathematical proofs. Okay,
06:03
the, we are going to study the complexity of computational tasks and, you know, people, humanity always wanted to do things efficiently, our time on Earth is bounded, after all. But after Turing gave us a definition of an algorithm, this became the mathematical object,
06:23
so the computational complexity of problems is a mathematical object of study, and just, I'll give two examples, famous examples, and I want to use it to demonstrate what I'll call easy or hard. So, a very easy problem, which we learn in first grade, second grade, is how to do long
06:43
multiplication. We want to study it as a function of the length of the data, the length of the numbers, how many digits they have, and if, in this algorithm we learn, if they have n digits, the multiplication takes something like n squared steps. So that's what we call an easy problem, it has a polynomial time algorithm, that's p. Here's another problem, which is just
07:06
the inverse of the first, I give you an integer, you need to find prime factors, and here we are not doing that well, I mean, the best known algorithm so far is something like exponential in square root the number of digits, it's huge for any large number, and
07:23
if that was the best we could do, this would be a hard problem, exponential time algorithms are inefficient. The truth is, we don't know whether it's hard or not, and what's more interesting here is that the whole world, including all of you who are buying, using your credit card
07:43
on the internet, believe that it's hard, because that's what the security of the transactions depend on. But nevertheless, we don't know, that's a great challenge, a great problem. Here's another problem, which is probably dear to everybody's heart in this audience, another computational task, it's theorem proving. The input to this problem is a
08:07
mathematical statement of our choice, like the Riemann hypothesis, and some integer n, which is how many pages it will be, to write down a proof, and the task is to find a proof for this in any
08:22
system you want, for example, or I don't know what, of that length, if one exists. You know, what's the complexity of this problem? I mean, I think everybody here will agree that in general it should be difficult, but we don't know that. However, we do know relations between the complexity of problems. For example, it turns out that if there is a fast algorithm for this
08:48
problem, there is a fast algorithm for factoring integers. So even though we don't know whether they are easy or hard, we know this implication. And this is a consequence of a very basic theorem of Cook and Levin from the 70s, that this theorem proving problem is a
09:08
universal problem, it's a complete problem in the class NP, which I won't even define, but it's a large class, and in particular, this problem turns out to be equivalent in complexity to
09:21
a huge number of other problems from mathematics, from computer science, from other sciences, that look sort of unrelated. So it's a very special, of course it's very special for mathematicians, but it turns out to be special in this much broader sense. And so if you want to state the previous NP problem, one formal way to do it is just asking
09:43
is a polynomial time algorithm for theorem proving? Can a child prove the Riemann hypothesis? And we don't know, we cannot rule it out yet. And of course it captures a much deeper thing, it captures questions about whether we can automate creativity, at least mathematical
10:03
creativity, but actually it's much bigger than that. So that's the question we cannot answer, but you know, we have our beliefs, right? So there are all these problems in NP and even beyond, for which we don't only have a polynomial time algorithm, we don't have anything
10:23
non-trivial. The obvious exponential time algorithm seems to be the best we can do. So if you ask yourself is any of this problem hard, requires exponential time by the best algorithm or exponential size by the best hardware circuit, you will be forced to conjecture.
10:44
This is a standing conjecture. Everybody believes that you know, P is different than NP, in fact there are problems in NP like theorem proving that probably requires exponential time. So that's one fundamental question of theoretical computer science. Now let me move to the second fundamental question, which is about the power of randomness.
11:08
So what I want to demonstrate by a few examples is a set of problems, very natural problems and they are just examples, there are many more,
11:21
for each of which we have a very efficient probabilistic algorithm and for none of which do we have even a sub-exponential algorithm so far. So this will demonstrate the power of randomness. So let me start, there'll be examples from different areas of mathematics, these are very basic simple to state problems,
11:45
but before that let me just define what is a probabilistic algorithm. So a probabilistic algorithm is an algorithm, a program that is allowed to toss coins or dice. So we assume that we have at our disposal just a perfect uniform distribution, just a
12:07
collection of independent unbiased coin tosses, which the algorithm can use for its decisions and of course once you allow randomness in your computation the outcome of your
12:21
computation becomes a random variable and the question then is, you know, that you may have errors so what do you accept as a good algorithm and we'll accept anything that does the job with very high probability, with let's say 99% probability.
12:40
Why should anyone tolerate error in, you know, why should anyone tolerate error period? Well I mean there are many answers, I mean the good, maybe the best argument is that we tolerate it anyway in life all the time so why not in
13:00
algorithms. Actually errors in probabilistic algorithms are much better behaved than errors in life, you can decrease them arbitrarily which is something you cannot do if you just cross the street and want to avoid being run over. So you can repeat the probabilistic algorithm many times and decrease the error exponentially and of course the real reason we
13:25
use it is for some problems we can't do it deterministically so we use randomness and it's a very powerful tool and here are the examples I want to give. First is number theory, you know, recognizing primes and here, you know, I've been giving
13:46
similar talks for like 20 years and primes were my prime example of a problem that has a probabilistic solution but not deterministic one but this was ruined two years ago by a beautiful result so in the 70s, well let me say what the problem is, I give you an n-bit
14:05
or n-digit integer and I ask you whether it is prime, I refer it to Gauss here, of course people ask it, well I guess it doesn't matter, people ask it for ages but
14:23
Gauss wrote the most explicit paragraph challenging the world with finding the complexity, computational complexity of this problem in the language of his century, he's talking about indefatigable calculator so it's, you know, it's clear it was after the exact
14:42
computational complexity of this problem. In the 70s, Solveig Strassen gave a probabilistic algorithm that really started the age of probabilistic computation, very efficient algorithm for testing primality and that used to be the best example and in a wonderful
15:03
breakthrough that I'll talk about later too, Agarwal, Kial and Saxena found a deterministic algorithm, so this is not an example of the type I wanted but there is a related one which is, I just give you n, the number n and ask you for an n-bit prime, well I mean probabilistically
15:28
it's trivial because of the density of primes, you just pick let's say a thousand n integers in the range in, you know, numbers of n digits and apply to each of them the primality test, well with high probability, you know, one of them or many of them will be prime,
15:43
so the density guarantees it but if I ask you for a deterministic algorithm, nobody has an idea how to do it in less than exponential time so far, so that's one example. Let's do an example from algebra, so polynomial identities, here's one famous one, right,
16:04
if you take the Vandermonde matrix of n variables and look at its determinant where we know that it will equal this product of all differences and Vandermonde proved it, but I just want to state that to clarify, right, this is an exponential size object,
16:21
if you open it up to check all the coefficients, that all the coefficients are zero, I mean you will never end, so of course that's not the way Vandermonde proved it, he found a better proof by induction, that's a simple theorem but in general, if I gave you another polynomial, you know, something that you think or if you had one,
16:41
you came up with one that you believe is an identity, it's a polynomial that's described somehow implicitly like this one and you want to know whether it's identically zero, it vanishes completely, how would you do it? Well again, probabilistically it's very simple,
17:03
this simple algorithm, well I mean we know, if it's not identically zero, then it's a variety, it has measure zero, so a random point will not be on it and you can even discretize it, it's enough to pick a value for each of the variables randomly in the range, let's say between one and a hundred d, any hundred d,
17:26
let's say integers for each one, you pick it randomly, so you do this very simple sampling and of course if your polynomial was identically zero, you always get zero, but if your polynomial is not identically zero, you will get a non-zero with extremely
17:41
high probability, that's very simple and you know again, nobody has an idea how to do it deterministically in sub-exponential time. Let me just stress that of course you need many values in your field, whatever the field is, for this algorithm to run and there is a reason,
18:02
if you are working over a very small field, the problem is currently complete, so can't hope to find such an algorithm, but on the other direction, if the field is large enough to contain so many elements, this is the degree of the polynomial, then you can do much more than testing zero, in fact there are better algorithms and they are used all over the place in the computer algebra packages, you can factor polynomials
18:25
for example, and again this is a probabilistic algorithm and has no deterministic counterpart. Okay analysis, I'm trying to touch on everything, so for your coefficient, suppose you have
18:41
again an exponential size object described implicitly like a function on the cube, on the boullion cube, let's say it's given by a formula or a circuit and some epsilon and you want to find all the large Fourier coefficients of the function, okay so even though there are exponentially many, there aren't too many bigger than epsilon,
19:04
just by parceval, so can you do it? Now in the previous two examples the probabilistic algorithms themselves were very simple, you just sample blindly and it works, here it's much more sophisticated and there is this beautiful probabilistic algorithm of Goldreich-Levin which does adaptive sampling and which gets with high probability all the
19:27
large Fourier coefficients and in fact it can be extended to arbitrary abelian groups again of exponential size that are described implicitly and it has very important applications in coding
19:41
theory and complexity theory and again we have no deterministic way of doing that. And the last one, geometry is again a very basic problem, the problem is that you are given in very high dimension a convex object, let's say a polytope, it's given implicitly,
20:02
let's say a polytope given by the bounding hyperplanes and you want to estimate the volume of this body, like the volume of this audience. Now I say estimate because it's not hard to see that computing the volume exactly is even worse than NP-complete so we should settle for an approximation.
20:26
That was a well-known problem for a long time and then came this ingenious solution, first by Dyer, Fries and Cannon and then by a host of people with more and more refined,
20:41
beautiful, faster algorithms and similarly beautiful analysis. So let me give you the idea of this probabilistic algorithm because again it's very different than the previous ones, just a very highlight. So there are several ideas that come in here.
21:00
The first thing is you discretize the space so computing the volume is, approximating the volume is roughly counting the number of, approximately counting the number of lattice points inside this body. And the next is a connection, a very basic connection between approximate counting and uniform sampling. It turns out that it will be sufficient to find an
21:25
almost random point inside the body to approximately count, but now we cannot throw darts, we cannot sample in a bigger ball because we are in high dimension and the probability of falling in the body is exponentially small. So what you do is something
21:41
much more clever, you take a random walk inside this body. So this is a slide I stole from Latsilova, I couldn't have generated that. So you take a random walk inside the body and if you just happen to move out you immediately go back and it's a Markov chain
22:04
and you know it eventually will get you to a uniform point in the body, but eventually you know when. And it turns out to know, to show that it's rapidly mixing, to show that in polynomial time you get to a random point, you have to analyze the spectral gap in this
22:23
Markov chain and for this you need to develop these parametric inequalities for general convex bodies and these are the type of things that go into the proof. I should mention that this type of Markov chains appear a lot, it's the Monte Carlo method in statistical mechanics but analyzing these various Markov chains borrow from these techniques here and it's important
22:47
group theory in other areas as well. Okay, so we've seen four examples and you should believe me or you probably know that there are many more. Does randomness help or these
23:03
are just, you know, demonstrate our ignorance? Other problems that have probabilistic polynomial time algorithms but no deterministic counterparts, that's the second fundamental problem in theoretical computer science and well suddenly the examples and our current knowledge
23:23
would tempt you to conjecture that the answer is yes. Let me remind you the previous fundamental problem, does NPO, this set of problems require exponential time, exponential size and we also believe that. So the main point of this lecture for those who
23:44
didn't know it already is this. These two conjectures, first of all even though they don't look related at all, are intimately related, in fact one of these conjectures must be false and if you ask which it's this one. So what's going on, you know, what is the
24:08
connection, where is this coming from? So that's what I want to explain to you in the next couple of slides. So again, what is another way of saying it is if there are hard problems
24:21
then randomness is not as powerful as it seems. So let's go to this. What's the connection between hardness and randomness? So this has evolved over, it's a program really if you want to give it the mathematical
24:40
name even though it was not stated as a program, it's just an evolution of results and understandings starting from the mid 80s, even continuing still today, is that you can take hard problems and construct from them pseudo-randomness that looks good enough
25:02
to all probabilistic algorithms. You can trade off hardness and randomness. And let me give you one concrete one which is in some sense the strongest of this set of events. I'm not stating it in full generality but in particular if any problem in NP requires
25:24
exponential size, it's as hard as we think it is, then, I was very happy to see this in Terry Tao's slides, then BPP equals P which in plain language means that every probabilistic polynomial time algorithm has a deterministic counterpart. There is nothing you can do with
25:43
randomness that you cannot do without in polynomial time efficiently. This is what I want to sort of sketch the ideas of in a second. I just want to mention that now that we have a connection between hardness and randomness, at least hardness implies
26:03
pseudo-randomness, you might wonder how tight is this connection and it turns out that very recently we have been able to start to get partial converses to this theorem. So these two fundamental questions that seem so distant are not only related in one direction,
26:22
in some sense they are even related in the other direction and from de-randomization you can sometimes build hard problems, prove lower bounds on complexity. I will not talk about that, I will just talk about, but you can hear more about this subject both in Luca Trevisan's
26:45
talk and in Omer Reingold's talk later this week. Okay, so let me go back to this. How do we take hard problems and eliminate randomness? What is the connection? Okay,
27:00
so the key word is computational pseudo-randomness, very, very, very different than the pseudo-randomness that you have seen in Terry's work and let me try to explain what kind of, what do we call pseudo-random. So first let me say what is our problem? What do we want to do? We want to show that we can take any probabilistic algorithm and remove
27:24
the randomness and still run it, you know, deterministically somehow. So what is a probabilistic algorithm? It is an object like this, it has an input, it has a source of randomness and remember this is perfect randomness, independent on bias coin tosses, that is why they are gold color. And then we get our output with high probability is correct. And we want to eliminate
27:47
randomness, so let's reduce our expectations a little bit, let's not ask ourselves how to remove it completely, but let's ask ourselves what other distributions would do as good a job as a uniform distribution. Okay, so what other distributions here, maybe biased correlated coins,
28:08
would still cause the same algorithm to behave similarly to compute with high probability the right answer? And well the answer is a definition, it's a fundamental definition, I mean at this point it's, you know, we'll have to give it meat, but let's call such a
28:27
distribution pseudo-random if it satisfies exactly what we want. If every algorithm on every input, every efficient algorithm, I'm sorry, every efficient algorithm on every input will behave the same. So distribution is pseudo-random if no efficient procedure can
28:47
distinguish it from random. That's the key definition. And once you have this definition, it's clear that you can replace this by this. The question is whether there is any pseudo-random
29:00
distribution other than the uniform one, and whether you can, you know, build it without randomness. So that's exactly what we are going to do. We are going to create a pseudo-random distribution without randomness, deterministically. So let me tell you how.
29:20
So we have no beats, we want to create this N pseudo-random beats. Well, I mean, we can cheat and take, well okay, let me just stress, this construction should be deterministic and efficient, because we want the whole construction together to be efficient. Okay, so we can cheat and start not from no random beats, but from a few
29:42
random beats. Why? Because, I mean, if we just let ourselves have log N random beats instead of N, this is no problem because we can enumerate all the possibilities. The number of possibilities is still just polynomial in N. So that's okay. And now what we want to do is to convert this
30:00
log N pure independent beats into N pseudo-random beats in this sense that will fool every possible algorithm. Okay, so this is the problem. How do we do that, and what's the connection to hardness again? So let me give you a sketch. Yeah, this procedure is called the pseudo-random generator. Expanding a few random beats into
30:22
many pseudo-random beats is a pseudo-random generator. So how do we do that? What I'll show you is just not how to convert K, you know, log N to many, to N random beats. I'll just show you how to just increase the number of beats by one and have a pseudo-random distribution.
30:45
How to go from there? It's like, well, it takes work, but I won't get into it. So let's suppose that this is our only task. We have to generate something that looks random, that looks unpredictable, K plus one random beats from K random beats.
31:04
So, well, I mean, the first K is obvious. We just copy what we have, right? So that's no problem. We have K random beats already. How do we generate the last beat that should be, should look unpredictable to any efficient computation? Well, I mean, there is only one
31:24
thing we can do. We can take, we have just these three beats, so we can take some function of them, and this function should be computationally difficult. Computationally difficult means here, computationally difficult in an average sense, right? We not only should not be able to predict this beat exactly from the previous ones or from the input. We should not be able
31:47
to even guess it better than 50-50 because that's what random means, right? No efficient procedure should be able to guess it better than 50-50. And so what we need is a very strong hardness. We need an average case hardness of a function. And what we have assumed,
32:05
you already see a connection, but what we have assumed is something much weaker. We just assumed that some problem is computationally difficult. Maybe it's difficult just on one input, right? And there is a whole work to do here in amplifying, let's say, amplifying
32:22
the difficulty of a function that may be hard on rare instances into a function that's hard on essentially half the instances because yes, no question. It's the best you can do, and there's a lot that goes into this part. But the key thing is that you can use a computationally
32:42
hard function to compute bits or bits that look random to any efficient procedure. And that's the key to the pseudo-random generator here. So let me just make sure that we understand the whole process, what happened here. The way we deterministically emulate
33:01
a probabilistic algorithm is to look at this generator we have just constructed and try, if you were going to do it deterministically, we don't have this randomness, so we enumerate over all polynomially many possibilities of the seed, evaluate the output, feed it to our algorithm, and take eventually a majority vote. And this
33:24
will behave exactly or almost exactly as the probabilistic algorithm behaved initially. Now, let me make a point that's extremely important here about this pseudo-randomness paradigm. We wanted to fool or to remove randomness from all possible algorithms, and we
33:44
could do it under some assumption, under the assumption that we have a difficult problem, let's say in NP. But this paradigm is much broader, is much more powerful. For example, you may want to fool not all algorithms, you may want to fool a particular algorithm. This particular algorithm is analyzing randomness in a particular way, maybe you can
34:06
just fool the use of randomness there. And it turns out that you can do it in many specific instances, and some of the highlights are the primality testing algorithm, the deterministic primality testing algorithm of Agarwal, Sehgal, and Saxena. It comes from
34:22
the randomizing a particular primality test, and it has no assumptions. And similarly, a problem I'll talk about in a second. Okay, so using this pseudo-random generator, which is based on computational difficulty, you can compute a small set of pseudo-random strings,
34:43
and their average behaves like the average of all random strings. Okay, good. Let me move to the power of randomness in other settings, computational settings.
35:01
One setting, which is very ancient, problem is the case not when your time is limited, but your memory is limited. Like, you come to a new city, you've never been in, let's say, Madrid, you want to get to your hotel, you have no map, and moreover, you have no memory, in the sense that you cannot just explore and note down everything you've seen so far.
35:25
You just can remember, basically, where you are, and what are the names of the streets that you are currently looking at. But that's all. That's what we call log space. What you remember is about log n bits out of this n-size graph. It doesn't have to be planar, it's a general
35:43
graph. Yeah, so what do you do in this case? I don't know what you do, but here's what undirected graph. What you should do is just take a random walk. Drink a bit, and then start walking.
36:07
And amazingly, in polynomial time, you will get to your hotel and to any other hotel in the city. It's not trivial, because in directed graphs, it's not like that. If you have one-way
36:22
streets, you're dead. But it's a very elegant, very simple solution to this problem. And this problem is not an isolated problem. Again, it's a complete problem for a natural class of computational problems. And it's a probabilistic algorithm. There was a natural question, can you de-randomize it? It's a very different game than what you've seen before.
36:45
And there's just, again, a breakthrough last year, amazing result of Omer Reingold. Again, he will talk in this conference, is that you can replace this random behavior by a terministic walk that will do exactly the same, will get you to all hotels in the city.
37:06
And this walk can be computed again in lock space. You don't need to remember anything you see. And even more remarkable is this insight that he had in which the pseudo-random generator, if you will, that he's using, that he's building, is based on expander graphs that
37:25
seem not to be related at all, because most cities are not expanders. And he's using it on particular construction of expander graphs that we've done a few years before using the so-called zigzag product. So it's a beautiful, I encourage you to go to his talk.
37:46
That's one setting, the setting of space. And here you will see a problem again where randomness does not seem as powerful as, you know, in general. But there are other problems where randomness seems to be, or so far seems to be more powerful than determinism in the case
38:05
that you have no memory, but not in these cases. The last one I want to talk about, the setting which is, again, dear to every person in this room, is about proofs. What does randomness do to proofs? So I want to talk about probabilistic proof systems. This is a notion that
38:26
came up in two very important papers, Goldwasser, Mikhaili Rakov and Babay. And to tell you what a probabilistic proof system, let me tell you first what a deterministic proof system is, which is the proof systems you all know. So we are interested in proofs for some claims,
38:44
whether maybe Fermat or the claim that the Riemann hypothesis has a proof in 200 pages. This is a mathematical statement and we wonder whether it's true or not. And what's the proof system? Well, we in computational complexity abstract all proof systems in mathematics very simply.
39:07
Any proof system is defined by its verification procedure. A verification procedure, verifier, is an algorithm which has to be efficient and all proof systems in mathematics are efficient. Of course, we expect to be able to verify proofs we read in papers.
39:23
It takes two parameters, the claim and the argument, and should satisfy the obvious soundness and completeness. If the claim is true, then there should be a convincing argument. And that's a good case, in which case we call the claim, we call a theorem, the argument, we call a proof, and everybody is happy. And on the other hand, if the claim is false,
39:45
there should be no argument that convinces its verifier. That's a soundness. So that's a normal proof system. What is a probabilistic proof system? By the way, I should say that notice in this definition the prover plays a minor,
40:03
we play a minor role here. Somebody has to come up with this good argument. Anyway, what's a probabilistic proof system? Well, the completeness is the same as before. We want that if the claim is true, then there is a proof. And what we are giving up
40:23
in probabilistic proof systems, so what becomes probabilistic is the verifier, the verification procedure is allowed to toss coins and allowed to make errors. We are allowed to make errors in verifying correctness. This should be appalling to mathematicians,
40:42
and suddenly you may not want it for mathematical purposes, but you'll see that there are good purposes for studying it. So completeness we want always, and we are willing to give up a
41:00
little bit in the soundness. So it's possible, but with extremely low probability that this verifier will be convinced that the wrong claim is true. So where could you use such a definition? I mean, you may not want it in a referring procedure, even though maybe you do want it.
41:28
Okay, so let me tell you what probabilistic proof systems have that deterministic ones don't have. What are some remarkable properties of probabilistic proof systems? And I'll tell you about two kinds of them, two varieties, one is a probabilistically checkable
41:43
proof, the PCPs, which essentially address the question of trivializing the referring process, and zero-knowledge proofs, which sort of protect you against plagiarism. So what are these two probabilistic proof systems? So in both of them, I mean, we have
42:05
the usual setting, we have a particular claim, mathematical statement, we have a prover who has an argument, hopefully a proof, and a verifier who wants to check it. In probabilistic proof systems, the verifier who wants to verify that the argument is correct is allowed to just sample
42:29
a hundred bits from the proof, whether it's, you know, it can be a hundred pages, but it reads only, you know, a hundred randomly selected bits of the argument, then computes
42:40
some predicate and decides whether it's true or not. It seems almost ridiculous. I mean, we know that you cannot catch bugs in proofs this way, but the whole point about PCPs is that the proofs will be written in a particular fashion to make it useful. And here's a remarkable result that is about ten years old by these people. Every proof, every mathematical
43:05
proof can be converted efficiently into a PCP, into a format which affords this type of verification with extremely high probability. So if it was really practical, I think it would be
43:21
fair to say that referring would be much easier. It's not really a practical result, it's a theoretical result. However, I want to stress that the major application is not to referee, but actually for understanding combinatorial optimization and approximation algorithms of the hardness of approximation problems. And that's a very, very powerful tool
43:44
and these last ten years I've seen an amazing growth in understanding of the difficulty of approximation problems based on this tool. Here's the other magic you can do with probabilistic proofs. We have the same setting, but now we are worried about,
44:08
before the verifier wanted to verify correctness, now it's a concern of the prover. What is the prover worried about? Well, he may be worried that the verifier will read this proof and publish it first. So what are zero-knowledge proofs? This is a completely ridiculous concept
44:28
when you first hear of it because it's a proof which reveals only the correctness of the statement and reveals absolutely nothing about the content of the proof. It's maybe as ridiculous
44:42
as the previous one, but we saw that the previous one works, so this also works. Here's every proof, again every mathematical proof, can be converted into zero-knowledge format. So if I had a proof of the Riemann hypothesis, if I really did, I could convince you of it
45:01
without giving you a hint of what's in there, but you will be certain with any high probability you want that it's true. There is a difference between this and the previous theorem. This is assuming one-way functions, cryptography, or let's say that factoring, the factoring problem is difficult. And this indeed is a major application area of,
45:27
it's not for plagiarism, it goes into cryptography a big way, big time. It's a major theorem within cryptography and allows all sorts of magical properties of protocols, cryptographic protocols, to take place. So that's another thing. And both of these aspects,
45:45
zero-knowledge and quick verifications cannot be done if you have deterministic proof systems, if the verifier is just, you know, reading an entire proof given thing. Okay, let me summarize. One thing that is much more general than this talk is that when
46:11
you are wearing these computational complexity glasses and consider the efficiency of the layers participating in a particular activity or understanding particular concepts, then concepts
46:27
change their meaning and actually sometimes they get their correct meanings. And that happens to randomness, to games, to learning, to definition of knowledge, to definition of proof or definitions of proofs, and much more. And in particular about randomness, what we've
46:44
seen is that, you know, the definition here is that it's in the eye or rather in the power of the beholder. It's, you know, it's not an absolute term. It depends how much time you have to study your random sequence and try to find patterns in it.
47:04
Computational hardness can generate good enough randomness, good enough in the sense that good enough for efficient algorithms, and therefore the seeming power of probabilistic algorithms is probably just not there.
47:23
In other settings, randomness is powerful, sometimes cannot be eliminated. There are others I didn't talk about like distributed computing and cryptography itself. And that's where, you know, its power is showing. But as I said before, even in probabilistic
47:44
algorithms, it's a paradigm to build deterministic algorithms often is just design your favorite probabilistic algorithm and then de-randomize it and get a deterministic algorithm. So in some settings it's essential, some settings it's not, and some we don't know.
48:03
Since these results I described depend on hardness, we better find out whether these problems are really hard. We better solve the major, you know, fundamental question number one, prove lower bounds on the complexity of some natural problems. Can we do it for factoring?
48:21
Is factoring really difficult? And we really want to know whether, you know, not conjecture, but know that electronic commerce we use today is secure, or else replace it by, you know, replace it on other functions. Is theorem proving a trivial problem, or is it hard as we believe
48:40
it is? Is P different than NP? Can creativity be automated? I always have this when I, you know, at the end of a talk like this, when the end of a conversation with a mathematician about this, you know, they may say, oh, it's interesting and so forth. But, you know,
49:02
it's not my problem, you know, to do this, to prove this type of result, yeah, I have to get into the boring definitions of Turing machines and algorithms and what, how can a mathematician really look into this? Not a smooth function or, you know. So my answer is this.
49:24
There are many ways to phrase the P versus NP problems. All of you can work on it, and you are welcome to it. Here's a concrete one that's particularly appealing to mathematicians, doesn't mention algorithms, doesn't mention Turing machines. It's a simple relation between
49:41
two polynomials that are very familiar to all of you. Let's fix a field, make sure it's characteristic, it's not two, otherwise it's not interesting. Here are the two favorite functions, determinant and permanent. So determinant of a K by K matrix,
50:01
it's just what you know, and the permanent is the same function without the sign. Okay, suppose you want to compute the permanent of an N by N matrix. Here's one way you might want to do it, never mind why, but here's one way you can go about it. You can try to project it into the determinant, so you can try to embed your N by N matrix into a larger matrix,
50:28
a K by K matrix by way of an affine map, and then compute the determinant of the larger matrix. And what you want is that the determinant of the large matrix will be the permanent of the small
50:43
one. Okay, so let's denote, let's call a map good if it does it, if permanent is the composition of the determinant of this affine map, and let's denote K of N, the smallest K for which this can be done. Actually, it's not clear it can be done, but let me give you two theorems.
51:06
First one is that it can be done, and it suffices to have K exponentially big in N, like two to the N, a little bigger than two to the N will suffice. That's the result of Valyan, who saw this connection I'm talking about. And it turns out that there are even
51:28
lower bounds, and the best one is the recent one by these two algebraic geometers, a lower bound of N squared. What do you need to do? You just need to improve the lower bound a little bit. If you improve it to super-polynomial, you have proved that P is
51:46
different than NP. So it's a very concrete, clear, algebraic question that maybe is the right way to address this question. I put it in quotes because it's not exactly the same, but
52:04
it turns out that both the determinant and the permanent are complete problems for particular classes of algorithms, like P and NP, but slightly different. If you separate them for finite fields, if you prove this lower bound for any finite field, then you essentially
52:20
prove that P is different than NP. And the problem for infinite fields, for the complex rationales, whatever you like, is interesting as well. So any progress is welcome. Thank you.
Recommendations
Series of 12 media