Jason (jcreed) wrote,

Barrington's Theorem is a pretty crazy theorem.

It says that any log-depth circuit can be simulated by a polynomial-sized branching program of finite width. Specifically, width 5 suffices. In other words, NC1 = 5-PBP.

This is crazy! Not to mention you can do it in width 2 if you're allowed one qubit.

Why is it crazy? Because we can compute the "majority vote" of n bits with a log-depth circuit: just use the the AKS'83 sorting network to sort them all, then look at which way the middle voter is voting.

So we can do the same with a polynomial branching program of width 5.

In plain English, this means you can conduct a poll over an arbitrarily sized population by only remembering a number between 1 and 5 at any given moment, and cleverly changing this number each time you ask someone a question. You may need to ask people the same question multiple times because of your absurdly limited memory, but no more than polynomially many times, and eventually you'll figure out whether the majority (or any other fixed plurality threshold you might like to decide on at the outset) voted yes or no.

And fundamentally it is because there exist two cyclic permutations τ and σ of a set of five things such that their commutator στσ-1τ-1 is also cyclic, and because there are log-depth sorting networks.

Crazy, I tell you!
Tags: barrington, math, sorting, voting
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded