ฝัง
- เผยแพร่เมื่อ 22 พ.ค. 2024
- Support us on Patreon: / polylog
We explain why Avi Wigderson got this year’s Turing award: We show how you can make any randomized algorithm deterministic.
0:00 Intro
2:41 P = BPP
5:38 Statistical tests
7:52 Pi as a PRNG
9:44 Nisan-Wigderson PRNG
13:47 Finishing the proof
14:45 Zero-knowledge proofs
Blog post: coming soon
Code for the animations: github.com/polylog-cs/derando...
Richard Hladík: Script editor, animator
Václav Rozhoň: Writer, animator
Václav Volhejn: Narrator, animator, script editor
Thank you to our beta testers: Matěj, Honza, Filip
Animations: manim, a Python library docs.manim.community/en/stable/
Color palette: Solarized ethanschoonover.com/solarized/
Music: Thannoid by Blue Dot Sessions
Pictures: Wikipedia, Internet
Video clips used:
Avi Wigderson: • Interview with Avi Wig... and • Professor Avi Wigderso...
Seismograph: • Tremors (2/10) Movie C...
![MOBYE - มีใจทำไมไม่จีบ (ASAP) [Official MV]](http://i.ytimg.com/vi/dCOdz92FU18/mqdefault.jpg)
Pelease a video on zero-knowledge proofs. As you said is real mathematical magic!
Yes!
We want this, as evidenced by you abbreviating "Please release" to "Pelease". The excitement is real
I once read a paper on zero-knowledge inspection of nuclear warheads, really fascinating stuff. A. Glaser et al. "A zero-knowledge protocol for nuclear warhead verification" Nature 510 (2014)
Pseudorandomness comes up a lot in audio processing. I tried making an algorithm for it, and to test it I stored the outputs in an array and played it back as audio, which very easily showed periodicities in the resulting sequence. Lots to be said there about how our senses are essentially derandomization algorithms.
Our brains are essentially pattern recognition machines so it's not surprising to me that we can detect randomness by using our senses.
Back in the early days of CG i used a pseudorandom generator to place trees in a forest. I was annoyed to find unnatural looking periodicity in the result. At first I was annoyed at the pseudorandom generator. On reflection, I saw it was a great example of the power of visualization.
I think this could be a real problem for some algorithms that use pseudorandoms.
I've often wondered whether the periodicity was audible. Good to know that it does. A generator can pass all the statistical tests and still fail an audible test!
I though about the curve fitting theorem used in digital audio, aka, the Nyquist-Shannon sampling theorem.
Why people thought randomness testing in "random" polynomials would be actually random, they aren't if you sample enough. Its a polynomial after all, it is not random because it has no discontinuity.
Pannenkoek Mentioned
Mentioned mentioned!
Appelstroop gepakt
Noam Nisan is also one of the co-authors of the excellent "From NAND to Tetris" course.
I did not know that one -- looks cool!
Love that book!
What is the assumption that most people believe? Where can I read more?
EDIT: The assumption appears to be: "E requires exponential circuits".
Paper Title: "P = BPP if E requires exponential circuits"
en.wikipedia.org/wiki/E_(complexity)
en.wikipedia.org/wiki/Circuit_complexity
Thank you; I kept thinking that through the video - "oh COME ON, at least tell us the name of the assumption!"
Yeah that's definitely a flaw in the video. It's good not to go deeper into it because it's out-of-scope but you should at least mention it once for those interested.
Yes! It is a bit hard to explain this assumption since it is quite subtle, it is important to distinguish Turing machines and circuits to understand it.
5:52 Literally just finished watching pannenkoek's newest video :D
Have you seen the nearly 4-hour one though??
@@PolylogCS have you seen the 40 day livestream though?? (i also just finished the latest one lol)
@@PolylogCSLoved every minute of it.
I liked the video at this exact timestamp ahah ! I love when random parts of TH-cam send winks at each other :D
Fantastic video, thank you. I understood not everything but enough to put it in my little brain folder of clever math tricks and algorithms in case I never need inspiration. Thanks for presenting this recent work so clearly and concretely, I really liked how you used concrete things like 99% and the polynomial detection algorithm instead of variables and generalities, it helps me think.
Trying to prove that the pi prng actually satisfies even the statement that it passes all checks that need O(n^10) time to run is really hard. In particular, that would require it to pass the check which just counts the number of each digit and then checks that they all appear about 10% of the time. We don't even know if this is true. It is possible that the first n digits of pi has a bais for a particular digit which persists as n -> infty. So showing that this pi generator actually works is fairly well outside of the realms of current mathematical knowledge, even though it is probably true.
After watching the video 4 times, I think I got the idea down. And this is useful because to solve a BPP problem using a pseudorandom generator, such as the Nisan-Wigderson PRNG, is easier than using a truly random generator, and in extension also saves time for solving P problems... I think? Although I can't think of any day to day scenarios where I can use this, I think that's enough maths for a day 😅
Great video! + would love to see a similar video for the zero-knowledge proof :P
The danger of using a PRNG for problem solving is that inevitably you are now monte-carlo. Its easy to think a PRNG is sufficient for your monte-carlo problem when it isnt, that it cannot explore the entire graph of states, or that it can only do so if you use it in a certain way. PRNG's suffer from there own bijectivity.
When you're solving a problem in the P model, you have no access to random bits at all. You have to be able to solve the problem without any random bits. The key insight here is that under certain assumptions, if we take a BPP algorithm and replace our random bits with pseudorandom bits, the same probabilistic algorithm will still solve the problem just the same.
We still need a seed for the pseudorandom generator, which normally would have to be random, but we get around that too by just trying all possible seeds. The seed is only log n bits, so this only adds a factor of n to the runtime.
3:20 Just a small correction: the classes P and BPP are for decision problems. Problems whose answer is "yes" or "no". Sorting and finding the shortest path aren't decision problems. The definition is often extended to optimization problems using the generic decision problem "Is there a solution better than some bound k?". Which works for shortest path. But not for sorting.
Good point! :) Our videos are unfortunately full of inaccuracies like that (another one: instead of derandomizing BPP we are discussing derandomizing RP) and I never know what the right trade-off between length and precision is...
Personally, for a difficult subject like this there isn't a hesitance to click until like 30 minutes plus. 15 or 25, id've clicked on it. I know longer videos are harder but some of these very intensely difficult and deep topics could use more. It left me wishing you had more asides explaining the things that were hopped over.
Very good video though! And your thumbnail is very good as well. I've never seen your channel but I'll definitely be reading through your backlog!
*Above statements are about my personal preferences
@@PolylogCS well, if I might give you my opinion on making approximations: if it costs nothing to be precise, then do it. (Examples of polynomial decision problems aren't few.)
If it does cost some clarity, then explicitely acknowledge it's not the full story and in what way.
As a teacher myself, I know it's not always easy to find the right balance. ^^
You can transform an optimization problem into a decision problem by asking "Is there a solution with an optimal value
I ran into PRGs when I was trying to find a topic to do for a small undergrad research project and ended up learning a ton about specifically this topic, since my project was on stuff that builds on this result. This is a nice way of looking at it! (I got bogged down pretty deep into the actual mathematical definitions, which while useful for convincing me that this proof actually works, doesn't help with the part where I'm trying to find the basic idea of what they were doing.)
The part that confused me most about this particular topic when I was researching was how the >1% probability implies there being at least one working input (which is based on how probability is defined). I think it'd be useful to make a note about that.
Can you tell us what your project was about
" I was researching was how the >1% probability implies there being at least one working input (which is based on how probability is defined). I think it'd be useful to make a note about that.", I think that when you're doing the tests you use a plethora of inputs rather than one, so it does make sense (I think, this topic is crazy confusing).
@@milckshakebeans8356 The specific thing that's confusing is that no matter how many tests you run, you can't get a probability down to 0% when you think of probability the normal way. This whole thing only works because we have a finite event space and can check ALL of the inputs to actually compute the exact probability for that input in the algorithm.
> The part that confused me most about this particular topic when I was researching was how the >1% probability implies there being at least one working input (which is based on how probability is defined). I think it'd be useful to make a note about that.
@calvindang7291 said it nicely: It is really important that all probability spaces are finite -- in particular, if your algorithm gets t random bits (random here means uniformly distributed and independent to be precise), there are 2^t possibilities that you can iterate over.
Great video! Thanks.
Just as a side-note regarding tests of randomness: in addition to statistical summary tests, there are other notions such as:
- Compressibility: how much can we compress a given sequence? If it’s “truly” random, we cannot compress it. This a Minimum Description Length characterization.
- Kolmogorov complexity: what is the length of the shortest computer program for generating the given sequence? This is a beautiful idea, although impossible to do, because we don’t know if it’s really the shortest.
All 3 approaches (statistical summaries, compressibility, and Kolmogorov complexity) are inter-related, since you can sometimes (not always) convert one to the other.
Great video, the pace is good, not boring at all for me, congrats. Maybe you could use dark theme for the animation, it would be better for the eyes. Keep up the good work. Cheers.
Thanks!
Fascinating. I had considered this a few years ago, after using PRNGs for some algorithms (e.g. primality testing). Since PRNGs are deterministic, it seemed clear that we could match the apparent benefits of randomized algorithms without the randomness. Avi Wigderson's insight, that randomness is based an observer's knowledge, is the key.
Consider that quicksort has worst-case quadratic time complexity. You can shuffle the input with a PRNG to work around pathological inputs, to achieve much better expected time complexity. Shuffling doesn't truly change the performance characteristics of quicksort. Instead, it remaps the input space so that different inputs get bad performance. You're unlikely to produce those pathological inputs in practice. This works as long as an adversary doesn't know about your shuffle and how it's seeded. However, poor implementations have been exploited by people to cause slow sorting. :)
Amazing stuff.
I subscribed midway through this video. Too good.
The pannenkoek reference was fantastic
4:24 I never realized before why they always use 10^9 + 7 as the base for modulo in competitive programming questions
It's just because it is a prime number that is easy to write and remember and close to the int32 boundary. It is other than that completely arbitrary.
Fantastic presentation, glad the TH-cam algorithm recommend this channel to me
Thanks lots of fun, wishing you all the best.
Awesome video. Thanks
You can compute arbitrary digits of pi quite efficiently, as long as you're using base 16. Now I have to try building a random number generator from that, thanks!
I have learned and subsequently forgotten how zero knowledge proofs work far too many times
Avi on the preview looks a lot like an old Maxim Katz, a russian politician and youtuber I actually confused with him. He's also an all-russian poker champion, the game you mentioned in the video. Now answer, is that random? 0_0
Nice video though, wasn't disappointed
This is a very important discovery for mathematics at the same level of Fermat last theorem and Poincaré conjecture
For that polynomial matching problem, for a polynomial of degree d, we can just match values of polynomials for d+1 values. As different polynomials can have atmax d intersections, we can deterministically find if it's the same or different polynomial in polynomial time. Thus, it's a P problem.
I was also thinking about this. Maybe it is because these are not only for polynomials, but other expressions, such as x*sin(x) which has infinitely many roots?
Or another idea I had, is that maybe in some cases it's not easy to determine (an upper bound) for the degree automatically (by that I mean that a well trained mathematician may look at the expression and give an upper bound, but the computer isn't this smart). Or for high degrees such as 10000, testing 10001 points would be too time consuming, even if it is polynomial.
@polylog could you clarify?
14:20 - "Since A is correct for at least some seeds" -- where did this guarantee come from? A is correct for some pseudo-random inputs, but since the seed is shorter than the sequence of inputs, it doesn't seem that there's a guarantee that you will hit a random input for A is correct simply by iterating over all seeds. The space of potential inputs (of which >1% produce correct results) is exponentially bigger than the spaec of seeds; it could very well be that by the way the PRNG works, you'd miss all those sequences. Or is this guarantee coming from the assumption that the PRNG cannot be distinguised from 'real' random sequences?
I hope to see your bass play in the next random video
I wonder if something like this can be used in encryption
subscribed. well done
cool
One step I'm still unclear on is how you go from 1% success to always works. My best guess is something along the gollowing:
1. Make a version of the slgorithm that fails ¼ of the time (just iterate 1% algorithm)
2. For input size n iterate the algorithm n times. This is still polynomial
3. The probability that this algorithm succeeds for all inputs of size n is (1-¼^n)^(2^n). The probability that it succeeds for all inputs of any size is Π_n(1-¼^n)^(2^n).
4. Take log and get Σ_n2^n log(1-¼^n). This converges using root test. Thus there is some nonzero probability that it succeeds for all inputs. So ther should be a way of seeding the prng which works for all inputs.
Does something like this work?
For an arbitrary input, you have a 1% success probability on the algorithm based on the random seed - that is, at least 1% of random seeds passed into the PRNG, for that particular input, will give the correct answer. 1% is more than zero, so at least one seed will be correct. You try all of the seeds, which will necessarily include the correct one.
I'm more used to the definition that needs a 51% success rate so you can take the majority instead of the one-sided algorithm shown in this video, but this one's probably easier to understand.
@calvindang7291
Yeah, we had a lot of headache thinking how much time we should spend talking about concrete probabilities, boosting success probabilities, two-sided vs one-sided errors, ... In the end we decided for the minimalist version of the argument that still looked followable.
@@calvindang7291if the only goal is to prove that P=BPP, you only need to prove that it's always possible. for the purposes of the proof, it's preferable to make it as simple as possible, so adding extra steps to make a higher proportion of possible PRNG algorithms pass the test would only detract from the clarity of the proof
Fresh hair, takes courage to rock that
5:10 I have an idea for polynomial testing.
Check for x=0
Check for x=1
Check for x=2
Check for all natural numbers less than or equal to the degree of the polynomial. A deterministic algorithm with 100% accuracy.
Why this is not used?
Because it is exponential in the size of the input. Even in the simple case x^n, you need to encode n, which needs log n bits. So your input z has length |z| = O(log n), and you need to test n = 2^(log n) = O(2^|z|) points.
There was algorithm, which calculates digits of pi with certain given index. So, it's not so bad to use pi randomiser.
However, larger index--more time it'll take to compute it anyway, because it's based on sum of sequence.
it probably used hard coded values to some extent, which defeats the purpose using it in this hypothetical. Pi itself is not important here, it's just used as an example of a PRNG algorithm that runs in polynomial time.
Idk why but I’m in love w you
Well done
So the end result and the ground truth about randomness is that it doesn't matter whether a sequence has come from a PRNG or a true-RNG, the only thing that matters is whether this sequence obeys a particular distribution law or not. For sequences of finite length it is only possible to say that they obey a distribtion with a particular degree of uncertainity and only for infinite sequences it is possible to distinguish between two distribution laws with an arbitrary precision. However, there's a question if it possible to tell apart two infinitely close distribution laws with an infinite sequence, which has to be answered with a kind of statistical limit.
As a computer and data analysis freak, I find this very useful.
I've never been comfortable with the many analysis methods based on pseudo-random generators. Now that I understand why, I won't waste my time implementing the useless.
Do the video where you do the zero knowledge proof with who is watching to prove you got right sudoku now
You said to leave a comment if there were something we did not understand... Who are "we" in "we hope to see you next time"? 🙂 Please, also make that video on zero-knowledge proofs!
Hi, the video is done by a bunch of nerds from Czechia :) -- see video description.
15:00 - sudoku.
True!
Very nice!
Thank you I know have a full understanding of randomness. Not sure what to decide about this nowledge though. Guess the pseudo part is part of this paradoxically parallell uni... Never mind. It seems to actually be hard to reapeth the zero knowledge proof in practice.
At least it might have sown some seeds. Looking forward to the growth. Know I decidedly now I put that tree somewhere in this forest.
Does this advance us in finding the elusive solution to the P vs NP problem?
What is the probability that I read the short story, Vault of the Beast by A. E. van Vogt yesterday evening, and this was posted at about the same time :-)
"He frowned. ‘That makes the whole thing ridiculous. The ultimate prime would be an indefinite number. ’"
Conditional expectations or pairwise independence, but why not both?
Noam Nisan from Nand to Tetris!!!!!!
Strong typicality is an interesting property
Is formula for circle (c1) x formula for cylinder (c2)= donuts (d) as in topology?? Admin plz do answer.
I will not talk about haircuts ;-)
I stand by my choices 🥣🤓
Cool haircut, I like it
@@PolylogCS vector
@@PolylogCS Do I see the first haircut in the Stroustrup series? Respect 🙇
It can be shown to be the unique haircut which has smooth derivatives of all orders
ALGOrithmic RANDomness.
Interesting.
that's great, but... is the assumption true? or is this a kind of "assume RH; then blah" type of result?
The assumption is a bit hard to explain, but it is a bit like "there exists at least one problem that is similarly hard both with and without being able to use randomness". So it is a bit safer than assuming RH but, yeah, I understand it's a bit underwhelming that there has to be an assumption. :)
9:35 - sorry for dragging semantics and philosophy into the discussion, but is there truly such a thing as "random"? You said that Pi only "looks" random, which is perfectly fair, since we have formulas to calculate it.
However, if we had a way to perfectly predict any "random" physical process (such as radioactive decay, fluctuations in temperature, etc.) then all of those phenomena would become PRNGs. The state is the state of the universe, the function is physical formulas, and the outcome is perfectly predictable.
I think you already touched on that when you mentioned flipping a coin as an example: randomness-as-unpredictability disappears if you can predict the outcome.
Besides, once you get a "random" value, doesn't it stop being "random" because you just generated it? Like you said, if you take some digits from pi, they look random, but they're not actually random, because you obtained them through a computation.
In more general terms, does that mean that "computable" and "random" are mutually exclusive, and that it's impossible to have a truly random value, because any value we can think of will be "computed" somehow?
What about the electric bass?
wait that was a 20 minuten newspaper 😯 you live in zurich
love your videos
Yes! Thank you!
This of course dosn't hold up when you assume an adversarial algorithm (or parameters the algorithm works upon)
Does this have any applications in ml?
Was that a 2 CHF coin you used? ;)
yes :)
The elephant in the room is that it's unsure if actual random bits can exist. We live in a deterministic universe, except for perhaps at the quantum level. The jury is still out on whether it is actually random at that level either. If there can't actually be random numbers, it makes some of this pretty moot.
One of the cool takeaways of Avi's work on randomness is that talking about randomness makes sense even in a totally deterministic universe -- pseudorandom bits still provably behave as random bits, if you don't have enough time to exploit them.
Good point! It being moot is a feature then, and is the whole point. Thanks.
I don't think we are doubting about randomness at quantum mechanics as it is the most prominent interpretation of it's phenomena. But if we are not living in a universe that contains randomness, then the problem is much more complicated because the start should necessarily be methapysical, which implies pure determinism would not answer it either.
So they just proved that I can indeed use my low discrepancy sequences in my path tracer lol
The hair.
Is there a use case? Or like an “unknown” that is now “known”?
Almost like you explained “this is some cool stuff” but like didnt explain why?
I might not paying attention
Is it that pseudo random and “real” random are probabilistic the same thing almost, pretty much?
I think it's a big deal for a few reasons. I'll give a couple practical real world engineering reasons, but in practice I think this is more important for theoretical computer science than day to day software engineering.
Reason 1.
There are algorithms that use randomness, and have certain properties based on that assumption of randomness. In practice, most computers only use pseudo randomness. Which is pretty good, but from a mathematical perspective they are not the same thing. Computer scientists might think up some great algorithm that solves an important problem, but most real computers can't use it because they can't produce true random numbers.
This proof shows that, given the assumption holds, any algorithm based on true random numbers has some deterministic equivalent that could run on real computers, even thoughost can't produce true randomness.
Reason 2.
Randomness can be annoying.
On a practical level, if I write some code and someone finds a bug in it, I want to run that code again to diagnose the problem. But if it's random, the algorithm might just act differently next time that makes it harder to diagnose.
This proof means we could make these algorithms deterministic and still get good results.
Reason 3.
In a theoretical sense, analyzing and understanding algorithms with randomness vs without is just different, and each can use different mathematical tools. Some problems might be easier to analyse one way or the other. This proof kind of bridges that divide, or at least shows that it's possible. If you can prove something can be done non-deterministically, you know there's a deterministic way to do it.
I don't do computer science research. I can't judge how this will actually impact research going forward. But that's my impression based on this video.
As for why I think this is more theoretical than day to day...
I said at the start that I do think this matters more to theory than day to day programming. In practice, we tend to just use pseudo random number generators and trust that it's good enough. In certain applications, most notably security and encryption, getting this stuff right is more significant.
It think it will probably be mostly researchers working on this stuff and figuring out what pseudo random number generators work, and how to turn non-deterministic algorithms deterministic.
I think a subtle aspect of the proof as shown in the video is that it doesn't prove you can just take any pseudo random number generator and run it through this process to get a deterministic algorithm. But it does prove that there must exist some pseudo random number generator that would work.
So I think the more significant aspect of the result is that it's possible to turn these algorithms deterministic, not that you'd necessarily be applying this technique day to day. Just the idea of using multiple seeds for PRNGs doesn't sound like the most revolutionary thing to me, and I suspect where relevant it is already applied.
What if this isn't even a good question... what if the idea of 'randomness' in the way that mathematicians 'want' it to be... what if this is just a nonsensical idea....
Nice
8:40 finding the k+1 ... k+nth digits of pi doesn't require finding the first 1...k digits.
First step where randomness is replaced with pseudo randomness, is understandable. But I didn't get the step where pseudo random check algorithm turned into deterministic one.
We were a bit fast there.
The idea is the following: we start with an algorithm that is trying to find a witness that the two expressions are different. We know that if the two expressions ARE different, the algorithm succeeds with >1% probability.
Also, although our algorithm is randomized, the randomness is coming only through the seed which is very short, for concreteness you can think of it as having e.g. 20 bits.
So, we know that at least 1% of the 2^20 possible seeds result in our algorithm finding the witness. In particular, at least one of those seeds result in our algorithm finding the witness.
We can thus iterate over all 2^20 seeds and check whether at least one of them results in finding the witness.
@@PolylogCS
But this looks like cheating, coz 1% is for infinite true random sequence, but pseudoramdom sequences don't coinside with true random ones (according to kolmogorov complexity results).
@@__-de6he From what I understood, I think your understanding is mostly correct, and it's just a matter of semantics. This is still a probabilistic algorithm, but it's also deterministic. It's not implying you will always get a correct answer, just that you will always get the same output for a given input. Some inputs will consistently be wrong, and the percentage that will be wrong can still be expressed as a probability.
And I think iterating over all the possible seeds just increases the probability of success.
thats a cool mathematical video, finally not something elementary
What is the assumption? that is the most important part of the proof.
you're cool
why is there a finite number of seeds?
It is limited by the number of bits used to represent the seed in the prng algorithm
You choose the seed length you want, and only use seeds of that length. (This is mostly to aid with analysis; but even if not, you could just pad the rest with 0s or something.)
Holy cow this video is great. Makes me feel like I could’ve come up with this proof. Thanks
So basically he proved that polynomial time functions that produce pseudorandom outputs are sufficiently indistinguishable from true randomness that you can replace any true random algorithm with a pseudorandom algorithm and it will still work. So since the pseudorandom algorithm is polynomial, then all random algorithms can also be polynomial algorithms? and also some stuff about how long things take.
I think
All randomized algorithms *that take polynomial time* can be made into a deterministic polynomial-time algorithm. You can't take something with arbitrarily high runtime and just lower it's running time, that's not how things work.
Can somebody explain to me why 1% correctness is enough? Doesn’t it mean that the algorithm does run in polynomial time, but doesn’t do so accurately at all, and then what is the point?
I could say then that we can sort any array in O(1) by randomly shuffling items in it and with 0.0000001% getting the correct result.
What am I missing?
Any constant threshold is enough because it's one-sided correctness. Imagine you have two 100-sided dice. One of them says "1" on every side. This represents a problem where the polynomials being tested are equal. The other one says "1" on 99 sides, but says "2" on the 100th side. This represents a problem where the polynomials being tested are different. If you roll both dice a thousand times, with high probability you will roll at least one "2" on the second die, but will never roll a "2" on the first die. So you can tell them apart.
It's amazing to see how randomness is created for encryption at Cloudflare. They use, among other solutions, a lava lamps wall and a camera to generate pure randomness. You can even visit this wall because human influence will create even more randomness. 🤯
Hardware generated randomness exists since a long time.
This may be creative or even ingenious reasoning on the part of the researchers, but it is not yielding any certainty, since it depends on an unproven assumption. As a conscientious researcher one must weigh whether or not to build on the result achieved. It may last the time of a whole career, or even several, but should the assumption be disproven some day, the work of possibly many researchers would be invalidated. In that case, again, the lasting value of the work might be merely historical or, in the best case, consist of novel reasoning techniques having been developed along the way.
A good point! One problem of complexity theory is that we can barely prove anything, so even proving something based on a believable assumption is a huge deal!
You should really look at that mic placement. Put it in the collar. I work sound on live TV. That’s what we do. It doesn’t need to be in the middle of the t-shirt.
What is the assumption they use to prove P=BPP? the assumption that most people believe
It was shown on screen at some point (around 10:08), but it's that there exists a function you can compute in [large amount] of time that you can't compute with small circuits.
It is a bit hard to explain because the difference between Turing machines and circuits is quite subtle. One intuition is that it is saying something like "There exists a problem that you can solve deterministically in exponential time and it requires exponential time even with randomized algorithms"
what IS the assumption MOST researchers believe to be true.
probably true, idk
If the pseudo-random version of the algorithm is still only correct 1% of the time, how do you convert that to a deterministic version of the algorithm? No matter how many times you run it there’s a nonzero chance you’ll get the wrong answer
because a prng is deterministic
By "correct 1% of the time", they mean "for each input, at least 1% of the random seeds will give the right output", since that's the definition of probability.
Then running it on ALL of the random seeds will definitely hit those 1%.
@@calvindang7291 I don't think that's quite right from my understanding. Switching from true randomness to a deterministic algorithm means that any given input will deterministically return the same true or false output. But if the non-deterministic algorithm has a 99% chance of being correct for any input, then a 99% accurate deterministic version means 99% of the possible inputs will be correct, and the 1% of incorrect inputs will always be incorrect.
Running against all possible seeds increases the likelihood of getting a correct result, possibly going from 1% up to 99% if you use about 450 seeds, but that doesn't guarantee that any of the seeds would have produced the correct result for that input in the first place.
An 8 bit seed can only produce 2^8 possible sequences. If I use a 16 bit sequence in my algorithm, there are 2^16 actual possible sequences, and it's possible the subset produced by the seed are all wrong.
i mean having a "pi-checking test" is kinda arbitrary, whats wrong with using pi as an rng?
Depends on your use of that pseudorandom value. For security uses, it's too predictable and fails its task.
@@JimBob1937 okay ty
D Sudoku usem 20 Minutä si aber o zimlech eifach 😅
:D
Wait a minute. Why would you say the digits of pi are "not random"? pi is (probably) normal, so all tests for randomness should pass. The fact that it's a well-known number doesn't make it "less random".
Am I missing something?
PS: My head is spinning from trying to understand this video, lol. Fascinating though
Indeed, the generator would pass most tests - but you can construct one that will recognize that the bits you generated are from pi. The fact that such a test exists means that there *could* be scenarios where it matters that your bits are not truly random. For the proof, it's important that there exist *no* such tests so that we can make the conclusion at 13:25.
To be clear, this is mainly important for the proof. In practice, using bits from pi would work for most things - but not everything. You can think back to the poker example. If the players knew that the cards were shuffled using an algorithm that uses some digits of pi, they could exploit that to get a better idea of what card might come next in the deck.
You can think of this as an adversarial setting where the player is your enemy who tries to *exploit* your generator somehow, and you're trying to build one that's not exploitable. Theoretical computer scientists often think about these adversarial setups because they correspond to the worst-case scenario. When you can say that your proof works even in the worst-case scenario, it works for all of them.
Our heads were spinning when we were thinking about this as well, so don't worry haha. Hopefully we got the gist of it across!
if i understood corectly pi digits are "not random" in a way that even if those digits are random they are known, so even if they would pass most randomness tests using a string of those would defeat the purpose of using them
There are many possible tests you could do. Some tests are really bad. For example, you can make a test that reports not random if and only if the output is a string of all zeroes. That's a valid randomness test and will catch any random generator that outputs strings of all zeroes.
Similarly, you can make a test that checks for if your output is exactly "31415926535", or if it's one of some list of strings (say, one for each sequence of 10 digits of pi starting from specific points - but as said in the video, you can't actually compute this check quickly).
The requirement for a pseudorandom generator is to pass **all** possible checks that can be computed fast enough.
```int randomInt(){
return 6; /*obtained from a fair dice roll - guaranteed to be random*/
}```
I think he could have done a better job at explaining what is randomness and that there are two distinct sources of uncertainty.
The 10 bits string 0010101100 is as likely to come up as 0000000000 if each bit is independent and has 50/50 chance. One is not "more random" than the other, this statement actually doesn't make sens on its own. They have both precisely 1/1024 chance to come up. There are adjacent concepts like entropy or Kolmogorov complexity. In the video, it's unclear which definition of randomness is used here. But I could venture and guess it could be something in the likes of:
"An infinite string of bits is random if there is no finite program that can infer a missing digit from the rest of the string with a success probability greater than 50%."
In that sens, pi is definitely not random. We know algorithms to generate its digits.
The other thing that was tentatively explained with the cards example at the beginning is the two distinct sources of uncertainty.
One source of uncertainty is intrinsic to the system. Things you have no way of knowing even given an infinite amount of time because you don't have the necessary information to calculate it. Things like, the result of the fair dice I just threw. The other source of uncertainty is just a limitation of our ability to compute. Like: what's the 99th digit of sqrt(17)? It's not random, it's definitely one of the 10 digits. But with a limited brain ability, you can't compute it in a reasonable amount of time.
Pi is definitely not random and not uncertain in the first sens.
But, if our model has a limited computation ability, then deciding whether a string of digits belong to pi might be much harder, or even impossible. If I understood correctly, assuming it is impossible is the unproven assumption the proof relies on.
Surprise Mario
parallel universes!!!
I think the result is poor and the prize is not well-earned. Here is my justification:
Suppose I implement an SQP solver. These use internally a QP solver. So I test the QP solver with (billions of!!) random instances and it passes them all. Now I plug it into the SQP solver and try solving ten toy problems. Result: The SQP breaks because the QP solver fails at solving some instance posed by the SQP. The SQP is in P and the QP solver is in P. Everything should be great. And my random oracle was even crypto-secure, so it takes fluctutation of my CPU, thus we can assume the random oracle of arbitrary high complexity, say n^(10^100) in the depicted sense (i.e., in that it is as difficult to judge whether it is fake random -- since it isn't). The learning: Algorithms not only depend on the purity of randomness but also on the _kind_ of randomness. In the SQP example, the issue is that SQP use globalizations, which cause certain _kinds_ of QP subproblems that may not be represented sufficiently in other random test batteries. So what computer users in computation have already and ever assumed is that random tests will hopefully cover decisive scenarios to sufficient extent. The contributions of Avi Wigderson do not enhance or safeguard this hope by the slightest. It is rather merely a revelation of himself what we and everyone else has already been doing.
The polynomial equivalence example has the issue that from Gerschgorin circles we can actually construct a sufficiently large integer (yes, indeed, it just has too be large enough, that's all) so that a success of the test gives assertion for equivalence. Also, if we had been to choose a random integer (which is how the original paper proposed the test) then because the number of roots is finite whereas the number of integers is countable infinite, the probablity of the algorithm failing has Lebesque probability zero.
If indeed we look (as suggested from the presentation) into trivial pseudo-random bit-patterns, a.k.a. a list of bits of which each is 50%-50% either zero or one, the amount of algorithms from the class BBP covered by this revelation (for him) is rather diminishingly irrelevant.
PS: Irrespective of my judgement on the scientific contribution, I still liked the video. Well-summarized. Thanks for your effort.
> Also, if we had been to choose a random integer (which is how the original paper proposed the test) then because the number of roots is finite whereas the number of integers is countable infinite, the probablity of the algorithm failing has Lebesque probability zero.
In computer science, integers are typically bounded numbers between 0 and 2^w for some w. So the probabilities of failure are never exactly zero, they are just small if you choose w large enough.
@@PolylogCS I know, hence why the brackets. But then Gerschgorin provides the value of w. But you are right.
Zero knowledge proof
Y not use quantum error in lottery😅😂😂 using three body problem i.e. input chaos.
is there anybody in there
The PRNG presented here is non-educational and can spoil young viewers - PRNG should be initialized... ONCE and used later for longer strings, probably with some bits omitted - if you are using N-length seed to generate 2N or 20N PR string then your app is doomed and can be exploited even on the precompiler level :)
The PRG (and definition) used here is a theoretical one used for proving specifically this statement rather than one made for practical use, though I'm interested in learning more about this; do you have a good resource for this?
> if you are using N-length seed to generate 2N or 20N PR string
I agree that this would be a really bad PRNG :) In our case
1) we go from log(N) bits to N bits, so it's much longer
2) this is a more theoretical than practical endeavor, the PRNG based on pi is not supposed to be practically reasonable, it's more a relatively simple example of how you can invest a lot of time in creating pseudorandom bits and then these bits look random to fast algorithms.
That haircut is random.
that's a random comment...
What a great video!!!
ahoj říšo!
2:50 - and i thought i have a strange look of face 🤪
BS. You only need one transistor to make a REAL random number generator.
random is a myth
Bro you need to go apologize to your barber, you obviously hurt them enough that they needed to get revenge
Everything is deterministic. Nothing is random in the sense of chance. The only context in which probability and randomness make sense is with finite agents who can't predict the way the universe will unfold (which is deterministically) due to complexity or chaos. There's nothing else going on.
I would say that's not true in a mathematical sense and probably not true in a physical sense once we moved from classical to quantum physics.
The probabilistic interpretation of quantum mechanics is commonly accepted, and though the deterministic hidden variable interpretation could be true, as I understand there isn't a compelling reason to believe that over the probabilistic interpretation.
In mathematics, probability is well defined by Kolmogorov axioms, regardless of the physical world. Even purely theoretical concepts can be useful, like the Turing machine with an infinite tape even though the real world has physical limits.
This proof is useful either way though since even if quantum physics is random, real world algorithms use pseudorandom number generators. It's useful to know that even without true randomness, these algorithms can in theory be made deterministic give the same level of correctness.
@@telaferrum "The probabilistic interpretation of quantum mechanics is commonly accepted" No. Only an ignoramus thinks that God "plays dice with the universe". I and Einstein know better.
"True randomness" would mean that the universe has no physics, that causality isn't.
Probability is the uncertainty in an agent's mind about a complex or chaotic aspect of reality, not a reality in the universe about its future.
@@weksauce There's no definitive proof either way. You and Einstein could be right. Physicists more accomplished than you or I have proved that both interpretations could be true.
For computer science purposes, as I said it doesn't matter. Mathematical probability doesn't depend on the physical world, and the proof just becomes more useful if you believe the world is deterministic.
A stochastic universe is hard for many people to accept, but just know that believing in a deterministic one is going against modern mainstream physics. But the mainstream has been wrong before.
I really don't know why people bother demonstrating this for an algorithm in particular when it's easier to demonstrate it in general.
"truly random" can't be a thing in the philosophical sense, since there is no fundamental distinction between the knowledge of all what is truly random and the knowledge of all what is not truly random.
In a nutshell, *if you could eliminate absolutely all predictability from a function, then you would define this function so precisely that it would make it perfectly predictable.*
*Random is, fundamentally, nothing but ignorance.* You can't define what you ignore, by definition.
Quantum physics disagrees. At the quantum level, it is fundamentally probabilistic. Some assumed a local hidden variable explanation for a bit, but that was ruled out. Things like spin states are truly random. This has been used in quantum key cryptography.
This notion works ok for the physical world but I think is mostly irrelevant for theoretical CS because there we can define the fundamental operations of a computer however we want. So for example you can define a perfect coin flip circuit which outputs 0 or 1 with 0.5 probability of each, and which by definition is a complete black box. We have now defined true randomness, given your definition of “randomness is ignorance”, because the computer can’t learn anything about the inner workings of this coin flip generator so will always be ignorant.
Then the question of pseudo randomness is still meaningful because it’s asking: can we drop the black box part of that definition and yet still get the same interface in practice for the rest of the circuit? In other words can you replace unpredictability built into the definition with algorithmic unpredictability?
Unfortunately you use "random" as a synonym for "having an even distribution" and this conflation and imprecision detracts markedly from what is otherwise a high-level presentation. As I am certain you (and probably all viewers) know, for instance a die can be loaded such that it generates 1 - 6 randomly but with a very uneven distribution.
Yes, this is a flawed assumption. Though, for most PRNG, the distribution is designed to be even probability, because this is most useful. However, there are many types of random distributions in the real world that don't have an even distribution.
Even the papers I read on the subject use random to be specifically the uniform distribution, because you just need *a* distribution for randomness and uniform is easy. You can even just transform one distribution to another, usually with good enough accuracy, so there's no reason not to use the uniform distribution.