Summer of Math Exposition

Great storytelling, and clarity of concepts. Understood a lot without knowing much about algorithms. Gotta say, fine work!

It takes some extra cleverness, but a better explanation would show how you might invent the solution, rather than just suggesting the solution out of nowhere (“Here’s an algorithm idea - Freivalds’”) and going on to prove it

What a good article, let me have a little understanding of randomized algorithms.

Cool! This was a very clear explanation with nice visuals and good motivation. I learned something new and have a better sense of randomized algorithms. For a reader with the assumed prerequisites, it is a solid intro.

A small issue but maybe worth amending: I had to read the lines above equation 3 several times to follow. “Exactly one of…” just didn’t parse for me initially. I was thinking in terms of indices… “Exactly one i? What?” Perhaps phrasing it as “Either… or…” or similar would help.

good visuals

I haven’t taken a probability or algorithms class before, so this article was my first exposure to randomized algorithms. This was fun to read (and all the visuals were very pretty and helpful), and I can get a sense of the feeling of disbelief and wonder that you said you experienced when you first learned about these: I was pleasantly surprised by how much this all just felt like real analysis. The four problems that this article centered around were each interesting in their own rights, and clearly had a role in the article as a whole: the identical matrix problem served as an introduction to/reminder of the notions of time complexity and amplification in randomized algorithms; the minimum cut graph problem really began to make use of discrete probability with an intuitive example (I could follow along most of the way despite never having taken a probability class before); the fast sorting problem introduces the distinction between Las Vegas and Monte Carlo algorithms; and the final reflection on the matrix problem demonstrated an impractical Monte Carlo algorithm. Each of these (except the fast sorting problem) reinforces the motif of 1. defining a deceptively simple algorithm, 2. finding the probability of the algorithm returning a particular event, 3. finding the minimum number of runs of the algorithm required to make the error below some level. Each of these three pieces reminds me of different aspects of solving real analysis problems, so I did come away with a strong sense of what kinds of challenges and joys there are to developing a randomized algorithm! I think this was about the right level for an undergrad student or advanced high school student to read with little stress.

I think one way to improve this explainer is to add a short preface at the beginning of the article, because as it is, if the reader doesn’t know what a randomized algorithm is, they will go into the article mostly blind to what the article is about. Here are some things that I think might be helpful to see in the preface: 1. a description of why one might care about randomized algorithms---something like the little anecdotal blurb you included early on,

“When I first encountered Freivalds’ in my studies, I was in disbelief. How can multiplying the matrices on a random vector give us any sort of confidence on whether the matrices in question are equal? This couldn’t possibly work. It’s too simple for a problem that seems more complicated. But it somehow does work.”

could provide good motivation to learn more! I think this really sums up the charm of randomized algorithms as you introduced them.

 2. a quick description of the three main problems that this article will talk about, and what each of them are for: maybe something like my summary of this explainer in the first paragraph of my feedback?

 3. a description of how certain specific fields might make use of these themes---for instance, how software testers might use randomized algorithms. I say this because if this is intended for people who are in high school/undergrad, a big thing that might be on many of their minds may be what job they can find after graduating!

Finally, I think the conclusion could also use some work; maybe a kind of “big picture review” could be helpful at the end, kind of like the three “motifs” I talked about toward the end of the first paragraph of my feedback?

All in all, this was a fun read!

The tone makes it easy to follow, and I enjoyed reading through the explainer! I do think there was some opportunity for improvement with some of the visualizations - for example, a more dynamic/slow/pace-controller-by-user change in the contracted graph to show how the original graph morphs into the contracted one, and similarly with the Karger’s algorithm visualization. Score is average of the following: motivation 8 (better for first than remaining sections), clarity 9, novelty 5, memorability 5.

The “animations” were all pre-played when I got to them, which I think is fine because animating them didn’t really add anything. Do they need to be animations at all?

Some of the mathematical detail feels extraneous, or at least really slows down reading. Would it make more sense to have derivations in optional footnotes or similar?

The whole thing is quite long, too - could it be split into separate parts? The matrix verification part could be a punchier article on its own, for example.

Where you say “by the handshake lemma” you haven’t introduced the handshake lemma. You could probably just say in words quickly what the idea is. (But, as above, do you need the proof in the main text at all?)

“Using the Master theorem (if you do not know what that is, just trust me on this)” is similar but maybe worse… you could link to a reference instead of appealing to trust.

Clear explanation.