Blog posts on computer science / math
We published our video on zero-knowledge proofs! Surprisingly, making this video took a lot of work. Zero-knowledge proofs for coloring are one of those algorithms that, in hindsight, seem beautifully simple and clean. But that’s just an illusion—there’s actually a lot going on behind the scenes. We struggled with deciding how in-depth to go and … Continue reading Zero-knowledge proofs →
We made a video about a nonstandard way to understand the A* algorithm. This blog post collects a few more clarifications, thoughts, and links. Another Example of a Run of A* Here is another run of A*, this time from Sarajevo (in the Balkans) to southeast Italy. You can notice that at the beginning, there … Continue reading The hidden beauty of the A* algorithm →
We made a video about Levin’s universal search. This blog post collects a few more clarifications / interesting related facts. How to actually make the algorithm asymptotically optimal There are a few subtleties that we need to take care of if we really want to claim that our algorithm is asymptotically optimal algorithm for factoring. … Continue reading The most powerful (and useless) algorithm →
We recently made a Polylog video about a nonstandard way of understanding the P vs NP problem. As usual, our goal was to present an underrated idea in a broadly understandable way, while being slightly imprecise and leaving out the messy technical details. This post is where I explain those details so that I can … Continue reading What P vs NP is actually about →
Recently, Avi Wigderson won the Turing Award (see 1, 2, 3, 4) and we decided to make a video explaining a bit about his work on derandomization. This was definitely one of our most ambitious projects at Polylog. Anything with randomness and complexity theory is inherently hard to explain in 15 minutes, so we needed … Continue reading Avi Wigderson has won the Turing Award →
We made a new video with the Polylog team! This post collects some interesting bits that did not make it into the final cut. Also, we promised a follow-up video with one of my all-time favorite mathematical proofs. Upon some reflection and due to the relatively low number of views of the video, I will … Continue reading Why arguing generals matter for the Internet →
In the book Surely, You Are Joking, Mr. Feynman, Richard Feynman tells a story of how he provoked math students at Princeton by asking them to explain what problems they were working on. He would then tell them pretty much instantly what the answer to their problem is. The catch is: just the answer, no … Continue reading If there is no reason for structure, assume there is none. →
We made a new video with the Polylog team! As usual, there is quite a lot of stuff happening behind the scenes that did not fit in the final video. I decided to put that stuff in a separate blog post to satisfy both interested viewers and myself. If you did not watch the video, you … Continue reading The flaw in every voting system →