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:
• (no subject)

Something that's bugged me for a long time is this: How many paths, starting at the origin, taking N steps either up, down, left or right, end up at…

• (no subject)

Still sad that SAC seems to end up being as complicated as it is. Surely there's some deeper duality between…

• (no subject)

I had already been meaning to dig into JaneSt's "Incremental" library, which bills itself as a practical implementation (in ocaml) of the ideas in…

• Post a new comment

Error

Anonymous comments are disabled in this journal

default userpic