The Vulcan in Me

Readers, here is a puzzle adventure in naive physics and topology. The author respectfully denies being a Trekkie. Enjoy!

***

I graduated last in my class at Starfleet Academy. Not much of a story, so don't ask. Anyway, you probably know what came next: it was either find a civilian job or go guard some worthless corner of deep space.

But I'm not exactly sociable, so I took the assignment with no hesitation. Sure enough, it was a real plum: I was put in charge of two monitoring stations (practically bathroom-sized, one of which I controlled remotely) orbiting neighboring stars, with nothing else even close.

For two years, there was nothing but silence as I idled there, chuckling at my fate and deepening my acquaintance with some bootlegged Romulan ale. Then, finally, something happened. I got an alert:

"Reports of extremely massive unidentified vessel, may be in your sensor range. Report: are gravitational readings consistent with null hypothesis (no vessel)?"

I almost panicked. I hadn't checked the sensors in ages, and I didn't even begin to remember how to interpret the readings--how did gravity work again? If I asked I'd definitely be canned. I fumbled through my old Academy lecture notes, struggling to penetrate the chicken-scratch handwriting and the alien sex doodles everywhere. Here is what I was able to recover:

1) Newton's laws govern the universe; quantum mechanics and other such exotic junk were conclusively disproved in 2247.

2) The world contains massive point-particles; the gravitational field at a point in space is the vector sum of its gravitational attractions to all point-masses. Beyond a critical range and below a critical mass, these attractions can be assumed zero. (so I could discard the mass of myself, the two monitoring stations, and everything beyond the two stars and, maybe, this weird vessel... all of which I could model as point-masses.)

3) The gravitational attraction v to a mass m felt by a point p in space is a vector pointing from p in the direction of m, with magnitude w*f(d), where w is the mass of m, d is the distance from p to m, and f is a function given by...

...but I couldn't make out the formula for f; it was totally obscured by a lascivious Ferengi.

Still, I'm not as thick as you think. I reasoned that this much is true:

4) f, the function governing the magnitude of the attraction, must be continuous, positive, and decreasing on the positive real numbers, tending to infinity as d goes to zero, and tending to zero as d approaches infinity. That is, it looks something like this:



Now, the readings from my two stations looked something like this:



(s[1], s[2] are the two stations, and v[1], v[2] are the two gravitational field readings.)

The picture's not much to go by--the vectors didn't all lie in a plane together, and I can't swear by the magnitudes I drew. The thing to notice is that a, b were obtuse--of that I'm sure.

Recall that there were definitely two stars kicking around in the vicinity. Don't ask me how massive they are; it was on record somewhere, but I was too frazzled to even look up the numbers. Also, my windows were frosted over and I had no way of getting a bead on the stars' position. The question was, could some placement of those two masses have generated the gravitational field readings?

What can I say... I may be lazy, but I'm also one-eighth Vulcan, and my genes chose that do-or-die moment to kick in. I confidently delivered my report: "Readings consistent with null hypothesis."


Well, they never found that vessel; still, doing my duty with flair like that was a high point for me, despite my usual tendency to shirk. But two more years have passed, and all this booze has given the Vulcan in me a sore beating.

So help me remember--how the hell did I know what to say?

Define 'Rope'

Random food for thought:

