33
$\begingroup$

When trying to explain complexity theory to laypeople, I often mention randomized algorithms but seemingly lack good examples to motivate their usage. I often want to mention primality testing but the standard randomized algorithms don't admit a simple description (or proof of correctness) in a lay-atmosphere. I often resort to the saying that randomized algorithms allow "finding hay in a haystack", but that has little mathematical substance.

The question: Is there a good example of a problem that:

  • is easily explained (and sufficiently interesting)

  • has a simple randomized algorithm

  • appears non-trivial to get an efficient deterministic algorithm

and ideally also satisfies:

  • the randomized algorithm has a somewhat understandable proof of correctness - so no Markov/Chernoff/random-walk-mixing-times
$\endgroup$
9
  • 2
    $\begingroup$ For a long time primality testing was the archetype of a problem in BPP (via Miller-Rabin) not known to be in P. Of course that's obsolete now but you still have testing to see if a polynomial is zero... $\endgroup$ Sep 9, 2010 at 23:50
  • 12
    $\begingroup$ I like the question. I'm just wondering about what you mean by laypeople, and what kind of layperson needs a proof of correctness in conversation. ;-) $\endgroup$ Sep 10, 2010 at 0:44
  • 5
    $\begingroup$ Polynomial identity testing is probably the best example. (was mentioned by Steve) $\endgroup$
    – user5810
    Sep 10, 2010 at 0:54
  • 4
    $\begingroup$ Polynomial identity testing seems like the simplest example to me. Be prepared to spend some time explaining why it isn't easy. (Short polynomial expressions can become exponentially long when expanded.) $\endgroup$ Sep 10, 2010 at 2:08
  • 6
    $\begingroup$ Despite what you say, I think primality testing is a good example. You can tell someone that for any composite number n and for roughly three quarters of the numbers m up to n, there is a simple test you can do on n and m that will prove for you that n is composite. But since you don't know which numbers m work, you have to resort to looking for them randomly. It would also be possible to give an idea of what the test is, but proving that it works would be too hard. $\endgroup$
    – gowers
    Sep 11, 2010 at 7:00

19 Answers 19

45
$\begingroup$

Michael, how about approximating the volume of some shape in $\Re^n$ by sampling random points?

This example has the following advantages:

  • It seems easy enough to explain at a cocktail party (depending, of course, on the guests).

  • It's used constantly in "real life" (indeed, pretty much any Monte Carlo simulation in physics, etc. could be interpreted as solving this problem).

  • We don't know how to derandomize it. Indeed, the problem is easily seen to be PromiseBPP-complete (assuming of course that whether a point $x \in \Re^n$ belongs to the shape is decidable in polynomial time).

$\endgroup$
20
$\begingroup$

I love the following example: approximating pi. Ask a person to come up with a relatively efficient algorithm to compute the digits of pi, and unless they already know some math, most will draw a blank.

Here's something that anybody with a basic geometry background will understand: Simply generate many random 2D points (x,y) in the box [-1,1]x[-1,1], and count the number of points within distance 1 of 0 (call this number A) and the number of points in the box total (call this number T).

You can then approximate pi with $\pi r^2 /4r^2 \approx A/T$, but $r=1$, so $\pi \approx 4A/T$.

$\endgroup$
6
  • 2
    $\begingroup$ Buffon's needle is fun too in this regard. $\endgroup$ Sep 10, 2010 at 17:29
  • 1
    $\begingroup$ As is Buffon's noodle. $\endgroup$
    – dvitek
    Sep 10, 2010 at 18:18
  • 4
    $\begingroup$ "Buffon's noodle" is also fun to say. $\endgroup$ May 3, 2011 at 21:56
  • 2
    $\begingroup$ This algorithm is more obviously correct than Buffon's needle, though. $\endgroup$
    – Max
    May 5, 2011 at 9:39
  • $\begingroup$ can't say it's really motivating... $\endgroup$ Dec 28, 2015 at 15:13
10
$\begingroup$

While this requires the use of approximation as well as randomization, I always find the idea that you can get a good estimate of a population by sampling a constant sized set to be very non-intuitive and powerful. The way I usually phrase it in class is: you want to poll the population so that any reasonably popular group is represented. If "reasonably" popular" is defined as a constant fraction, then you only need to sample a constant number of people to hit all groups. Judging by how the general population gets confused by polls, this seems like a good example.

Another example that's more useful for a "CS-aware" layperson is one that requires knowledge of the notion of a median. You can get a quick and dirty approximation for the median in constant time by sampling (in fact, the median of THREE random elements suffices), and the more you sample, the better the approximation.

