Various fields have various notions of "nice proofs," be they *combinatorial*, or *elementary*, or *bijective*. In TCS, perhaps the correct standard for lower bound proofs should be "encoding proofs." In these proofs, one starts with the assumption that some algorithm exists, and derives from that some impossible encoding algorithm, e.g. one that can always compress *n *bits into *n*-1 bits.

A normal lower bound will have a lot of big-bad-ugly statements -- "there are at least A bad sets (cf Definition 12), each containing at least B elements, of which at most a fraction of C are ugly (cf Definition 6)". To deal with such things, one invokes concentrations left and right, and keeps throwing away rows, columns, elements, and any hope that the reader will not get lost in the details.

There are 3 huge problems with this:

- Most lower bounds cannot be taught in a regular class. But we can't go on saying how problems like P-vs-NP are so awesome, and keep training
*all*our graduate students to round LPs better and squeeze randomness from stone. - The reader will often not understand and appreciate the simple and beautiful idea, as it is too hard to pull apart from its technical realization. Many people in TCS seem to think lower bounds are some form of dark magic, which involves years of experience and technical development. There is certainly lots of dark magic in the step where you find small-but-cool tricks that are the cornerstone of the lower bound; the rest can be done by anybody.
- You start having lower-bounds researchers who are so passionate about the technical details that they actually think that's what was important! I often say "these two ideas are identical" only to get a blank stare. A lower bound
*idea*never talks about entropy or rectangle width; such things are synonymous in the world of ideas.

Proofs that are merely an algorithm to compress

*n*bits have elegant linearity properties (entropy is an expectation, therefore linear), and you never need any ugly concentration. Anybody, starting with a mathematically-mature high school student, could follow them with some effort, and teaching them is feasible. Among researchers, such proofs are games of wits and creativity, not games involving heavy guns that one may or may not have in their toolkit.***

My paper on lower bounds for succinct rank/select data structures was submitted to SODA in extraordinary circumstances. I had been travelling constantly for a month, and the week before the deadline I was packing to move out of California and down with a flu. In the end, the only time I found for the paper was on an airplane ride to Romania, but of course I had no laptop since I had just quit IBM. So I ended up handwriting the paper on my notepad, and quickly typing it in on my sister's laptop just in time for the deadline.

[ You would be right to wonder why anybody would go through such an ordeal. I hate submitting half-baked papers, and anyway I wanted to send the paper to STOC. But unfortunately I was literally forced to do this due to some seriously misguided (I apologize for the hypocritical choice of epithets) behavior by my now-coauthor on that paper. ]

If you have 8 hours for a paper, you use all the guns you have, and make it work. But after the paper got in, I was haunted by a feeling that a simple encoding proof should exist. I've learnt long ago not to resist my obsessions, so I ended up spending 3 weeks on the paper -- several dozen times more than before submission :). I am happy to report that I found a nice encoding proof, just "in time" for the SODA camera-ready deadline. (As you know, in time for a camera-ready deadline means 2 weeks and 1 final warning later.)

The paper is here, if you are interested.