You want to climb to the top of a very tall hanging rope (never mind what's up there). You expect to get tired along the way, too tired to continually grip with your hands. How do you do it?

Gadgets, harnesses, etc. are permissible. I don't have any magically clever solution in mind, only some crude, untested thoughts that for the safety of impressionable youth I'll keep to myself. Also, I asked a friend who says this is a solved problem in rock-climbing circles.

What interested me as I thought about this is how the requirements and mental verification process resembled algorithms work. The climber wants to loop thru a basic routine to create progress ("climb-a-bit"), with a safety invariant ("securely fastened") assumed at the beginning of the routine and reestablished at the end. Efficiency-type considerations also come in play--the amount of rope around the climber's body and the complexity of its arrangement and manipulations should stay bounded.

I've never done engineering, and maybe these analogies are pervasive enough that my observation would seem vacuous to someone in-the-know. Still, it's nice to dabble in problems that have conceptual affinities with math I study without necessarily being reducible to math.

What is the Poincare Inequality, Really?

This post is a cry for help.

OK, it's more of a request for information. First, let me explain what I know, which I hope will be enough to be an informative post about graph expansion in its own right.

I've been reading off and on about Fourier analysis of Boolean functions for awhile, and recently in the context of Property Testing towards giving the talk I posted, where it is really the elegant way of analyzing the linearity test. Afterwards I was doing some random online course exercises, and stumbled on a good one here, by Ryan O'Donnell.

Here's a proof for exercise 1, whose statement I'll rephrase:

'Poincare Inequality': Let (A, B) be a partition of the Boolean n-cube into two sets. Let p be the fraction of the cube's edges going between A and B (vertices are connected by an edge if at Hamming distance 1). Then,

p >= 2|A|*|B|/(n*2^{2n}).

First, what does this say? If the cube were a 'totally random' graph, and A, B were a 'totally random' partition of the vertices, we'd expect a 2|A|*|B|/2^{2n} fraction of the edges to go between A and B.

So, while ill-chosen partitions of the cube can induce sparser cuts than randomly chosen partitions of random graphs, Poincare says these can only be sparser by at most a factor of n. In this sense, the cube is robustly interconnected; not on a par with strong expanders, but to a nontrivial extent. An example that shows the inequality can be approximately tight is to let A be the vectors with first coordinate 0.
(Note: this is the 'extremal example' for edge expansion on the cube, whereas letting A be the set of vectors with Hamming weight at most k gives extremal examples for 'vertex expansion'... for more on the latter, see my June 2006 post.)


Proof: Pick x, y uniformly at random from the cube. The probability q that one is in A,the other in B (we don't care which one is in A) is exactly 2|A|*|B|/2^{2n}.

On the other hand, choose also a random monotone path P between x and y. The probability that x, y lie in these distinct sets is at most the probability that at least one of the edges on P goes between A and B (call this a 'mixed edge'), since the first event implies the second.

The path has edge length at most n, and each individual edge that appears is uniformly randomly distributed over all edges of the cube (though there is dependence in the joint distribution), so there is a mixed edge with probability at most n*p--here we are using the union bound.

So q = 2|A|*|B|/2^{2n} <= n*p, or

p <= 2|A|*|B|/(n*2^{2n}). QED.


What was interesting about this proof for me was that I had used the same idea once before, to show a seemingly different type of result to the extent that

"If an n-by-n 0/1 matrix is 'reasonably balanced' between 0s and 1s, it has either 'many' only-slightly-less-balanced rows, or 'many' only-slightly-less-balanced columns."

(It's easy to see you must allow this choice of rows-or-columns in the statement.)

Looking back at that proof, which was just the one I described but now with length-2 paths instead of length-n ones and n-element hyperedges in place of edges, I realized that result too was 'about' (hyper-)graph expansion. The proof technique also could apply to cases where the edges along the random path are not uniformly distributed, but merely almost-uniform.

I also know, however, that Poincare was working in a very different mathematical milieu, one which, while aware of the importance of isoperimetric inequalities (as this sort of thing can be considered, and the most famous historical example of which being the result that circles have minimal perimeter among planar figures of a given area), was not to my knowledge pursuing expander graphs per se. So what was the larger 'story' of which Poincare's Inequality originally played a part?

Update: My question about the inequality still stands; however, I've found work in the literature that puts my proof of the inequality in perspective. The argument looks to be a simple variant of something called the 'canonical paths' technique, that has successfully shown the good expansion properties (or the weighted version, 'conductance') for much more complex structures; Jerrum and Sinclair are two prominent names in this area, and Jerrum wrote an excellent chapter in 'Probabilistic Methods for Algorithmic Discrete Mathematics' which has been getting me up to speed in this area. I hope to post more about this soon.

More Parity Puzzles

...because I'm odd that way. Both are in the same 'can-do' spirit of the last one, yet neither use quite the same techniques; still simple.
Guaranteed correct, 'cause they're not mine, but lifted from the problem sets I'll credit.

1. Two delegations A and B, with the same number of delegates, arrived at a conference. Some of the delegates knew each other already. Prove that there is a non-empty subset A' of A such that either each member in B knew an odd number of members from A', or each member of B knew an even number of members from A'.

2. Given a finite set X of positive integers and a subset A of X, there exists a subset B of X, such that A are precisely the elements of X that divide by an odd number of elements of B.

(Hint: not a number theory puzzle.)


First is from the 1996 Kurschak Competition (Hungarian), via the Kalva site (see sidebar). Second is from the book '102 Combinatorial Problems' by Andreescu and Feng. Enjoy!

For the Dim Bulbs

After the (n+1)st Sangria spill on your dirty shag rug, and after learning on good authority that wasabi green is officially hip, you've resolved: it's home improvement time.

You rustle up a few pals and get to work, and a few hundred dollars later the place is looking like less of a dive, but in a moment of belated clarity you realise that only one thing needed to be changed to cement its 'cool' status:

just install 'The Clapper' in every room in the house.

For those too young to remember the Clapper heyday, this device controls the on/off switch to a lighting source, and toggles its position when you clap in the audible range--which, for added value and amusement, tends to extend at least into adjacent rooms. For our purposes, let's say the device's range is exactly its host room and those directly adjacent. So, say you've got one light source per room, each with a Clapper, in a house which, like any good house, is actually just an m-node undirected graph.

Now, for your grand house-rewarming party, you invite all your friends over, wait until their thinking skills are nice and clouded, and issue a challenge: clap the house into a fully-lit state.

In fact, no matter what your house's structure, this challenge can always be met, as long as lights are initially off! Can you prove it?


I came up with this result a few years ago after playing a computer solitaire game, which presented this problem for a 5-by-5 square grid (don't recall if there were diagonal connections... anyone have a weblink?). Thought I was pretty clever, but then I saw it given as a problem in an old math journal, I think an AMS one (I'll post a ref if I ever find it). No fancy tools needed to solve this fairly simple puzzle, although of course some linear algebra would help.

Extra Credit: Now the lights all have k > 2 brightness settings, which you cycle thru with claps. Prove it's possible to get them all to the brightest setting. Extra credit, think of a less hasty and more true generalization.

Extra Extra Credit: Now some of the lights are off/bright, while some are off/dim/bright. Now it's no longer always possible to get all lights bright simultaneously. In fact, I'm guessing it's NP-complete to maximize the number of bright lights, but haven't proved this. What's the story?

Oh, and the wasabi-green tip came to my attention (briefly!)in a recent New Yorker.

SATisfaction guaranteed

Or some such lame pun... Folks, this post is yet another puzzle. It should be pretty easy for anyone who knows a certain famous combinatorial Lemma (which I'll name in the comments section). To everyone else, this is a chance to rediscover that lemma, and do a little more besides; I think that, approached with pluck, it should be solvable--but not easy.

The puzzle is to give an efficient algorithm to decide satisfiability (and to produce satisfying assignments when possible) of a restricted class of boolean formulae. They are going to be k-CNFs, that is, a big AND of many ORs, each OR of k variables from {x[i]} or their negations {~x[i]}.

As stands this is NP-complete, even for k = 3. Here is the extra restriction on instances: for every subset S of k variables, there is an OR clause C[S] which contains each variable from S exactly once, possibly negated, and no other variables. (So, these SAT instances are fairly 'saturated' with constraints.)

For example, the property that a bit-vector contains at most k-1 ones can be written this way: for each variable-set S = {x[i_1], ... x[i_k]} of size k, we include the constraint

C[S] := (~x[i_1] OR ~x[i_2] OR ... OR ~x[i_k]).


That's the problem statement--get to it!

Where Are The Puzzles?

I am not a number theorist--far from it. It's not just that I suspect I wouldn't be very good (though there's that): while I admire its beauty, depth, and growing applicability, on a basic level I don't 'buy in' to the scenarios it presents--they don't seem real and urgent in the way theoretical CS problems do (and I say this despite being almost equally far in my tastes from 'applied' math).

But I don't want to rag on number theory, or give a polemic in favor of my field. I want to point out a sense in which number theorists seem to have it really, really good, and ask whether TCS people could ever work themselves into a similar position.

Number theorists live in a towering palace of puzzles. I don't think any other branch of math, not even Euclidean geometry, has produced such a wealth of problems. A meaningful diversity, too, in terms of range of difficulty, types of thinking and visualization involved, degree of importance/frivolity, etc. This has several benefits to the field:

i) supports more researchers, and researchers of varying abilities and approaches;

ii) gives researchers ways to blow off steam or build their confidence before tackling 'serious' or technical problems in number theory;

iii) provides more 'sparks' for theoretical development and conceptual connections;

iv) gives young mathematicians plenty of opportunities to cut their teeth (the Olympiad system seems to produce 18-year-old number theorists of demoniacal skill);

v) provides good ways to advertise the field to the public and entice in new young talent.

