The hidden beauty of the A* algorithm Polylog 2023-01-20 | 00:00 Intro01:38 Change the lengths!06:34 What is a good potential?12:31 Implementation16:20 BonusTom Sláma's video: youtu.be/umszOeerdsUPatreon: patreon.com/PolylogWebsite: polylog.ccGithub: github.com/polylog-cs/Astar/tree/mainBlog: vasekrozhon.wordpress.com/2024/09/04/the-hidden-beauty-of-the-a-algorithmSome related stuff:-- One thing I did not mention is that Dijkstra's algorithm is designed to solve the problem of finding the shortest path from the start node to all other nodes of the graph. It does this job very well, in almost linear time, so there is not much to improve there. It is the problem of finding the shortest path between two nodes where A* usually improves upon Dijkstra. -- Here is a link to another example of A* run from Sarajevo to east Italy. You can see how the algorithm quickly reaches the first city, Tirana, but then it gets stuck because of the Adriatic sea. So it searches along its coastline until it finds Italy. After that it confidently runs through Italy until it finds the destination. github.com/polylog-cs/Astar/blob/main/Explore.mp4-- If your heuristic is not consistent, but at least admissible, A* will still return the correct answer, though its time complexity may be exponential in the network size. -- IDA* is a popular algorithm that relates to iterative deepening depth first search the same way as A* relates to Dijkstra/breadth first search. -- A perhaps simplest application of potential reweighting technique is the Johnson’s algorithm:en.wikipedia.org/wiki/Johnson%27s_algorithm-- See also this codeforces blog post that collects some applications of potentials in competitive programming. codeforces.com/blog/entry/95823-- The underlying reason why potentials are often so useful is that they are dual to the concept of distances in the sense of linear programming duality. Problems:-- Prove that heuristics from the video are consistent. -- Prove that the maximum of two consistent heuristics is still consistent. (Thus, if you have two incomparable heuristics, you should combine them this way. )-- Prove that for any heuristic that is consistent, equal to zero for the goal state and otherwise nonnegative, A* always explores less states than Dijkstra. That is, apart for the time spent on computing the heuristic, A* is never worse than Dijkstra in the problem of finding the shortest path between two points. Big thanks to: Richard Hladik, Matěj Konečný, Martin Mareš, Yannic Maus, Jan Petr, Vojtěch Rozhoň, Hanka Rozhoňová, Tom SlámaLinks in the video:maps.google.comgeojson.iopublic.opendatasoft.com/explore/dataset/europe-road/export/?refine.icc=BEstackoverflow.com/questions/29470253/astar-explanation-of-nameCredits: To make this video, we used manim, a Python library: https://docs.manim.community/en/stable/ The color palette we use is solarized: ethanschoonover.com/solarizedmusic: Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782music: Also sprach Zarathustra from Strauss from wikimedia commonsimage of the scroll: pxfuel.com/en/desktop-wallpaper-aadkbimages of the cities are from wikimedia commons
What OpenAIs breakthrough means for mathematics Polylog 2026-06-23 | Recently, OpenAI’s model managed to disprove Erdős’s famous unit distance conjecture. We explain the conjecture in depth and talk about what this news tells us about the future of math.Patreon: patreon.com/PolylogWebsite: polylog.ccCode: github.com/polylog-cs/erdos-problemCreditsRichard Hladík: Animator, video editor. Site: https://rihl.czVáclav Rozhoň: Narrator, animator, video editor. Site: vaclavrozhon.github.ioVáclav Volhejn: Narrator, video editor, animator. Site: vvolhejn.comAnimations: Canvas Commons, a TypeScript library canvascommons.io0:00 Intro0:45 Erdős problems1:31 The unit distance conjecture2:09 The asymptotic question3:12 Erdős’s n^1.5 upper bound5:28 Erdős’s n^(1+o(1)) construction7:43 OpenAI's n^(1+ε) construction9:50 Strengths and weaknesses of current LLMs11:22 What happens next?12:26 But we'll still be writing definitions, right?15:09 Outro
How to stop an evil postman (ft. Amit Sahai) Polylog 2026-06-12 | How to communicate securely even if someone listens? A video about the Diffie-Hellman protocol and its generalizations.Full interview with Amit: youtu.be/zWdl6WbcQ_8Patreon: patreon.com/PolylogWebsite: polylog.ccCode: github.com/polylog-cs/impossible-riddleCreditsRichard Hladík: Script editor, video editor, animator. Site: https://rihl.czRomana Hladíková: Video editor.Tomáš Sláma: Animator, script editor. YT channel: youtube.com/@YTomSVáclav Rozhoň: Writer, animator. Site: vaclavrozhon.github.ioVáclav Volhejn: Narrator, animator, script editor. YT channel: youtube.com/@vvolhejnHuge thanks to Amit for suggesting this topic and being so awesome.Thank you to all our beta testers for their feedback: Adrien Ramanana Rahary, Alyx, AT & KBV, Ondra ChwiedziukAnimations: Motion Canvas, a TypeScript library motioncanvas.ioMusic: From the Bodytonics album by Blue Dot SessionsColor palette: Solarized ethanschoonover.com/solarized0:00 Intro0:58 The evil postman riddle01:38 Double-padlock protocol02:46 Translating the double-padlock protocol to software03:35 Take 1: additive double-padlock protocol05:04 Why this breaks06:04 Hardness of the discrete logarithm07:35 Fixing the double-padlock protocol08:40 Diffie–Hellman10:49 Man-in-the-middle11:41 The Internet security stack12:16 Solving the gossip riddle13:55 Oblivious transfer discussion15:06 Outro
99% is easy, 100% is hard Polylog 2026-02-11 | Why is randomness so powerful for algorithms?Patreon: patreon.com/PolylogWebsite: polylog.ccCode: github.com/polylog-cs/99-easy-100-hardCreditsRichard Hladík: Writer, animator. Site: https://rihl.czTomáš Sláma: Script editor, animator, video editor. YT channel: youtube.com/@YTomSVáclav Rozhoň: Script editor. Site: vaclavrozhon.github.ioVáclav Volhejn: Narrator, animator, script editor. YT channel: youtube.com/@vvolhejnFirst presented as a talk at SNiC 2025.Animations: Motion Canvas, a TypeScript library motioncanvas.ioMusic: From the Bodytonics album by Blue Dot Sessions0:00 Intro2:07 Equation testing4:31 Quicksort5:24 Worst case luck / input7:55 Rock Paper Scissors8:30 In conclusion10:04 Thanks
100k Anniversary Livestream 🎉 Polylog 2025-09-03 | We hit 100k subscribers, so we're celebrating with a livestream! 🎉We’ll do a Q&A, solve problems, play games, and rate algorithms together.Ask questions: https://app.sli.do/event/nZgp9V2A9448gKg3EUgCGW/live/questionsTimestamps:0:00 - Stream Start6:25 - Introductions14:23 - Competitive Programming with Václav V.1:04:45 - Algorithm Tier List with Václav R.2:12:30 - Break2:19:56 - Game Bot Programming with Tom S.3:00:37 - Q&A with EveryoneSchedule:19:00 CEST Competitive programming with Václav V.20:10 CEST Algorithm tier list with Václav R.21:20 CEST Game bot programming with Tom S.22:00 CEST Q&A with everyoneLinks:Competitive Programming: atcoder.jp/contests/abc420/tasksTier List: polylog-cs.github.io/tier-listGame Bot Programming: https://cw.slama.dev/
The fastest sorting algorithm Polylog 2025-08-16 | Radix sort is older than the computer yet quicker than quick sort. Why aren’t we all using it?Check out 80000hours.org/polylog for advice on how to choose an impactful career.100k subscribers celebration livestream!! It will start 2 September 2025, 19:00 CEST. We’ll do a Q&A, an algorithm tier list, and small coding games where you can join in. Save the date!Patreon: patreon.com/PolylogWebsite: polylog.ccBlog post: vaclavrozhon.github.io/polylog/radixsortCode: github.com/polylog-cs/radix-sortCorrections09:40 the right punch card is here: vaclavrozhon.github.io/polylog/radixsortMachines from technikum29IBM O83 sorter: https://technikum29.de/en/computer/punchcard.phpPlayer piano: https://technikum29.de/en/miscellaneous.phpCreditsRichard Hladík: Script editor, animator. Site: https://rihl.czTomáš Sláma: Narrator (museum scene), script editor, animator. YT channel: youtube.com/@YTomSVáclav Rozhoň: Writer, animator. Site: vaclavrozhon.github.ioVáclav Volhejn: Narrator, animator, script editor, video editor. YT channel: youtube.com/@vvolhejnThank you to all our beta testers for their feedback: the KSP gang, Carmen Bach.Thank you to Technikum29 for letting us play with their amazing punch card sorter.Animations: Motion Canvas, a TypeScript library motioncanvas.ioMusic: From the Bodytonics album by Blue Dot SessionsObama sort video: youtube.com/watch?v=k4RRi_ntQc8If you wonder why Obama knew bubblesort -- John McCain got the same question a few months earlier, so this was likely a diligent preparation of his team. 0:00 Intro1:12 100k subs celebration livestream1:29 Bucket sort3:18 Radix sort, first attempt4:42 Radix sort, second attempt7:10 But is it fast?8:57 Punch card sorter from 195810:45 Why isn’t everyone using it?11:30 Floating point trick14:30 In conclusion15:38 80,000 Hours16:45 Thanks
A mathematical magic trick Polylog 2025-03-24 | Zero-knowledge proofs: proving that I've solved a Sudoku without revealing my solution.
I can prove I’ve solved this Sudoku without revealing it Polylog 2025-03-16 | I can convince you that I’ve solved a sudoku without giving you any information about my solution. We discuss how to do this using what cryptographers call a zero-knowledge proof, and how the same tricks can be used for almost any other problem you can think of.Patreon: patreon.com/PolylogWebsite: polylog.ccBlog post: vasekrozhon.wordpress.com/2025/03/17/zero-knowledge-proofsCode for the animations: github.com/polylog-cs/zero-knowledge-proofsRichard Hladík: Script editor, video editor, animator. Site: https://rihl.czTomáš Sláma: Script editor, video editor, animator. Channel: youtube.com/@YTomSVáclav Rozhoň: Writer, animator, the verifier. Blog: vaclavrozhon.github.ioVáclav Volhejn: Narrator, animator, script editor, the prover. Channel: youtube.com/@vvolhejnThank you to our beta testers: Matěj, Honza, Filip.Thank you to Gabor Hollbeck for helping with the video equipment.Animations: Motion Canvas, a TypeScript library motioncanvas.ioColor palette: Solarized ethanschoonover.com/solarizedMusic: Astrisx, Cases to Rest, Thannoid, and ZigZag Heart by Blue Dot SessionsMario Speedrun: youtube.com/watch?v=LmgguleEH3k0:00 Intro0:50 Interactive proofs2:28 Graph coloring3:22 A simple protocol6:31 Building the full protocol10:24 Commitment schemes12:37 Reducing sudoku to coloring14:28 General reduction17:04 Discussion19:09 Outro
What P vs NP is actually about Polylog 2024-08-19 | What if we could run algorithms backwards? We discuss how we could do this by turning algorithms into circuits and encoding those into satisfiability problems. We then explain how it all connects to P vs NP. Patreon: patreon.com/PolylogWebsite: polylog.cc#somepi0:48 Satisfiability2:15 Breaking RSA8:46 General reductions to SAT12:03 P vs NPBlog post: vasekrozhon.wordpress.com/2024/08/18/what-p-vs-np-is-actually-aboutCode for the animations: github.com/polylog-cs/np-completenessBlender clip: youtube.com/watch?v=qg1ckCkm8YIRichard Hladík: Script editor, animatorGabor Hollbeck: Video recording, video editorVáclav Rozhoň: Writer, animatorVáclav Volhejn: Narrator, animator, script editorThank you to our beta testers: Matěj, Honza, FilipAnimations: manim, a Python library https://docs.manim.community/en/stable/Color palette: Solarized ethanschoonover.com/solarizedMusic: Thannoid by Blue Dot SessionsPictures:* Intel 8008: righto.com/2016/12/die-photos-and-analysis-of_24.html* Stephen Cook: heidelberg-laureate-forum.org/laureate/stephen-a-cook* Leonid Levin: https://www.cs.bu.edu/fac/Lnd/* Richard Karp: https://www.icsi.berkeley.edu/icsi/people/karp* Mick Jagger, Keith Richards: Wikipedia* Hash function circuit: https://www.academia.edu/download/31149146/498-497.pdf
And this years Turing Award goes to... Polylog 2024-05-11 | We explain why Avi Wigderson got this year’s Turing award: We show how you can make any randomized algorithm deterministic. Patreon: patreon.com/PolylogWebsite: polylog.cc0:00 Intro2:41 P = BPP5:38 Statistical tests7:52 Pi as a PRNG9:44 Nisan–Wigderson PRNG13:47 Finishing the proof14:45 Zero-knowledge proofsBlog post: coming soonCode for the animations: github.com/polylog-cs/derandomizationRichard Hladík: Script editor, animatorVáclav Rozhoň: Writer, animatorVáclav Volhejn: Narrator, animator, script editorThank you to our beta testers: Matěj, Honza, FilipAnimations: manim, a Python library https://docs.manim.community/en/stable/Color palette: Solarized ethanschoonover.com/solarizedMusic: Thannoid by Blue Dot SessionsPictures: Wikipedia, InternetVideo clips used:Avi Wigderson: youtube.com/watch?v=YOrBVEwDqAg and youtube.com/watch?v=ZzsFb-6wvoESeismograph: youtube.com/watch?v=mbKEarx9CCs
The Byzantine Generals problem, and why it matters for the Internet Polylog 2024-02-20 | We solve the Byzantine Generals problem, a fundamental problem of distributed computing. Then, in classic Polylog fashion, we spend the latter half of the video discussing why it matters in the broader context, specifically for distributed databases and blockchains.0:00 Intro0:31 The byzantine generals problem3:51 First solution10:13 Importance12:00 Blockchain-based solution15:57 Wrap-upPatreon: patreon.com/PolylogWebsite: polylog.ccBlog post: vasekrozhon.wordpress.com/2024/03/29/why-arguing-generals-matter-for-the-internetCode for the animations: github.com/polylog-cs/byzantine-generalsFilip Hlásek: Animator, script editor, beta reviewerRichard Hladík: Script editor, beta reviewerVáclav Rozhoň: Writer, animatorVáclav Volhejn: Narrator, animator, script editorThank you to our beta testers: Aashna, Coralie, Frido, Gabi, Jan (hi dad!), Julia, MartinoAnimations: manim, a Python library https://docs.manim.community/en/stable/Color palette: Solarized ethanschoonover.com/solarizedMusic: Thannoid by Blue Dot SessionsPictures: Wikipedia, DALL-E 3, Internet
The flaw in every voting system Polylog 2023-08-10 | A story about the fundamental flaw in every voting system -- strategic voting. We prove a simplified version of the Gibbard-Satterthwaite theorem, the most fundamental theorem of the voting theory. #some3 0:00 Intro3:11 Definitions6:44 Proof11:39 Arrow's theorem13:25 Approval voting17:03 OutroBlog post: vasekrozhon.wordpress.com/2023/09/10/voting-systemsGithub: github.com/polylog-cs/voting-systemsPatreon: patreon.com/PolylogWebsite: polylog.ccCredits:Thumbnail by Alžběta VolhejnováTo make this video, we used manim, a Python library: https://docs.manim.community/en/stable/The color palette we use is solarized: ethanschoonover.com/solarizedComparison of voting systems: en.wikipedia.org/wiki/Comparison_of_electoral_systemsmusic: Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/trac...also a few seconds of Moon Men by Jake Chudnow: youtube.com/watch?v=TN25ghkfgQA&ab_channel=MyContentpictures: MidJourney, Wikipedia, Internet
The most powerful (and useless) algorithm Polylog 2023-04-04 | 0:00 Intro2:44 The Algorithm6:38 Why it works9:28 Code10:41 Final ThoughtsOur implementation of Universal Search: github.com/polylog-cs/universal-search/blob/main/code/universal_search.pyPatreon: patreon.com/PolylogWebsite: polylog.ccImpromptu: https://impromptu.fun/More about universal search:-- To prove that the universal search is asymptotically optimal, we implicitly used the fact that there exists a linear time algorithm for multiplying two numbers. This is true if you work with standard models of computers like the so-called Word RAM or pointer machine (Schonhage's algorithm, see 4.3.3. in Art of Computer Programming). For arithmetic operations, people also often consider a bit different model, where the time complexity of multiplication is O(n log n) (algorithm by Harvey & van der Hoeven).-- A historical note: Levin presented his universal search in the same paper where he presented his discovery of NP-completeness which was independent of Steve Cook. This is why the main theorem about NP-completeness is called Cook-Levin Theorem. The paper of Levin is from early 1970's. Blum's speedup theorem (see next paragraphs) is even older, from 1960's. You can see how people back then thought about these super fundamental questions like "Is it clear that there is an asymptotically best algorithm for every problem?". It turned out that some of the results proven back then (Blum's speedup theorem, universal search) were too abstract to be useful, and it was the concept of NP completeness and related concepts that won and now they form the basis of our theory of algorithms. -- The way we explained universal search, it is applicable only to "search problems" where you are searching for something (factors of a number) and once you find it, it is easy to check that what you found is correct. However, there exists an improved universal search by Hutter that searches not only over all programs, but also over all possible mathematical proofs that analyze those programs. This way, you can get an asymptotically optimal algorithm for any problem you like, except for some absolutely insane cases like when the fastest algorithm cannot be mathematically proven to work (although it works) or the time complexity f(n) is so complicated function that computing the value of f(n) takes more than O(f(n)) time. In fact, Hutter's search can be implemented in such a way that for algorithm with time complexity f(n), it takes only 1.01f(n) + O(1) time (for absolutely humongous O(1)). -- On the other hand, there is a so-called Blum's speedup theorem that says that there exists a certain problem and a certain function f(n) such that you can have algorithms for this problem with complexities O(f(n)), O(log(f(n))), O(log(log(f(n)))) and so on but there is no fastest algorithm. Why is this not contradicting Hutter's universal search? Because this function f(n) is so weird that computing f(n) takes more than O(f(n)) time.Big thanks to: Tomáš Gavenčiak, Matěj Konečný, Jan Petr, Hanka Rozhoňová, Tom SlámaAlso, big thanks to 3blue1brown and the manim community for manim!Credits:To make this video, we used manim, a Python library: https://docs.manim.community/en/stable/The color palette we use is solarized: ethanschoonover.com/solarizedmusic: Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782picture of monkey: DALL-E 2picture of Leonid Levin: https://www.cs.bu.edu/~lnd/picture of Weierstrass and Cantor function: Wikimedia CommonsBrainfuck suggestion: ChatGPTLevin’s quote taken from here: http://www.hutter1.net/idsia/nipsws.htmHe definitely said something similar here: https://www.cs.bu.edu/fac/lnd/expo/qc.htm
The OPTIMAL algorithm for factoring! Polylog 2023-04-01 | Our program:github.com/polylog-cs/universal-search/blob/main/code/universal_search.pyRSA factoring challenge: en.wikipedia.org/wiki/RSA_Factoring_ChallengeBig thanks to: Tomáš Gavenčiak, Matěj Konečný, Jan Petr, Hanka Rozhoňová, Tom SlámaPatreon: patreon.com/PolylogWebsite: polylog.ccCredits: To make this video, we used manim, a Python library: https://docs.manim.community/en/stable/ The color palette we use is solarized: ethanschoonover.com/solarizedmusic: Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782music: Ride of the Valkyries from R. Wagner from wikimedia commons
AI cracked this Codeforces problem. Can you? Polylog 2022-10-06 | Patreon: patreon.com/PolylogWebsite: polylog.ccAlphaCode is a model by DeepMind. alphacode.deepmind.comThe problem we discussed is from CodeForces. codeforces.com/problemset/problem/1566/E0:00 Intro3:29 Problem Statement5:55 Problem Solution11:20 Final ThoughtsMusicNew World Symphony by Dvorak. musopen.org/music/4942-symphony-no-9-in-e-minor-from-the-new-world-op-95/#recordingsImagesThe picture from the thumbnail is by DALLE-2 on prompt“A humanoid robot standing thoughtfully next to a tree with many leaves and buds”The images of dogs and muffins are all over the internet so it is hard to give proper credit there. Codegithub.com/polylog-cs/alpha-codeTo make this video, we used Manim, a Python library developed by 3blue1brown and Manim cumminity. https://docs.manim.community/en/stable/ The color palette we use: ethanschoonover.com/solarizedCreditsBig thanks to Davin Choo, Christoph Grunau, Filip Hlásek, Matěj Konečný, Hanka Rozhoňová, Tom Sláma, Erik Stavarache for a review of an early version of the video.
We designed special dice using math, but there’s a catch Polylog 2022-08-16 | How would you order the players randomly? Tell us in the comments. :)Patreon: patreon.com/PolylogWebsite: polylog.ccSome proposals that already appeared in the comments section:- Put cards with player names in a sack, shuffle, then take them out one by one to get the order.- Simulate the above process using dice (see the comments by Jordan Weitz and samuraiwarm for how to do it).- Just reroll the dice if there are ties. More precisely, the tied guys go to the next round where they decide the order between themselves (or some of them need to go to the third round etc.).- One die with n! sides, write the final permutations on it. The first two solutions are also similar to our solution with cards and to a so-called Fisher-Yates algorithm for sampling a random permutation. If you consider the third solution with coins instead of dice, what it is doing is that each player is basically sampling a uniformly random number from [0,1], bit by bit. Then, they are ordered by the size of sampled numbers. This corresponds to a simple and popular algorithm to create a random permutation: just sample n random reals from [0,1] and order them by size; the probability of ties is negligible. #SoME200:00 Intro06:53 General Construction15:26 Final ThoughtsEric's webpage: http://www.ericharshbarger.org/dice/go_first_dice.htmlAlso: youtube.com/watch?v=L3d0YIW7wHU&t=1s&ab_channel=SHURecreationalMathsResearchClusterThe code for the animations and for finding fair dice: github.com/polylog-cs/fair_dicegithub.com/gavento/permutation-fair-diceTo make this video, we used manim, a Python library: https://docs.manim.community/en/stable/ The color palette we use: ethanschoonover.com/solarizedA few more facts and (open) problems if you are interested:-- You can generalize the lower bound on the number of sides of fair dice for general n; concretely, you can use the prime number theorem (or bounds on the so-called primorial) to show that n same-sized fair dice have to have 2^{\Omega(n)} sides each. -- On the other hand, our construction gives dice with (n!)^{n-1} = 2^{O(n^2 \log n)} sides. It would be interesting to see these two bounds getting closer, if you have progress on that, let us know!-- The lower bound on the number of sides can be generalized to the case when the dice are allowed to have different numbers of sides, then it tells you that for any n fair dice, at least 99% of them have to have 2^{\Omega(n)} sides. But we don't know whether all dice have to have exponentially many sides. -- Suppose I give you a string of length n over alphabet with k letters and ask you whether it is fair. The naive way to check it has time complexity O(n^k). Can you do it in time O(f(k) * n) for some function f?
The Simplest Sorting Algorithm (You’ve Never Heard Of) Polylog 2022-04-13 | Patreon: patreon.com/PolylogWebsite: polylog.ccWe know this beautiful algorithm from the recent preprint by Stanley P. Y. Fung: arxiv.org/pdf/2110.01111.pdfHowever, it turns out that other people stumbled across it multiple times, see e.g. the discussion here:news.ycombinator.com/item?id=28758106------------------------Attributions:To make this video, we used manim, a Python library: https://docs.manim.community/en/stable/ The color palette we use: ethanschoonover.com/solarizedThumbnail contains this version of Raphael’s angelskindpng.com/imgv/iJxhTTJ_raphael-angels-hd-png-downloadMusic: Messiah by Händel en.wikipedia.org/wiki/File:Handel_-_messiah_-_44_hallelujah.ogg
The trick that solves Rubik’s Cubes and breaks ciphers Polylog 2022-02-05 | What do the Rubik's cube and a cipher from the 70s have in common? Let's find out.Patreon: patreon.com/PolylogWebsite: polylog.cc0:00 Rubik's cube9:40 DES------------------------Links:Feliks setting the 4.73 recordyoutube.com/watch?v=R07JiT0PlcE&ab_channel=FeliksZemdegswebpage "God's number is 20" http://www.cube20.orgThe fact it was verified computationally that every cube can be solved in at most 20 moves is super impressive and much more complicated than the problem of solving just one cube that we covered in this video!Four degrees of separation on Facebookarxiv.org/pdf/1111.4570.pdfCode:github.com/polylog-cs/rubiks-cube-video/blob/main/code/rubik_mitm_solution.cpp------------------------Fill in the gaps:Convince yourself that the meet in the middle algorithm finds the shortest path!Convince yourself that the meet in the middle algorithm for Rubik's cube does not need to know that every cube can be solved in 20 steps. ------------------------Real Algorithms:The first algorithms solving a random scramble like Korf's algorithmhttps://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdfwork roughly as follows:First, although there are around 10^20 possible cube configurations, if you focus on just the possible configurations of 8 corner cubies, the number of possibilities drops to around 10^8. Using breadth first search, you can precompute for each such configuration of corner cubies how many steps you need to put them into the correct position. You need at least that many steps to solve the full cube configuration, probably even more as you need to solve not just the corners but also the edges. You can now iterate a breadth first search from your scrambled cube, each time looking into further distance from it. For each cube you look up in your table of size 10^8 to find how many steps, at least, are needed to finish the search. If it is more than the current maximum distance you are looking at, you stop searching, as you can be sure you will not find the solved cube in this branch of the breadth first search. This approach is similar to the meet in the middle algorithm in that we first precompute some information from the solved cube and then run breadth first search from the scrambled cube. However, now you need much less memory. The actual state of the art algorithms are more complicated than that. You can read more about it e.g. here. en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube------------------------More Connections:The meet in the middle trick is also called "bidirectional search" in the context of searching graphs. en.wikipedia.org/wiki/Bidirectional_searchComputing the exact number of states of a Rubik's cube (we used it is around 10^20) is not so hard. youtube.com/watch?v=z2-d0x_qxSM&ab_channel=JPermThe graphs where the number of nodes in your distance grows exponentially are pretty important in computer science. For example, there are scale-free networks and expander graphs. en.wikipedia.org/wiki/Scale-free_networken.wikipedia.org/wiki/Expander_graphTriple DES is kind of a hack made to prolong the life of the DES cipher when it became apparent that it is not strong enough. However, because of the meet in the middle attack, its "security level" is only 2*56 bits and not 3*56 bits as one would naively expect. But you still need to apply DES three times. So you can guess it is not the most efficient way of doing the encryption; it is now superseded by the so-called AES standard. en.wikipedia.org/wiki/Advanced_Encryption_Standard------------------------Riddles:If you like to solve algorithmic puzzles, here you can find more algorithmic problems that can be solved with this technique:youtube.com/watch?v=18sJ3mK173s&ab_channel=Errichto2https://wiki.algo.is/Meet-in-the-middleTry to prove, just with pen, paper and calculator that there is a cube for which at least 16 moves are needed to solve it. Try to convince yourself that by blind search of the cube graph you cannot beat the sqrt(N) time, at least if you do not use anything else than that the graph "looks random". Hint: Birthday paradox------------------------Attributions:To make this video, we used manim, a Python library: https://docs.manim.community/en/stable/The color palette we use: ethanschoonover.com/solarizedPhoto of Grant Sanderson:youtube.com/c/grantsandersonThumbnail: Alžběta Volhejnová
How to Use Beads and Strings to Find the Diameter of a Tree Polylog 2021-08-22 | This video was made for the Summer of Math Exposition 1. Check out other cool videos there!3blue1brown.com/blog/some1#some1 Patreon: patreon.com/PolylogWebsite: polylog.ccTo make this video, we used manim: https://docs.manim.community/en/stable/Our video is based on the following great book:Explaining Algorithms Using Metaphorsby Michal Forišek and Monika Steinováyou can buy it here: https://www.springerprofessional.de/en/explaining-algorithms-using-metaphors/17933980:00 Intro0:40 Trees6:19 The algorithm7:43 Why it works-----------------------------------------------------------------------------------------------Fill in the gaps:It is a good exercise to fill in the missing gaps in the proof sketch that we gave in the video, where we focused on a particular tree instead of analyzing our algorithm in full generality. For example: we started by observing that if we hang a tree by its longest path, its nodes are contained in a triangle. How is this fact used in the actual proof?Also: it can help with understanding the algorithm to consider the case when the tree is simply a path. What else follows from the triangle picture:The one or two nodes that are in the middle of the top edge of our triangle (see the end of the video) are also called the center of the tree. They have the following properties (formally, you would use one of these to define the center of the tree):- The center is in the middle of any longest path of the tree- Leaves are the nodes with just one connection. If you repeatedly remove leaves from the tree (in each step, you remove all current leaves, in the next step the nodes that became leaves, and so on), the center is the last remaining node(s) before the whole tree is removed. - Eccentricity of a node is the distance to the farthest node from it. The center is the node(s) with minimum eccentricity.Fun Riddles: - Compute eccentricities of all nodes of a tree with an algorithm with linear time complexity (=number of steps at most some constant times number of nodes)- Compute the number of longest paths in a tree with an algorithm with linear time complexityMore Connections:A more general question is: what is the diameter of a general network (there, diameter = longest distance between two nodes in it). This problem can be again solved by a naive algorithm that iterates over all nodes and finds the farthest node from each one. There is a substantially faster algorithm that uses similar ideas to those we saw in the video. The downside is that the algorithm is only approximate. If the true answer is D, it returns some number D’ that satisfies 2D/3 ≤ D’ ≤ D. That may seem unsatisfactory, but we know that if there is a nontrivial algorithm with at least slightly better approximation than the one above, something similar to P=NP happens (whether P=NP is the biggest problem in computer science and is considered unlikely to be true). The relevant paper: https://people.csail.mit.edu/virgi/diam.pdf-----------------------------------------------------------------------------------------------Attributions:The color palette: ethanschoonover.com/solarizedTree stump: creazilla.com/nodes/12939-tree-stump-clipartLicense: creazilla.com/pages/11-creazilla-open-source-licenseDrake meme: the guy in the photo is some singer: youtube.com/watch?v=uxpDa-c-4Mc&ab_channel=DrakeVEVO License: fair use, hopefullyRuler: pixabay.com/vectors/ruler-metric-measure-length-4113045License: pixabay.com/service/licensePhoto of Pál Erdős: commons.wikimedia.org/wiki/File:Erdos_budapest_fall_1992_(cropped).jpgLicense: creativecommons.org/licenses/by/3.0/deed.enA book: http://www.clker.com/cliparts/I/O/x/x/4/8/open-book.svgLicense: http://www.clker.com/disclaimer.htmlA tree: illustoon.com/?dl=383License: illustoon.com/help.phpBacteria tree adapted from: commons.wikimedia.org/wiki/File:TreeActinobacteria.svgLicense: en.wikipedia.org/wiki/Public_domainCover of the book Explaining Algorithms Using Metaphors: amazon.com/Explaining-Algorithms-Metaphors-SpringerBriefs-Computer/dp/144715018XLicense: fair use, hopefully
