Bijective Combinatorics

I was remarking previously that this blog is meant to be somewhat similar to Terry Tao's blog, but without the associated Fields medal. Maybe a more important difference however, is that while Terry Tao is (still) doing old Math, it seems I am working on the new Math. And what better plot twist could reinforce our community's claim, than to have algorithms become not only the language of science, but the language of Math itself. This post is about an area of Mathematics where this may end up happening soon.

Bijective combinatorics is the area of combinatorics where algorithm is king. To count some set S, we find another set T of known size, and establish an explicit bijection f between them. "Establish" and "explicit" mean we have to give an algorithm for f and one for f ^-1.

The field owes a lot to Richard Stanley, another member of La Familia. (No, we are not a Mafioso group trying to gain control of science, and constantly promoting each other's work. Talk to my lawyer.) The central assertion is that the algorithm is the most beautiful way to understand combinatorial counting -- a normal step is Mathematics' long quest for beauty by one standard or another.

Here are two examples of nice puzzles in the area. If you are only interested in "serious business" skip to the section on the role of CS theory.

Example 1: Prüffer codes. To get a flavor for the technique, let us count the number of trees that can be formed with n labeled nodes (i.e. nodes have personality, 1-2-3 is a different tree from 1-3-2, but the same as 3-2-1). We encode such a tree using an array A[1..n-2] of labels as follows:

for i=1 to n-2:
 L = min {label(v) | v is a leaf}
 A[i] = label(unique neighbor of node labeled L)
 remove the node labeled L from the tree

Exercise (quite fun): Now give an algorithm to reconstruct the tree uniquely from the encoding (an array of n-2 labels). Bonus points if the algorithm runs in time O(n).

This shows there are precisely n^n-2 labeled trees. Like many nice puzzles I know, I first saw this as a problem in the Informatics Olympiad, around 9th grade.

Example 2: Balanced parentheses. The number of strings containing n pairs of balanced parentheses, e.g. (()(())) for n=4, is {2n \choose n} / (n+1). This is known as Catalan's number.

Exercise (not so easy, but rewarding): Show an algorithm that encodes a set of n elements from [2n] into a pair of the form: a number in {0,..n} and a string of n balanced parentheses. Then show a decoding.


Where we come in. All nice and fun. But since algorithms are the words of this corner of science, our challenge is to create metaphors and poems. As it turns out, combinatorialists have some problems they haven't figured out how to solve despite a lot of effort. Some of the most famous ones are about partitions, an area where bijective combinatorics is particularly strong. If you want to dig further, see a survey by fellow Mafioso Igor Pak.

Maybe, just maybe, the reason they can't solve the problems is that no efficient bijection exists. And that would be something great for us to prove, and bring complexity theory to the spotlight.

An immediate question is what "efficient" means. People versed in algorithmic counting (I promise to blog about this another time) will immediately see that we can find polynomial time algorithms. Thus, polynomial time is not the answer here. Maybe the mathematical notion of explicit is more like log-space, or small depth circuits, or whatever.

I worked on the problem briefly a few years back, and talked to Igor Pak about it. He didn't have an ultimate definition for what we want, as common bijections turn out to be in many small complexity classes. But the consensus arose that the initial step is to prove some impossibility, e.g. for small space or small depth, and resolve the deep philosphical question later. (There is always ample time for that, given the sloooow progress that complexity theory tends to make.) Alas I was not successful in proving anything.

Miklós Ajtai. And that was all I heard about the problem, until lunch today, when Mikki Ajtai told me he had been working on it, and thinks he has something. Specifically, the statement seems to be of the form: there are two languages recognizable by AC⁰ such that there is no AC⁰ bijection between them.

Judging from previous examples (like the first predecessor lower bound, parity not in AC⁰, the superlinear lower bound for branching programs, AKS sorting networks, lattice-based encryption, ...) one can hope/expect a result that will:

• be painfully incomprehensible
• preocupy us for at least a decade, until it is distilled into a few brilliant ideas
• forever enter our collective reasoning process and our understanding of CS
• earn a permanent entry in Encyclopedia Informatica

How to get citations

To start lightly, here is a tribute to fellow MIT student Krzysztof (you get free vodka if you can say his name).

While Suresh, Piotr et co are analyzing the value of citations, here is how to get them (see right corner):



Krzysztof calls it a joke, I call it a prank, but in any case it's brilliant. One cannot help think about the time when we'll have a budget category in NSF grants for advertising the publications coming out of the grant. To some extent, NSF already does that by encouraging you to list talks on previous NSF research when applying for a grant.

Ars poetica

The first poem of many classic volumes was an "Ars poetica", a meta-poem about the "art" that the author intended to incorporate into the rest of the poems in the book. So it seems fitting to start a blog in much the same way.

The scope of this blog was mainly decided by pondering the deep philosophical question "who the heck needs another blog?". Almost certaintly nobody in theory, and especially not me as the author.

Despite this, I constantly find myself wanting to fill a void in organizing, publicizing, emphasizing, propesizing about my corner of theory, roughly defined as data structures, nonuniform lower bounds, and interesting topics in CS. So the blog will be just that: a research blog. I hope to review the current state of the art in the understanding of fundamental problems, and review interesting research. Feel free to suggest topics and guest-blog about your favorite topic.

If you will, the model I hope to follow is Terry Tao's blog, though there is a notable difference in that I decided not to wait for my Nevanlinna / Turing / whatever award.

In particular, the blog will contain a minimal amount of meta-discussions about theory (which is perhaps a waste, as I seem to be extremely good at bringing the best/worst out of people with just a few remarks).

Despite my interest in the topics, I will also keep away from trying to find the art or philosophy hidden in life (yes, no battling vaginas here). And despite the fact that my kind of sports (like rugby or rock climbing) might make for more entertaining posts that baseball, they shall be banished from the blog.

PS: the fact that some   bloggers have been very successful in getting jobs this year, and I am graduating in 2008, has nothing to do with me starting a blog.


PS2: The title, yes... Well, I sometimes look like this, ride an ancient motorcycle, travel to a lot of cool places, and hope to start a revolution (in CS). The domain infoweekly stands for Informatics Weekly, and more accurately portrays the topic of the blog.