Feel free to chime in with other possible benefits--or maybe you think puzzles are a detriment (I've heard this expressed); if so I'd also love to hear from you.


I'm not anxious to hammer down what a puzzle is, or the exact role they play in scientific fields (others have tried); but I would like to get a better sense, in the specific case of TCS, of where the puzzles are or why they are fewer in number (I'm not saying there are none). Towards that end I'd like to first point out what may be a salient feature in number theory's success: it possesses at least one powerful generative syntax for puzzle-posing: namely

Find solutions to F(x, y, z, ...) = 0,

where x, y, z are integral and F is a polynomial, exponential function, etc. You can just start inventing small equations, and before too long you'll come across one whose solution set is not at all obviously describable, and worth puzzling over.

Now, complexity theorists have a pat explanation why this is so: solving Diophantine equations is in general undecidable, maybe even hard on average under natural distributions (?). But, though amazing and true, I think it's a sham explanation. Diophantine equations somehow manage to be (for number theorists at least) interesting on average, meaningful on average, and actually pertinent to the life of the field. (number theorists--am I wrong?)

So where in CS is there a generative scheme of comparable fertility? Are there inherent reasons why CS as we know it could not support such a scheme? Is CS too 'technical', too 'conceptual' to support that kind of free play? Or is it simply too young a field to have yielded up its riches? What do readers think?


I don't want to suggest that there aren't good puzzles and puzzle-schemas kicking around CS (contests, too, though weighted towards programming); there was a period when "prove X is NP-complete" was virtually my mission statement (though it gets old, I gotta say... and we should also admit that some of the best puzzles in any field are likely to be ones that don't fit any familiar scheme). You should also check out the impressive efforts of Stanford grad student Willy Wu, who has a cool collection of riddles, many about CS, and a long-running forum devoted to posing, solving, and discussing them.