March 15th, 2010

beartato phd

(no subject)

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!
beartato phd

(no subject)

More progress on ICFP paper.

Yesterday got to hang out with Copic and Spoons since they were nearby in Manyunk visiting Spoons's sister. This is great!

I decided I was getting in a rut piano-wise, and decided to learn some new Actual Music, so I pulled down a free pdf of Maple Leaf Rag. I can kinda play through the first strain at very low speed, but it is fun.

Making some plans to be in pittsburgh 'round SIGBOVIK-time. Trying to arrange giving a POP seminar talk on the topic of Crazy ICFP paper. Should be good times.