More details here: vasekrozhon.wordpress.com/2024/05/18/avi-wigderson-has-won-the-turing-award/
@estebanmartinez4803
4 ай бұрын
Pelease a video on zero-knowledge proofs. As you said is real mathematical magic!
@cryptonative
4 ай бұрын
Yes!
@nbboxhead3866
4 ай бұрын
We want this, as evidenced by you abbreviating "Please release" to "Pelease". The excitement is real
@meltdown6165
4 ай бұрын
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)
@aleph0x
3 ай бұрын
There's a Numberphile video on ZKP With Avi Widgerson.
@nvjt101
3 ай бұрын
Avi Wigderson himself has a video on Numberphile
@seedmole
4 ай бұрын
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.
@xugro
4 ай бұрын
Our brains are essentially pattern recognition machines so it's not surprising to me that we can detect randomness by using our senses.
@stereosphere
4 ай бұрын
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!
@monad_tcp
4 ай бұрын
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.
@ПендальфСерый-б3ф
4 ай бұрын
@@stereosphere Note that in case of tree generator you are talking about, even perfect random number generator may lead to unnatural results. Because in reality trees don't grow randomly (for example, new tree is more likely to grow in the place, witch is farther from existing trees). For more info look white noise vs blue noise.
@stereosphere
4 ай бұрын
@@ПендальфСерый-б3ф Yes, this is not a very good model of a forest, but good enough for the purpose. The video is at kzitem.info/news/bejne/lIl6mYusaqudjKg. The terrain is from a topo map of an area near the Grand Canyon in Arizona.
@IvanToshkov
4 ай бұрын
Noam Nisan is also one of the co-authors of the excellent "From NAND to Tetris" course.
@PolylogCS
4 ай бұрын
I did not know that one -- looks cool!
@frozzenwaterfall
4 ай бұрын
Love that book!
@IronicHavoc
4 ай бұрын
Pannenkoek Mentioned
@cryptonative
4 ай бұрын
Mentioned mentioned!
@crix_h3eadshotgg992
4 ай бұрын
Appelstroop gepakt
@wickmar3036
4 ай бұрын
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
@krinndnz5767
4 ай бұрын
Thank you; I kept thinking that through the video - "oh COME ON, at least tell us the name of the assumption!"
@anonymousanon4822
4 ай бұрын
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.
@PolylogCS
4 ай бұрын
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.
@nomukun1138
3 ай бұрын
The pinned comment links to a blog post that explains everything very clearly!... I see the pinned comment was posted several days after your comment, but anyone can read it now.
@LukePalmer
4 ай бұрын
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.
@Ceelvain
4 ай бұрын
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.
@PolylogCS
4 ай бұрын
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...
@eqwerewrqwerqre
4 ай бұрын
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!
@eqwerewrqwerqre
4 ай бұрын
*Above statements are about my personal preferences
@Ceelvain
4 ай бұрын
@@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. ^^
@javastream5015
4 ай бұрын
You can transform an optimization problem into a decision problem by asking "Is there a solution with an optimal value
@hdswashere
4 ай бұрын
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.
@Lemon3ea
4 ай бұрын
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
@styleisaweapon
4 ай бұрын
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.
@chiaracoetzee
4 ай бұрын
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.
@calvindang7291
4 ай бұрын
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.
@maheshsoni007
4 ай бұрын
Can you tell us what your project was about
@milckshakebeans8356
4 ай бұрын
" 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).
@calvindang7291
4 ай бұрын
@@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.
@PolylogCS
4 ай бұрын
> 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.
@Bluelightzero
4 ай бұрын
5:52 Literally just finished watching pannenkoek's newest video :D
@PolylogCS
4 ай бұрын
Have you seen the nearly 4-hour one though??
@DemonixTB
4 ай бұрын
@@PolylogCS have you seen the 40 day livestream though?? (i also just finished the latest one lol)
@James2210
4 ай бұрын
@@PolylogCSLoved every minute of it.
@bigbang2a
4 ай бұрын
I liked the video at this exact timestamp ahah ! I love when random parts of KZitem send winks at each other :D
@hydropage2855
4 ай бұрын
The pannenkoek reference was fantastic
@gideonk123
4 ай бұрын
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.
@ethanbottomley-mason8447
4 ай бұрын
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.
@jakeoreilly
2 ай бұрын
man i've been liking maths content recently anyways, but that pannen reference got me to subscribe fr
@andrashorvath2411
4 ай бұрын
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.
@PolylogCS
4 ай бұрын
Thanks!
@Oler-yx7xj
4 ай бұрын
4:24 I never realized before why they always use 10^9 + 7 as the base for modulo in competitive programming questions
@canaDavid1
4 ай бұрын
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.
3 ай бұрын
I loved the Bismuth Mario ABC reference!
@emjizone
4 ай бұрын
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.
@mattshu
4 ай бұрын
Idk why but I’m in love w you
@arisinger8434
2 ай бұрын
I took a course on cryptography last year taught by a professor who was advised by Silvio Micali. One of the most brilliant people I’ve ever met. This stuff is so cool!
@StratosFair
4 ай бұрын
Fantastic presentation, glad the KZitem algorithm recommend this channel to me
@martinkorecek9816
3 ай бұрын
Great video! Technically, the pi-PRNG wouldn't have to be *that* ineffective if it used e.g. the BBP formula rather than generating all k first digits.
@sret919
3 ай бұрын
Thanks for the video
@judyyfong
3 ай бұрын
Btw twin primes conjecture is provable if you relax some mental constraints/parameters and assume that all information is knowable. Such as a reliable way to estimate G the mass of earth by taking in account all the variations as minute spacial differents of the mass, aka G changes based on the viewer’s location.
@judyyfong
Ай бұрын
I changed this comment
@mayankpaneri1295
4 ай бұрын
I subscribed midway through this video. Too good.
@garretmh
4 ай бұрын
I have learned and subsequently forgotten how zero knowledge proofs work far too many times
@rudiklein
4 ай бұрын
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. 🤯
@javastream5015
4 ай бұрын
Hardware generated randomness exists since a long time.
@LarsDonner
4 ай бұрын
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!
@xyphenius9942
4 ай бұрын
Fresh hair, takes courage to rock that
@kokomanation
4 ай бұрын
This is a very important discovery for mathematics at the same level of Fermat last theorem and Poincaré conjecture
@ЯСуперСтар
4 ай бұрын
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
@philipoakley5498
3 ай бұрын
It's worth noting that many of the historic pseudo random generators had a repetition cycle that wasn't large enough to fully explore the possible options in many games of chance such as card games. If worst case, there was never a chance that four aces were not even dealable, so you'd have a lousy game, and it would be easier to fiddle the game. There's a lot of interest in the on-line gambling field about ensuring that overall the house wins, yet it's still 'random' enough. 52 cards, go through all the shuffle orders, once per second, every billion years take a 1cm step along the equator, when you reach the pacific ocean remove a 5mL spoon of water, every time the pacific empties, and a A4 sheet o paper to a pile, when it reaches the moon start actual counting, when you get to a million, realise you are still less than 90% of the way to completing the task. [you need 4 x 64bit words to represent the 52 card deck shuffle number]. And that's not even a 'large' number, never mind an 'arbitrarily large' one.
@JochemKuijpers
4 ай бұрын
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?
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?
@gianlucaspitzer5165
4 ай бұрын
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.
@dominobuilder100
2 ай бұрын
So how do you prove that you’ve solved a sudoku without showing the solution? You got me hooked and I need a video about it now
@riteshbhartiya6155
4 ай бұрын
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.
@me_hanics
4 ай бұрын
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?
@pgmcr5413
2 ай бұрын
What you are describing is a pseudopolynomial algorithm. The polynomial (x+1)^n with fixed n has to be evaluated at n+1 points to check, so the algorithm is polynomial in n. The problem is that complexity classes are about input length and you only need about m bits to describe a polynomial of degree 2^m. For example, i can describe (x+1)^10,000,000,000,000 with only 24 symbols = 8*24 bits, but your algorithm would need to evaluate it at 10 trillion points.
@1238a8
4 ай бұрын
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.
@matta5749
4 ай бұрын
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.
@deepdimdip
4 ай бұрын
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.
@Atrix256
4 ай бұрын
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.
@PolylogCS
4 ай бұрын
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.
@Atrix256
4 ай бұрын
Good point! It being moot is a feature then, and is the whole point. Thanks.
@diadetediotedio6918
4 ай бұрын
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.
@theK594
3 ай бұрын
Can you explain to me how it is possible I have not yet learned about this wonderful channel? Dobrá práce kluci❤🇨🇿
@PolylogCS
3 ай бұрын
Dík :)
@tilmakyaa
4 ай бұрын
Awesome video. Thanks
@ASOUE
4 ай бұрын
Holy cow this video is great. Makes me feel like I could’ve come up with this proof. Thanks
@FloydMaxwell
4 ай бұрын
I will not talk about haircuts ;-)
@PolylogCS
4 ай бұрын
I stand by my choices 🥣🤓
@KrasBadan
4 ай бұрын
Cool haircut, I like it
@legendarybanana37
4 ай бұрын
@@PolylogCS vector
@bakedbeings
4 ай бұрын
@@PolylogCS Do I see the first haircut in the Stroustrup series? Respect 🙇
@abugigi
4 ай бұрын
It can be shown to be the unique haircut which has smooth derivatives of all orders
@antarctic214
4 ай бұрын
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?
@calvindang7291
4 ай бұрын
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.
@PolylogCS
4 ай бұрын
@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.
@matta5749
4 ай бұрын
@@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
@charlessmyth
4 ай бұрын
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. ’"
@jonasbruce
4 ай бұрын
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!
@PolylogCS
4 ай бұрын
Hi, the video is done by a bunch of nerds from Czechia :) -- see video description.
@Egotrippade
4 ай бұрын
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.
@Egotrippade
4 ай бұрын
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.
@maspofu2538
2 ай бұрын
there is no proof for the existance of prgs if I am not mistaken. So this would just proof the implication, that if there were Prgs then it follows that BPP = P.
@vlc-cosplayer
4 ай бұрын
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?
@PolylogCS
3 ай бұрын
One implication of Wigderson's (and Kolmogorov's) work is that I find it philosophically very appealing to think about randomness as being ultimately about unpredictability. Even in the fully deterministic worlds where no "truly random bits" exist, whatever "truly random" means, you can still have construct pseudorandom bits that are for all practical purposes unpredictable and thus random.
@CherryBlossomStorm
24 күн бұрын
Wait. Who actually runs BPP algorithms with truly random numbers? in the real world, random algorithms always use PRNG inputs, right? and no one even thinks about it or cares, the answer is always 'yeah its good enough' im curious about the practical / real-world implications of this when 99% of the time we use PRNGs anyways in datascience/SWE applications.
@PolylogCS
23 күн бұрын
This is mostly theoretical justification of why we strongly believe that, as you say, we don't have to care about true randomness. You could imagine a world where pseudo randomness leads to serious security vulnerabilities but avi explains why that's not the case in our world.
@_hydrogelic
4 ай бұрын
Noam Nisan from Nand to Tetris!!!!!!
@seanconlon4055
4 ай бұрын
subscribed. well done
@VincentKun
4 ай бұрын
Do the video where you do the zero knowledge proof with who is watching to prove you got right sudoku now
@Qstate
4 ай бұрын
Strong typicality is an interesting property
@shafayat1004
3 ай бұрын
11:16 Why is it not 100% certain? If the results ofnthe two expressions are not equal then definitely theynarent equal, right?
@DanielTorres-gd2uf
3 ай бұрын
Parallel Universes Mentioned
@outerskyb
4 ай бұрын
I hope to see your bass play in the next random video
@keyboard_toucher
4 ай бұрын
8:40 finding the k+1 ... k+nth digits of pi doesn't require finding the first 1...k digits.
@SuperLucasGuns
4 ай бұрын
Very nice!
@Paand
4 ай бұрын
thats a cool mathematical video, finally not something elementary
@icusawme2
4 ай бұрын
Well done
@googleyoutubechannel8554
4 ай бұрын
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....
@memoryleak4732
4 ай бұрын
If I can trust wikipedia, then "Under an assumption that most people believe, P = BPP" is very misleading. "[...] They also showed that P = BPP if the exponential-time hierarchy, which is defined in terms of the polynomial hierarchy and E as EPH, collapses to E; however, note that the exponential-time hierarchy is usually conjectured _not_ to collapse." en.wikipedia.org/wiki/BPP_(complexity)#Derandomization
@PolylogCS
4 ай бұрын
More relevant is the sentence after that: Russell Impagliazzo and Avi Wigderson showed that if any problem in E has circuit complexity 2Ω(n) then P = BPP. The result is by Impagliazzo & Wigderson, but the overall result uses Nisan Wigderson generator, so we took the liberty of just talking about Nisan-Wigderson. It is a bit subtle to understand the assumption because the difference between Turing machines and circuits is subtle, but one intuition about the assumption is that it is saying something like "there is at least one problem that can be solved deterministically in exponential time and requires exponential time even if you can use randomness".
@Amonimus
4 ай бұрын
I wonder if something like this can be used in encryption
@Rollmops94
2 ай бұрын
How to create a random number: First you take a random number as a seed...
@kylebowles9820
4 ай бұрын
So they just proved that I can indeed use my low discrepancy sequences in my path tracer lol
@swordfishxd-
4 ай бұрын
cool
@deliyomgam7382
4 ай бұрын
Is formula for circle (c1) x formula for cylinder (c2)= donuts (d) as in topology?? Admin plz do answer.
@johnboyboy919
4 ай бұрын
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?
@telaferrum
4 ай бұрын
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.
@jaimeduncan6167
4 ай бұрын
What is the assumption? that is the most important part of the proof.
@shykj8892
3 ай бұрын
It just confuses me more. I won't question why people pursue the perfect "randomness" because I'm not a scholar, but things happen and while 111111 happens once in 1/2^6 occasions, when it happens it happens. True random number machine might just drop 11111111111111 and casually go on. Like how monkeys playing with typewriters might write a whole hamlet. I'm happy with my hardware noises processed through linear equstions.
@nguyentientrungkien4661
3 ай бұрын
🤯
@gwentarinokripperinolkjdsf683
4 ай бұрын
This of course dosn't hold up when you assume an adversarial algorithm (or parameters the algorithm works upon)
@KaiSong-vv7wh
4 ай бұрын
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.
@PolylogCS
4 ай бұрын
> 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.
@KaiSong-vv7wh
4 ай бұрын
@@PolylogCS I know, hence why the brackets. But then Gerschgorin provides the value of w. But you are right.
@thbaloo
4 ай бұрын
wait that was a 20 minuten newspaper 😯 you live in zurich love your videos
@PolylogCS
4 ай бұрын
Yes! Thank you!
@leofun01
4 ай бұрын
15:00 - sudoku.
@soupisfornoobs4081
4 ай бұрын
True!
@MustacheMerlin
4 ай бұрын
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
@calvindang7291
4 ай бұрын
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.
@mrhassell
4 ай бұрын
Conditional expectations or pairwise independence, but why not both?
@HominisLupis
2 ай бұрын
what a haircut
@morglod
3 ай бұрын
just lol that you can get award for thing that programmers use for 20 years
@TheCaphits
4 ай бұрын
ALGOrithmic RANDomness. Interesting.
@judyyfong
3 ай бұрын
ALGORANDI - ergo randy
@__-de6he
4 ай бұрын
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.
@PolylogCS
4 ай бұрын
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.
@__-de6he
4 ай бұрын
@@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).
@telaferrum
4 ай бұрын
@@__-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.
@andrewsomerville5772
4 ай бұрын
The hair.
@enantiodromia
4 ай бұрын
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.
@PolylogCS
4 ай бұрын
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!
@rtl42
4 ай бұрын
that's great, but... is the assumption true? or is this a kind of "assume RH; then blah" type of result?
@PolylogCS
4 ай бұрын
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. :)
@jamieclarke321
3 ай бұрын
Doesn’t this also prove the converse that truely random numbers don’t exist or can’t be accurately proven to exist with sufficient certainty?
@SSoup64
4 ай бұрын
Does this advance us in finding the elusive solution to the P vs NP problem?
@jobautomation
3 ай бұрын
Just discovered yoour channel. It's a 💎! Thank you very much for your content! Like and Subscribe!!!
@francomarchesoni9004
4 ай бұрын
Nice
@thermidorthelobster4645
4 ай бұрын
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.
@sidharthghoshal
4 ай бұрын
what IS the assumption MOST researchers believe to be true.
@PolylogCS
3 ай бұрын
You can look here: vasekrozhon.wordpress.com/2024/05/18/avi-wigderson-has-won-the-turing-award/
@biquinary
4 ай бұрын
you're cool
@bencrossley647
4 ай бұрын
Does that mean if the 3-SAT problem can be reduced to a BPP polynomial equivalence problem then P = NP?
@PolylogCS
3 ай бұрын
As far as I know, this is not known. But if somebody proved that, I think most complexity theorists would start believing that P=NP at the very least!
@bencrossley647
3 ай бұрын
@@PolylogCSDo you know if this theorem applies to multivariable polynomials or is it limited to the case of 1 variable? If multiple variable polynomials are allowed then I may have something along the lines of 3-SAT -> polynomial -> apply BPP = P. So 3-SAT would be in P. I have 0 excitement over this btw. I'm a mathematician and haven't really studied complexity that much so I highly doubt I'll be the one to stumble across such an important proof.
@fedorryzhenkov4474
4 ай бұрын
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?
@chiaracoetzee
4 ай бұрын
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.
@AE-cc1yl
4 ай бұрын
What is the assumption they use to prove P=BPP? the assumption that most people believe
@calvindang7291
4 ай бұрын
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.
@PolylogCS
4 ай бұрын
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"
Пікірлер: 243