Probably the most spectacular demonstration of the power of randomness, but one alas that isn't easy to prove to a layman, is the power of two choices. It seems almost impossible that it's true, but it is.

$\endgroup$
10
$\begingroup$

[EDIT: disclaimer! I probably shouldn't have posted this answer, because it's nowhere near my area of expertise; so beware, it may contain nonsense!]

[EDIT: sorry; I saw this nice problem in a book, but it seems a nice deterministic algorithm in $O(n (\log n)^4)$ time was found later, so this answer is inapplicable; reference:

Matching nuts and bolts by Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky;

citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103 ]

The "nuts and bolts" problem, which I saw just a few days ago in the Algorithm Design Manual [precise reference to follow when I get time to edit]:

You are given $n$ pairs of nuts and bolts, all very slightly different sizes (so, each nut fits exactly one bolt); but unfortunately they have all been disassembled, and you have to fit them together.

You cannot see the difference in size by eye, so the only way to see if a nut fits a bolt is to try it. If a nut is too large/small for a bolt, you will discover this; but note that you can't compare two nuts, or two bolts, with each other directly.

Abstractly: we have 2 real unknown sequences $(x_1, x_2, \ldots, x_n)$ and $(y_1, y_2, \ldots, y_n)$.

The $x_i$ are all distinct, and $(y_j)$ is an unknown rearrangement of $(x_i)$. We want to match them up, but the ONLY measurement we can make is to pick $i,j$ and compare $x_i$ with $y_j$.

The obvious algorithm of trying all of them one-by-one takes $O(n^2)$ time.

However, a variant of randomised quicksort takes $O(n \log n)$ time on average. The randomness just comes from picking each nut/bolt at random.

Details: pick a nut, use that as the pivot element for the bolts; then use the matching bolt as the pivot element for the nuts, etc. - like quicksort, but going back-and-forth between $x$ and $y$ elements.

$\endgroup$
2
  • $\begingroup$ Not clear why the deterministic algorithm is better --- it is slower, and surely much more complicated. After all, there are deterministic sorting algorithms but in practice everyone uses quicksort. $\endgroup$ May 5, 2011 at 10:59
  • $\begingroup$ I confess I know almost nothing about this area, so it was unwise of me to post this answer. Maybe I'd better not comment any more about it, because I will probably say something stupid! $\endgroup$
    – Zen Harper
    May 6, 2011 at 0:42
7
$\begingroup$

I like the non-technical examples given by Anup Rao in this essay: http://docs.google.com/Doc?id=dq6zxpq_473cvj8ggfx

It's available from his website

He gives two example of randomized algorithms, one of them is an example of an interactive proof system with the zero knowledge property.

$\endgroup$
1
  • $\begingroup$ As I commented below, I don't like the max-cut/vertex-cover results because they aren't too much harder than the derandomized versions. But I do really like Anup's directed connectivity story, and it plays nicely with the SL=L result of Reingold. Of course, it doesn't have an easily-explained correctness proof, but it is a nice story at least (about steady-state distributions, etc). Still hoping for a better answer though ... $\endgroup$
    – miforbes
    Sep 10, 2010 at 5:25
7
$\begingroup$

If you're willing to flex a bit on "non-trivial to get an efficient deterministic algorithm" (or at least on the definition of "non-trivial"), max-cut is a very easy one. Given a graph $G=(V,E)$, the aim is to partition $V$ into $(V_1,V_2)$ to maximize the number of edges between $V_1$ and $V_2$. Picking a random partition into sets of equal size -- up to parity -- gives you something that on average has at least half the edges of the graph, so is on average at least halfway to optimal.

This example is also nice in my view because the Goemans--Williamson algorithm, the algorithm achieving the best-known approximation ratio (and best possible assuming a certain complexity result) for the problem, about 0.878, is also randomized. (It can be derandomized using the method of conditional expectations, but at a fair cost in terms of ease of explanation.)

$\endgroup$
2
  • $\begingroup$ I know I'm being picky here, but I suppose I'm looking for an algorithm to solve a problem exactly. But further, I don't consider the "derandomized" 2-approximation algorithm for max-cut to be non-trivial - it is just a greedy/conditional-expectation result. (also, the randomized algorithm shows existence apriori, and to get efficiency we need a Markov-type result; not hard but not easily to explain to a layperson) $\endgroup$
    – miforbes
    Sep 10, 2010 at 5:23
  • $\begingroup$ Well, it depends on who it is supposed to be non-trivial to. I think the greedy procedure is harder to explain to a layperson than the random one. Also, I imagine the layperson who has a hard time with Markov is also unlikely to be raising questions about efficiency when you give them the existence proof. But it's true that it isn't exact. $\endgroup$ Sep 10, 2010 at 10:11
