Відео

thanks a lot. very simple and clear explanation.

wow, you should call it "bubble sort"

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.

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

Surprise Mario

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?

8:40 finding the k+1 ... k+nth digits of pi doesn't require finding the first 1...k digits.

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

Do the video where you do the zero knowledge proof with who is watching to prove you got right sudoku now

Hans Reichenbach: The Concept of Probability. Read it for a philosophical discussion of one of humanity’s most useful concepts that has no real philosophical basis and no empirical basis in reality.

I have learned and subsequently forgotten how zero knowledge proofs work far too many times

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.

The hair.

This is a very important discovery for mathematics at the same level of Fermat last theorem and Poincaré conjecture

Does this have any applications in ml?

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.

subscribed. well done

BS. You only need one transistor to make a REAL random number generator.

What about the electric bass?

Awesome video. Thanks

Fantastic presentation, glad the UA-cam algorithm recommend this channel to me

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

The pannenkoek reference was fantastic

Zero knowledge proof

parallel universes!!!

Okay. As an amateur programmer, I'm trying to get my head around how we actually Dijkstra navigate the graph without actually storing the whole graph in memory - for something like the Tile Puzzle, with 10 trillion nodes, we would clearly have to do this, since storing the map is not viable. As such we translate a Puzzle State into a Node along with its Potential (using the 'optimistic distance' as out potential as suggested in the video). We then interpret every legal move as an 'edge' to-from the State Node we're at and a 'nearby' State Node. When Dijkstra removes the Start node and adds in all its 'neighbors', that is the first time those neighboring nodes exist; we have to generate these new State Nodes and, at the same time, determine if it is a Node that already exists - the only way I can think to do this is by comparing it to every previously generated State Node. With a good Potential function, we should not add too many more nodes than we need to, so the 'neighborhood' of nodes to check should remain relatively small. More to the point, the only nodes being stored in memory at once time are those that are at any point part of the Neighborhood (or Boundary in the code). Is there a good way to estimate the Memory Impact of the algorithm as a function of size of the input space (in a similar way that we estimate Runtime in that big-Oh way?). At the end of the process, we have only acknowledged the existence of a tiny fraction of the total graph, and used the structure of the puzzle itself as a way to directly 'compute' the base edge lengths and the Potentials on an as-needed basis, which is pretty genius. It also cleanly explains why having an edge with a negative length would break the algorithm entirely, because the choice of how to expand the neighborhood depends on the fact that you are always getting 'further away' from the starting point in a global sense; that the length of your 'best current path' is always increasing, which is violated if a path-length can be negative. I would love to see some example where the appropriately well-chosen Potential could be used to fix the negative path length problem.

Was that a 2 CHF coin you used? ;)

random is a myth

What is the assumption? that is the most important part of the proof.

Well done

thats a cool mathematical video, finally not something elementary

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?

I subscribed midway through this video. Too good.

Conditional expectations or pairwise independence, but why not both?

so this algorithm only can be applied assuming the node position can be fitted into a map ? i imagine for more complicated node we can make a 3d map of it or whatever dimension needed, but if the question is, how can you compute their position for arbitrary node weight ?

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.

Get a hairstylist

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

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?

I hope to see your bass play in the next random video

So you never sajd what this "condition that everyone believes" is. Pathetic

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.

That haircut is random.

What a great video!!!

Holy cow this video is great. Makes me feel like I could’ve come up with this proof. 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!

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.

that's great, but... is the assumption true? or is this a kind of "assume RH; then blah" type of result?