7
$\begingroup$

How about using Monte Carlo for deciphering encrypted messages? This paper by Diaconis deciphers a prison message that involves prison lingo, multiple languages, bad spelling and centers around a prison slashing. The younger TV-detective-show obsessed crowd will love it. The algorithm is very simple. Showing precise rate-of-convergence estimates is a bit if a mixing time problem, but perhaps they can take it on faith?

I remember reading it a while ago and feeling inspired by random algorithms. I'll be honest I know very little cryptography, but it seems to me that the given problem in the reference can ONLY be solved by a randomized algorithm. The fact that it converges so quickly and even has a moderate window for "data corruption" (such as bad spelling and different languages) really makes you appreciate the power of this stuff.

$\endgroup$
5
$\begingroup$

This suggestion is not quite as good as Scott Aaronson's, but the following expected time $O(n)$ algorithm for the smallest enclosing circle (also known as minimum spanning/covering circle/disc) of a set of $n$ points in the plane definitely meets the requirements.

Problem: Given are $n$ points in the plane, $p_1,\dotsc,p_n$. Find the circle of minimal radius that encloses all those points, i.e., all points are in the interior or on the boundary of that smallest circle.

Algorithm: The algorithm itself was introduced in the following article:

Emo Welzl, Smallest enclosing disks (balls and ellipsoids). New results and new trends in computer science (Graz, 1991), 359–370, Lecture Notes in Comput. Sci., 555, Springer, Berlin, 1991.

The document is accessible via CiteSeer.

Let $P$ and $R$ be finite sets of points, possibly empty. We describe a recursive procedure $MD(P,R)$ that tries to compute the smallest circle that encloses $P$ and such that all points in $R$ lie on the boundary. Of course, in general such a circle need not exist (say $R$ contains more than 4 points that are not cocircular or the points of $R$ are strictly in the inside of the convex hull of $P$). Note that a circle is already determined by any 3 distinct points on its boundary. Anyhow, that will not be a problem as we call the procedure only for $R=\emptyset$ and $P=\{p_1,\dotsc,p_n\}$.

Definition of $MD(P,R)$:

If $P=\emptyset$ or $\operatorname{card}(R)=3$, then directly calculate and return $MD(\emptyset,R)$.
Otherwise, take a random point $p\in P$ and recursively calculate $D:=MD(P\setminus\{p\},R)$.
If $p$ is enclosed by $D$, return $D$.
Otherwise, return the recursively calculated $MD(P\setminus\{p\},R\cup\{p\})$.

It is possible to cast this in a short and efficient iterative computer program. Regarding the randomization, it actually suffices to randomly shuffle the points only once. Also note that the method can be generalized to higher dimensions and ellipses.

Deterministic algorithms: The obvious try-every-circle brute-force algorithm runs in $O(n^4)$. It is not hard to come up with some improvements, but starting by calculating the convex hull first already results in $O(n\log n)$ at best (at least in usual models of computation). Anyhow, there exist deterministic optimal $O(n)$ algorithms, but they are (as far as I know) quite involved and not used in practice. See Wikipedia or this webpage by Rashid Bin Muhammad.

Reasonably simple analysis: Only elementary geometrical considerations are required to prove the correctness of the algorithm. They are easily justified to laymen (maybe even more easily than to experts). To prove the expected time complexity, a simple backward analysis argument is employed. This basically uses that the smallest enclosing circle is unlikely to change if a random point is removed. See the above article for details.

$\endgroup$
1
4
$\begingroup$

I sometimes mention the efficient generation of expander graphs. In layspeak, an expander graph is "a network where every node is connected to say only 5 other nodes, but you have to cut a million such connections in order to separate two substantial portions of the network from each other". It is possible to generate large expander graphs explicitly, but this is very far from trivial (see Lubotzky, Phillips and Sarnak); on the other hand, in an appropriate sense, a random large network is amazingly good.

(how do you make a random network with 5 neighbors per node? start by imagining that each node is made up of 5 pebbles, pair up the pebbles randomly, and merge the pebbles into nodes).

This is an algorithm-to-generate, not an algorithm-to-decide, but this shouldn't cause too much trouble with most layfolks.

$\endgroup$
4
$\begingroup$

If you are willing to sacrifice the non-trivial deterministic requirement, then I would suggest the Deutsch-Jozsa problem. To summarize: you are given a black-box $f: \{0,1\}^n \rightarrow \{0,1\}$ it is promised that either $f$ is constant or balanced (i.e. $|f^{-1}(0)| = |f^{-1}(1)|$). You have to tell me which it is. The randomized algorithm works exponentially faster than the deterministic one, and has small error.

The best feature is that if you want to continue and mention quantum algorithms, you can do so to recover an error-less algorithm.

$\endgroup$
1
  • $\begingroup$ Deutsch-Jozsa is very much a query problem, and as such always feels too unnatural to try to motivate over a dinner with friends (which is approximately my target audience). $\endgroup$
    – miforbes
    Sep 10, 2010 at 5:28
3
$\begingroup$

Why not mention evolution? It looks very similar to a (still running) random algorithm and its current output does not seem without interest.

$\endgroup$
3
$\begingroup$

Ant algorithms to determine and select the best path from one place to another; ant algorithms can also be used to select the goals along with the paths.

Ant trails and pheremones are easy to describe. Every one has seen them and it's fascinating to explain how miniscule ant-brains can carry out a parallel distributed algorithm that can also be used to select the best routing path on the internet or for a quick and dirty solution to the traveling salesman problem.

$\endgroup$
3
$\begingroup$

Nobody has mentioned the Solovay-Strassen primality test? It's easy to explain (at least with handwaving) that the Jacobi symbol and the modular exponential are straightforward to compute. Then for odd prime n, $a^{(n-1)/2}\equiv \big({a\over n}\big)$ for all bases a, but for composite n, the equality doesn't hold for at least half the bases. So you choose bases at random until you find a compositeness witness or satisfy yourself that you're not going to find one (probability $\le 2^{-k}$ after k tests). I think this was one of the earliest ones? It's very easy to motivate and understand IMHO.

$\endgroup$
1
  • 4
    $\begingroup$ Primality testing was actually mentioned in several comments above. The standard Rabin–Miller algorithm is easier to explain, easier to analyze, and easier to implement than Solovay–Strassen, and it has both a lower probability of error and (somewhat) better running time. In other words, after Rabin the Solovay–Strassen algorithm is but a useless historical curiosity. $\endgroup$ Mar 4, 2011 at 12:01
3
$\begingroup$

Suppose that hundreds of undergraduates have written a test and some people in the department have to score these all with a tight deadline. There are a few tests that are tricky to score and so take more time to score, but you can't tell which ones these tests are in advance without actually scoring them. A professor has to divide the tests among all the teachers so they score them. No teacher should get too many hard to score tests, because then they can't finish even if they work all night.

There's no deterministic method to divide the tests in a fair way. On the other hand, it works fine to shuffle the tests and divide them randomly. (You must shuffle because there are many people who leave after fifteen minutes and write almost nothing are very easy to correct, and often many such tests are clustered together in the stack.)

$\endgroup$
3
$\begingroup$

Multiplication checking: is $ab$ equal to $c$ (or is $a(x)b(x)$ equal to $c(x)$)? Analysis of randomized solution is pretty easy; also it provides a huge gap in asymptotic compared to straightforward multiplication.

$\endgroup$
2
$\begingroup$

I'm not an expert, but I know that for path planning randomized algorithms are very good, and that good deterministic algorithms are very hard to come by. The advantage being that the path planning problem should be easy to explain to lay people.

$\endgroup$
2
$\begingroup$

The randomized algorithm most familiar to newspaper readers is the electoral poll. Polls select a very small fraction of voters and manage to predict the result of an election within a few percent. The hard part is how to sample randomly. But f irst show an example such as finding a volume or computing $\pi$, to avoid getting caught in a political argument.

$\endgroup$
1
  • 2
    $\begingroup$ Polling is mentioned by Suresh Venkat in his answer above; computing pi or a volume are also mentioned by prior answers. $\endgroup$ May 9, 2011 at 12:24
1
$\begingroup$

Input: n

.

Output:

a quadratic nonresidue mod n, if n is an odd prime

0, otherwise

.

.

According to this article, there is a known deterministic polynomial time algorithm for it, although the randomized algorithm really is "searching for hay in a haystack". Furthermore, the article is either wrong or poorly enough known that wikipedia is unaware of it.

$\endgroup$
2
  • $\begingroup$ MathSciNet doesn't list any papers by the author of this preprint. $\endgroup$ Sep 10, 2010 at 9:02
  • $\begingroup$ If the proof for that algorithm is wrong, all the better for this example. $\endgroup$
    – user5810
    Sep 10, 2010 at 9:55
0
$\begingroup$

I would say that the flame fractal algorithm is a monte-carlo way of approximating the invariant measure of a Hutchinson operator. Easy to explain in laymans terms, and produces pretty pictures.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.