Andy's Math/CS page

A geometric-graphs offering

2011-09-28T12:35:00.000-04:00

Introduction

After a night of board games, I found myself thinking about the peculiarities of movement on discrete versions of the plane. This suggested a number of questions. As they would likely suffer neglect at my hands, I'm posting them here for others to enjoy---any ideas or references are very welcome.

The basic structure that got me thinking was the 8-neighborhood (or Moore) graph:

This graph (which we'll denote by $G_{8N}$) describes how a chess king moves on an infinite chessboard. It's often convenient for game designers, but there's something... wrong about it: it distorts distances in the plane.

To make this formal, let $G$ be a (finite or countably infinite) undirected graph. Let $d_G(u, v)$ denote the shortest-path distance in $G$ between vertices $u, v$.

We say $F: V(G) \rightarrow \mathbf{R}^2$ is an embedding of $G$ if $|| F(u) - F(v)||_2 \geq d_G(u, v)$ for all distinct vertices $u, v$. (This is just a normalization convention.) Define the distortion of $F$ as the maximum (supremum) of

\[ \frac{|| F(u) - F(v) ||_2}{d_G(u, v)} , \quad{} u \neq v . \]

The study of low-distortion embeddings (which can be pursued in a more general setting) has been a highly-active TCS research topic, largely due to its role in designing efficient approximation algorithms for NP-hard problems. My initial focus here will be on embeddings for periodic and highly-symmetric graphs like $G_{8N}$.

As an example, look at the usual embedding of the 8-neighborhood graph into the plane. This has a distortion of $\sqrt{2}$, witnessed by points along a diagonal.

Warm-up: Show that $\sqrt{2}$ is the minimum distortion of any embedding of the 8-neighborhood graph $G_{8N}$.

Symmetries and Distortion

Now a basic observation here is that, when we started with a graph with a high degree of inherent symmetry, we found that its optimal (distortion-minimizing) embedding was also highly-symmetric. I would like to ask whether this is always the case.

For background, an automorphism of $G$ is a bijective mapping $\phi$ from $V(G)$ to itself, such that $(u, v) \in E(G) \Leftrightarrow (\phi(u), \phi(v)) \in E(G)$.

Let's say that a graph $G$ has 2D symmetry if there's an embedding $F$ of $V(G)$ into the plane, and linearly independent vectors $\mathbf{p}, \mathbf{q} \in \mathbf{R}^2$, such that a translation of the plane by $\mathbf{p}$ or by $\mathbf{q}$ induces an automorphism of $G$ (in the obvious way). In this case we also say the embedding $F$ has 2D symmetry.

So for example, with the usual embedding of $G_{8N}$, we can take $\mathbf{p} = (1, 0), \mathbf{q} = (0, 1)$.

Question 1: Suppose $G$ has 2D symmetry. Does this imply that there is a distortion-minimizing embedding of $G$ with 2D symmetry?

Say that $G$ is transitive if "all points look the same:" there's an automorphism of $G$ mapping any vertex $u$ to any other desired vertex $v$. Similarly, say that an embedding $F$ of $G$ is transitive, if translating the plane by any vector of form $(F(u) - F(v))$ induces an automorphism of $G$. (The usual embedding of $G_{8N}$ is transitive.)

Question 2: Suppose $G$ has 2D symmetry and is transitive. Is there a distortion-minimizing, transitive embedding of $G$ with 2D symmetry?

Question 3: Suppose $G$ has 2D symmetry, and is presented to us (in the natural way, by a finite description of a repeating "cell"). What is the complexity of determining the minimum distortion of any embedding of $G$? What about the case where $G$ is also transitive?

It seems clear that the answers to Questions 1 and 2 are highly relevant to Question 3.

Graph Metrics and Movement

I want to shift focus to another type of question suggested by $G_{8N}$. Let's back up a bit, and think about the familiar 4-neighborhood graph $G_{4N}$. It's not hard to see that the minimum-distortion embedding of $G_{4N}$ also has distortion $\sqrt{2}$. (You have to blow up the grid by a $\sqrt{2}$ factor to make the diagonals long enough.) Yet $G_{4N}$ seems considerably more natural as a discrete representation of movement in the plane somehow. Why?

I think the answer is that, with the usual embedding of $G_{4N}$, the graph distances $d_G(u, v)$ correspond to actual Euclidean travel-distances, under the restricted form of paths in which we confine ourselves to the line segments between vertices. (You can see why this metric is sometimes called "taxicab geometry.") By contrast, the usual embedding of $G_{8N}$ doesn't have this interpretation.

However, consider the following system of paths connecting points in the plane:

If we restrict ourselves to these paths, and if we make those squiggles the right length, then shortest Euclidean travel-distances actually do correspond to distances in the graph $G_{8N}$! This is so, even if we're allowed to switch paths at the crossover points.

So $G_{8N}$ is not totally weird as a discrete model of movement in the plane; it just corresponds to an odder restriction of movement.

More generally, say that a graph $G$, with nonnegative edge-weights ("lengths"), is an obstructed-plane graph, if there is an embedding of $G$ into $\mathbf{R}^2$ along with a set of "obstructions" (just a point-set in $\mathbf{R}^2$), such that shortest paths in $G$ correspond to shortest obstruction-avoiding paths in $\mathbf{R}^2$.

Question 4: What is the complexity of deciding whether a given graph (finite, say) is an obstructed-plane graph?

It simplifies things a bit to realize that, in trying to find an obstructed-plane realization of a graph $G$, the obstructions may as well be all of the plane except the intended shortest paths between all pairs of points. Using this observation, we can at least show that our problem is in NP. Is it NP-complete?

Any planar graph, with arbitrary nonnegative edge-weights, is clearly an obstructed-plane graph. But we've seen that $G_{8N}$, a non-planar graph, is also an obstructed-plane graph. (Quick---prove that $G_{8N}$ is non-planar!) The essence of the problem is to find systems of paths in the plane which, though they may cross, do not introduce any undesired "short-cuts" between vertices.

Now suppose we draw $G$ in the plane, along with a collection of "intended" shortest paths between each vertices. (That is, we will obstruct the rest of the plane, and hope that these paths are indeed shortest in what remains.) We expect that the intended $u$-$v$ path is of Euclidean length $d_G(u, v)$.

A simple observation is that in order to avoid short-cuts, all 4-tuples of distinct vertices $u, u', v, v'$ must obey the following property:

$\bullet$ If the "intended path" from $u$ to $v$ intersects the intended path from $u'$ to $v'$, then

\[ d_G(u, v) + d_G(u', v') \geq d_G(u, u') + d_G(v, v') \]

and

\[ d_G(u, v) + d_G(u', v') \geq d_G(u, v') + d_G(u', v) . \]

Question 5: Is the necessary condition above also sufficient?

In a narrow sense, the answer to Question 5 is No: it's possible to draw a graph in this way and still introduce undesired short-cuts. My real question is whether, from a graph drawing with the property above, we can lengthen and contract the lengths of segments, without changing the topological structure of the drawing, in order to get the desired obstructed-plane realization.

It may be foolish to hope for such a simple condition to be sufficient. Also, an affirmative answer to Question 5 wouldn't seem to imply any new complexity upper bound for our problem (except perhaps to speed up the NP verification a bit). I ask only because I find the question interesting, and wasn't able to cook up any counterexamples in my brief attempt.

Joint computational complexity, and the "buy-one-get-one-free conjecture"

2011-06-15T10:21:00.001-04:00

Below is a simple-to-state open question, stemming from this paper of mine from CCC'09. First, I'll state the question; then I'll give some background, explaining how it's an instance of a more general and significant problem.

The question

Let's consider the standard two-party model of communication complexity. Given inputs x and y to Alice and Bob respectively, suppose there are 3 functions the two parties are interested in evaluating on these inputs---let's call them F(x, y), G(x, y), H(x, y).

Question: is there a collection of total functions F, G, H, and a positive value T, such that:

(i) any one of F, G, H requires at least T bits of communication to compute;

(ii) any two of F, G, H can be computed in (1.01 T) bits of communication, on a common input (x, y);

(iii) but, computing all three of F, G, H on a common input requires at least (1.99 T) bits of communication.

I believe such a collection exists. We can call this the 'buy-one-get-one-free conjecture': Think of T as the individual 'price' of the 'items' F, G, H; we want to arrange a special 'deal' where the second item is essentially free, but one has to pay full-price for the third item.

Now if you think about it, what we're looking for is pretty strange. The function F should be efficiently computable in at least two 'essentially different' ways---one of which also gives us the value of G, and one of which gives H---yet there should be no efficient scheme to compute F that gives us G and H simultaneously. (This property seems easier to contrive when the inputs x, y are assumed to have a special, correlated form; I rule this out by insisting that F, G, H be total functions.)

The question makes equal sense when posed for other models of computation. In my paper, I proved the corresponding conjecture in the decision tree model of computation, as a special case of a more general result--see below. Communication complexity could be a reasonable model to attack next.

Please note: While this conjecture may require lower-bounds expertise to resolve, I believe that anyone with a creative spark could make an important contribution, by coming up with a good set of candidate functions F, G, H. Please feel encouraged to share any ideas you might have.

Background on the question

Let cc(F) denote the (deterministic) communication complexity of computing F(x, y). Next, let cc(F, G) denote the communication complexity of computing F(x, y) and G(x, y)---on the same input-pair (x, y). We define cc(F, H), cc(G, H), and cc(F, G, H) similarly.

Together, we think of these various quantities as summarizing the 'joint complexity' of the collection F, G, H. Of course, this notion can be extended to collections of k > 3 functions; the joint complexity is summarized by giving the communication complexity of all 2^k subsets of the collection. Let's let JC denote the function that takes as input a k-bit vector, and returns the complexity of computing the corresponding subcollection. So, in our 3-function example, we have

JC(1, 1, 0) = cc(F, G) and JC(0, 0, 1) = cc(H).

The question we want to ask is: what kinds of behavior are possible with the joint complexity, if we allow the functions F, G, H, etc. to be chosen arbitrarily? In other words, what different types of 'efficiencies' can arise in a collection of computational tasks (in the communication model)?

A little thought reveals some obvious constraints:

1. the joint complexity function JC must always be nonnegative and integral-valued, with JC(0) = 0.

2. monotonicity: Enlarging the subset of the functions to be computed cannot decrease the complexity. For example, we always have cc(F, G) >= cc(F), which translates to JC(1, 1, 0) >= JC(1, 0, 0).

3. subadditivity: Taking the union of two subsets of functions to be computed cannot increase the complexity beyond the sum of the individual complexities of the subsets. For example, cc(F, G, H) <= cc(F, G) + cc(H), since we can always compute (F, G) in an optimal fashion first, then compute H optimally afterwards.

(Technically, this assumes that in our model both players always know when a communication protocol halts, so that they can combine two protocols sequentially without any additional overhead. No big deal, though.)

Now, a little further thought reveals that… well, there really aren't any other obvious, general constraints on the joint complexity! Let's call C an Economic Cost Function (ECF) if it obeys constraints 1-3. We are tempted to conjecture that perhaps every ECF is in fact equal to the joint complexity (in the communication model) of some particular collection of functions.

There are two things wrong with this conjecture. First, it's false, as can be seen by a simple counterexample: namely, the "buy-one-get-one-free" example, with T set to 1. That's how I stumbled onto this example, and is one reason why I find it interesting.

However, if we relax the problem, and just ask to realize some scalar multiple of C as a joint complexity function, this counterexample loses its force.

The second thing wrong with the conjecture (in its relaxed form) is that, even if true, it'd likely be impossible to prove. This is because determining the exact computational cost of even modestly-complicated tasks is just way too hard. So I propose a doubly-relaxed form of the conjecture: I conjecture that if C is an ECF, then there is a joint complexity function that is a good pointwise approximation to some scalar multiple of C. (Here we allow a (1 +- eps) multiplicative error.)

In my paper, I managed to prove the corresponding conjecture for the model of decision trees (aka deterministic query algorithms). Several interesting ingredients were needed for the proof. Now, why do I believe the conjecture should also hold true for the communication model? In a nutshell, I think it should be possible to 'embed' tasks in the query model into the communication model, by a suitable distributed encoding of each bit, in such a way that the relative costs of all computational tasks are approximately preserved. If this could be shown, the result in the communication model would follow from my result for decision trees. (See the paper for more details.)

We may not be ready for an attack on the general conjecture, however. In particular, we seem to require a much better understanding of so-called 'Direct Sum problems' in communication complexity. Thus, I offer the 'buy-one-get-one-free conjecture' as a simpler, more concrete problem on which we can hope to make progress sooner.

In the decision tree model, my result allows us to realize an ECF of the 'buy-one-get-one-free' type as a joint complexity function; but I don't know of any method for this that's significantly simpler than my general construction. Even finding such a simpler method in the decision tree model would be a very nice contribution, and might lead to new ideas for the more general problem.

An exciting new textbook, and a request

2011-05-09T10:53:00.000-04:00

Today I'd like to put out an appeal to readers. If you have a solid grasp of English and an interest in circuit complexity (no expertise required!), please consider helping proofread the forthcoming book "Boolean Function Complexity: Advances and Frontiers" by Stasys Jukna.

Stasys (whom I recently had the pleasure to meet at an enjoyable Dagstuhl seminar in Germany) is a talented researcher and a kind, gracious person; he's also worked tirelessly to produce high-quality textbooks for our community. I'm a long-time fan of his "Extremal Combinatorics: With Applications in Computer Science" which contains many gems of combinatorial reasoning in complexity theory.

His latest manuscript, to be published soon, promises to be a leading reference for circuit lower-bounds research. Although I've only read parts, it clearly achieves both depth and breadth; I really think anyone in the field could learn something new and useful here.

The main cause for concern is that Stasys (who hails from Lithuania) is not a native English speaker, and the text needs work in places to become grammatically correct and idiomatic. Also, it seems a full-time copy-editor is not available for this project.

So readers: by volunteering to proofread a chapter or two, you'll be doing a valuable service for present and future students of complexity theory. Language editing is the essential thing--you can skim over the equations, so it really doesn't take that long. (Of course, mathematical feedback is also welcome.)

The manuscript is available here; use the following login info:

User: friend
Password: catchthecat

You can email Stasys your comments. The text is long (500+ pages), so if you do or are planning to do some editing, please enter your name, the chapters you'll edit, and a timeframe in the comments below. This will allow others to maximize our coverage of the draft.

Thanks in advance for your help!

Harassment Policies for Theory Conferences

2010-12-10T00:38:00.000-05:00

Following offline conversations and recent discussions on other blogs (hat-tip to Anna and David), I want to promote the Geek Feminism Blog initiative asking computing conferences to adopt explicit policies against sexual harassment. Bringing such policies to theory conferences that don't yet have them is an important step. (Note that this would mean putting them on conference websites and preparing conference staff. Just having some boilerplate document hidden somewhere on the IEEE or ACM websites is not enough.)

What is the value of such a policy? Geek Feminism provides a policy template whose intro spells it out well. Such a policy

"sets expectations for behavior at the conference. Simply having an anti-harassment policy can prevent harassment all by itself...

"...it encourages people to attend who have had bad experiences at other conferences...

"...it gives conference staff instructions on how to handle harassment quickly, with the minimum amount of disruption or bad press for your conference."

Stating such a policy would cost nothing, and local conference staff could prepare for their roles using anti-harassment training materials, which abound on the web -- I invite others to suggest good ones.

So why would we hesitate to adopt such policies? I will suggest three possible reasons, and explain why they're unconvincing.

First, there is a certain tendency to deride anti-harassment training as "sensitivity training" and as stating the obvious. But whether or not most of us know how to treat others respectfully, responding to disrespectful treatment is another story. Conference staff need to know there are circumstances under which they can and should reprimand attendees or even eject them, and they need to mentally rehearse for these difficult tasks. Attendees need to know the staff are ready to help.

Second, some might object that while harassment may be a major problem in other parts of the computing/tech world, it's less of a problem in our mature, enlightened theory community. Of course, this would be a self-serving belief without empirical support. I'm not aware of any systematic efforts to track harassment incidents at theory conferences, although Geek Feminism maintains wiki record of incidents in computing/tech more broadly -- I hope theory conference-goers will find and use it or something similar. But if we can agree that sexual harassment is seriously wrong -- harmful to individuals and the community when it occurs -- surely we can take the time to state this publicly and prepare ourselves to deal with it, whatever its frequency.

Third, might an anti-harassment policy inhibit our freedom of expression too much or make people afraid to interact? Let me turn this question around. Almost all universities and major employers have explicit anti-harassment policies (here's MIT's, for example). Most of us support these precautions and don't feel oppressed by the policies. Why should conferences, which are outgrowths of the academic system, be different? Do we believe there is some special spirit of lawlessness that we need to protect at conferences, and only at conferences?

Of course not. So I support the harassment-policy initiative, and encourage others to do so as well.

ECCC: what authors should know

2010-11-04T13:38:00.000-04:00

Anyone interested in computational complexity should be aware of ECCC, the most important and widely-used online repository for complexity papers. (Depending on your specific interests, various sections of arxiv, along with the Cryptology eprint Archive, may be equally important to follow.)

Unfortunately, the technical side of ECCC's submission process is arguably broken, and seems to trip up many if not most authors. Here are the issues I'm aware of:

1: no preview function.

Unlike arxiv, ECCC offers Latex support for on-site abstracts, so you can have as many funky symbols as you want. Good thing? No, because the site offers no way to preview what the compiled math will look like. This results in bizarre spacing effects and compile errors. (The most frequent problem, I think, is authors trying to use their own custom macros in the abstract, or commands from outside the Latex fragment supported by the site.)

Nor is it possible to preview what your document will look like (assuming it's accepted). This brings us to the second point:

2: hyperrefs are broken.

Many authors these days like to use internal hyperlinks in their document (provided by the hyperref package in Latex). This way, in case the reader forgets what Lemma 14.5 said, there's a link to it every time it's invoked. ECCC is happy to accept hyperref'd papers, and when they appear on the site, they'll have the same appearance you've chosen to give them. Unfortunately, in most cases the damn things won't do anything when you click on them.

Faulkner wanted to print The Sound and the Fury in multi-colored ink. I happen to like the look of colorful hyperrefs, even broken ones, but I still feel like a fool when they're all over a paper of mine.

3: keywords are nearly useless.

There is so little standardization in the use of keywords, and they're handled so rigidly, that clicking on them is often a waste of time. For example, the keywords 'algorithmic meta-theorems' and 'algorithmic meta theorems' bring up one paper each -- two lonely souls separated by a hyphen. (The search tool and the browse-able list of keywords are somewhat more useful, but still probably less so than googling.) Mistyped keywords are another danger. I've also seen author names that, when clicked, bring up a proper subset of that author's work for no apparent reason.

Why does this matter?

I think all this constitutes a serious problem. But one possible objection to my view is that authors can always post revisions to their papers -- fixing abstracts, documents, and keywords in one stroke.

This might be an OK solution, except for the empirical fact that almost nobody does this (myself included). I think, and others have also opined, that this is because people are afraid to revise. Presumably, they fear there's a widespread perception that posting revisions = mistakes or sloppiness.

Whether or not this perception is actually widespread, we should stand visibly against it, to loosen the grip of pointless anxieties and to improve the quality of available papers. A more reasonable attitude is that having early access to preprints is a good thing, but that such papers will almost always have imperfections. Revising a paper within a few weeks or months of its release ought to be a sign of conscientious authors, not sloppy ones. This holds doubly in the context of a messed-up submission system.
Of course, there is such a thing as too many revisions, and it is possible to post a paper too early in the editing process. Where that line should be drawn is a tough topic that deserves its own discussion.

What's the solution?

We can and should expect more from ECCC. Specifically, a preview function for abstracts and documents would be a key improvement. But at the least, there should be a clear list of warnings to authors about common submission errors.

The web administrators are aware of these issues, and have been for some time; but we as users can each do our part to communicate the importance and urgency of fixing these problems. This is especially true of users on the site's scientific board.

In the meantime, what should you do if your submission doesn't turn out the way you expected? Last time this happened to me, I contacted a web admin, a friendly guy who was able to fix part of the problem for me, without resorting to the dreaded revision step. This might work for you as well.

Injective polynomials

2010-07-21T19:27:00.000-04:00

From a paper of MIT's Bjorn Poonen, I learned of an amazingly simple open problem. I'll just quote the paper (here Q denotes the rational numbers):

"Harvey Friedman asked whether there exists a polynomial f(x, y) in Q(x, y) such that the induced map Q x Q --> Q is injective. Heuristics suggest that most sufficiently complicated polynomials should do the trick. Don Zagier has speculated that a polynomial as simple as x^7 + 3y^7 might be an example. But it seems very difficult to prove that any polynomial works. Both Friedman's question and Zagier's speculation are at least a decade old... but it seems that there has been essentially no progress on the question so far."

Poonen shows that a certain other, more widely-studied hypothesis implies that such a polynomial exists. Of course, such a polynomial does not exist if we replace Q by R, the reals. In fact any injection R x R --> R must be (very) discontinuous.

Suppose an injective polynomial f could be identified, answering Friedman's question; it might then be interesting to look at `recovery procedures' to produce x, y given f(x, y). We can't hope for x, y to be determined as polynomials in f(x, y), but maybe an explicit, fast-converging power series or some similar recipe could be found.

Finally, all of this should be compared with the study of injective polynomials from the Euclidean plane to itself; this is the subject of the famous Jacobian Conjecture. See Dick Lipton's excellent post for more information.

Wit and Wisdom from Kolmogorov

2009-08-10T11:29:00.000-04:00

I just learned about a result of Kolmogorov from the '50s that ought to interest TCS fans. Consider circuits operating on real-variable inputs, built from the following gates:

-sum gates, of unbounded fanin;
-arbitrary continuous functions of a single variable.

How expressive are such circuits? Kolmogorov informs us that they can compute any continuous function on n variables. Wow! In fact, one can achieve this with poly(n)-sized, constant-depth formulas alternating between sums and univariate continuous functions (two layers of each type, with the final output being a sum).

Note that sums can also be computed in a tree of fanin-two sums, so this theorem (whose proof I've not yet seen) tells us that fanin-two continuous operations capture continuous functions in the same way that fanin-two Boolean operations capture Boolean computation (actually, even more strongly in light of the poly-size aspect).

This result (strengthening earlier forms found by Kolmogorov and by his student Arnol'd) may, or may not, negatively answer one of Hilbert's problems, the thirteenth--it's not entirely clear even to the experts what Hilbert had intended to ask. But a fun source to learn about this material is a survey/memoir written by A. G. Vitushkin, a former student of Kolmogorov. [a gated document, unfortunately...]

The freewheeling article starts off with Hilbert's problem, but also contains interesting anecdotes about Kolmogorov and the academic scene he presided over in Moscow. Towards the end we get some amusing partisan invective against Claude Shannon, who, scandalously, "entirely stopped his research at an early stage and still kept his position of professor at the Massachusetts Institute of Technology". Vitushkin (who passed away in 2004) apparently bore a grudge over the insufficient recognition of Soviet contributions to information theory. My favorite story relates a not-so-successful visit by Shannon to meet Kolmogorov and features a deft mathematical put-down:

"Kolmogorov was fluent in French and German and read English well, but his spoken English was not very good. Shannon, with some sympathy, expressed his regret that they could not understand each other well. Kolmogorov replied that there were five international languages, he could speak three of them, and, if his interlocutor were also able to speak three languages, then they would have no problems."

Going to CCC09?

2009-06-25T15:14:00.000-04:00

I posted this request on Bill and Lance's blog, but I'll ask again here: anyone want to share a room in Paris for CCC09? I should've asked earlier, of course; still, if you're interested, post a comment or email me: adrucker at mit dot edu.

Additive combinatorics: a request for information

2009-05-20T10:22:00.000-04:00

Given a subset A of the integers mod N, we can ask, how many 4-element `patterns' appear in A? A pattern is an equivalence class of size-4 subsets of A, where two 4-sets S, S' are considered the same pattern if S = S' + j (mod N) for some j.

Clearly the number of patterns is at most |A|-choose-4; but it can be much less: if A is a consecutive block, or more generally an arithmetic progression, the number of patterns is on the order of |A|^3.

So my question is: if the number of patterns is `much less' then |A|^4, what nice structure do we necessarily find in A?

I believe that similar questions for 2-patterns have satisfactory answers: then the hypothesis is just that the difference-set (A - A) is small. In this case I believe A is 'close' to a (generalized) arithmetic progression, although actually I'm having trouble finding the relevant theorem here too (most references focus on sumsets (A + A), for which Frieman's Theorem applies).

Thanks in advance for any pointers!

Algebraic and Transcendental

2009-03-24T15:45:00.000-04:00

A number is called algebraic if it is the root of a nonzero polynomial with integral coefficients (or, equivalently, rational coefficients); otherwise it is transcendental.

Item: there exists a nonintegral c > 1 such that c^n 'converges to the integers': that is, for any eps > 0 there's an N > 0 such that c^n is within eps of some integer, for all n > N. (I think the golden mean was an example, but I can't find or remember the reference book at the moment.)

Item: it is apparently open whether any such number can be transcendental.

***

Next up, two questions of my own on algebraic numbers. Possibly easy, possibly silly, but I don't know the answers.

Define the interleave of two numbers

b = 0.b_1b_2b_3... and c = 0.c_1c_2c_3...
(both in [0, 1], and using the 'correct' binary expansions) as

b@c = 0.b_1c_1b_2c_2...

1) Suppose b, c are algebraic. Must b@c be algebraic?

2) The other direction. Suppose b@c is algebraic. Must b, c be algebraic?

In both cases, I am inclined towards doubt.

***

Final thoughts (and these are observations others have made as well)... computational complexity theory seems to have certain things in common with transcendental number theory:
-an interest in impossibility/inexpressibility results;

-markedly slow progress on seemingly basic
questions--is (pi + e) irrational? does P = NP?

-attempts to use statistical and otherwise 'constructive' properties as sieves to distinguish simple objects from complicated ones.

So, could complexity theorists benefit from interacting and learning from transcendental number theorists? If nothing else, looking back on their long historical march might teach us patience and an appreciation for incremental progress.

A Rather Elegant Solution

2008-12-03T17:53:00.000-05:00

So I'm co-writing a survey paper for a course project, and struggling with the conflicting demands of completeness and brevity. As if charmed, while taking a break I happen upon a '99 paper called "50 years of Bailey's Lemma" by S. Warnaar whose abstract really resonates:

"Half a century ago, The Proceedings of the London Mathematical Society published W. N. Bailey’s influential paper Identities of the Rogers–Ramanujan type... To celebrate the occasion of the lemma’s fiftieth birthday we present a history of Bailey’s lemma in 5 chapters...
Due to size limitations of this paper the higher rank [42, 40, 43, 41, 14, 60] and trinomial [11, 59, 19] generalizations of the Bailey lemma will be treated at the lemma’s centennial in 2049."

Excitement and Probability

2008-10-31T10:36:00.001-04:00

Elections, sporting events, and other competitions can be exciting. But there is also a sense in which they are almost always dull, and this can be proved rigorously. Allow me to explain.

(What follows is an idea I hatched at UCSD and described to Russell Impagliazzo, who had, it turned out, discovered it earlier with some collaborators, for very different reasons. I wouldn't be surprised if it had been observed by others as well. The proof given here is similar to my original one, but closer to the more elegant one Russell showed me, and I'll cite the paper when I find it.)

I want to suggest that a competition is dull to watch if one side is always heavily favored to win (regardless of whether it's the side we support), or if the two sides muddle along in a dead heat until some single deciding event happens. More generally, I'd like to suggest that excitement occurs only when there is a shift in our subjective probabilities of the two (let's say just two) outcomes.

Without defending this suggestion, I'll build a model around it. If anyone is upset that this notion of excitement doesn't include the smell of popcorn, the seventh-inning stretch, or any substantive modelling of the competition itself, there's no need to read any further.

Assume we are a rational Bayesian spectator watching a competition unfold, and that we receive a regular, discrete sequence of update information $X_1, X_2, ... X_n$ about a competition (these update variables could be bits, real numbers, etc.). Let $p_0, p_1, ... p_n$ be our subjective probabilities of 'victory' (fixing an outcome we prefer between the two) at each stage, where $p_t$ is a random variable conditioning on all the information $X_1, ... X_t$ we've received at time $t$.

For $t > 0$, let's define the excitement at time $t$ as $EXC_t = |p_{t} - p_{t - 1}|$. This random variable measures the 'jolt' we presume we'll get by the revision of our subjective probabilities on the $t$th update.

Define the total excitement $EXC$ as the sum of all $EXC_t$ 's. Now, we only want to watch this competition in the first place if the expected total excitement is high; so it's natural to ask, how high can it be?

We needn't assume that our method for updating our subjective probability corresponds to the 'true' probabilities implied by the best possible understanding of the data. But let's assume it conforms at least internally to Bayesian norms: in particular, we should have $E[p_{t + 1} | p_{t} = p] = p$.

An immediate corollary of this assumption, which will be useful, is that

\[E[p_t p_{t + 1}] = \sum_p Prob[p_t = p]\cdot p E[p_{t + 1}|p_t = p]\]
\[= \sum_p Prob[p_t = p]\cdot p^2 = E[p_t^2].\]
OK, now rather than look at the expected total excitement, let's look at the expected sum of squared excitements, an often-useful trick which allows us to get rid of those annoying absolute value signs:
\[E[EXC_1^2 +EXC_2^2 + \ldots + EXC_{n }^2]\]

\[= E[(p_1 - p_0)^2 + \ldots + (p_n - p_{n - 1})^2 ] \]

\[= E[p_0^2 + p_n^2 + 2\left(p_1^2 + \ldots + p_{n - 1}^2\right) \]

\[ \quad{}- 2\left(p_1 p_0 + p_2 p_1 + \ldots + p_n p_{n - 1} \right) ] \]

\[= E[p_0^2] + E[p_n^2] + 2(E[p_1^2] + \ldots + E[p_{n - 1}^2)] \]

\[ \quad{} - 2(E[p_0^2] + \ldots + E[p_{n - 1}^2] )\]

(using linearity of expectation and our previous corollary). Now we get a bunch of cancellation, leaving us with

\[= E[p_n^2] - E[p_0^2].\]

This is at most 1. So if we measured excitement at each step by squaring the shift in subjective probabilities, we'd only expect a constant amount of excitement, no matter how long the game!

Now, rather crudely, if $Y \geq 0$ and $E[Y] \leq 1$ then $E[\sqrt{Y}] \leq 2$. We also have the general '$\ell_1$ vs $\ell_2$' inequality
\[|Y_1| + ... + |Y_n| \leq \sqrt{ n \cdot (Y_1^2 + ... + Y_n^2)} .\]

Using both of these, we conclude that
\[E[EXC_1 + \ldots + EXC_n] \leq E\left[\sqrt{n \cdot \left(EXC_1^2 + \ldots + EXC_n^2\right)} \right] \leq 2 \cdot \sqrt{n} .\]
Thus we expect at most $2 \sqrt{n}$ total excitement, for an expected 'amortized excitement' of at most $2/\sqrt{n} = o(1)$.

Watch $n$ innings, for only $O(\sqrt{n})$ excitement? Give me break! If $n$ is large, it's better to stay home--no matter what the game.

I would love to see this theory tested against prediction markets like Intrade, which are argued to give a running snapshot of our collective subjective probability of various events. Are the histories as 'low-excitement' as our argument predicts? Even lower? (Nothing we've said rules it out, although one can exhibit simple games which have expected excitement on the order of $\sqrt{n}$.)

And if the histories exhibit more excitement than we'd predict (some sign of collective irrationality, perhaps), is there a systematic way to take advantage of this in the associated betting market? Food for thought. I'd be grateful if anyone knew where to get a record of Intrade's raw day-by-day numbers.

Finally, nothing said above rules out individual games playing out with high excitement, on the order of $n$, but it does say that such outcomes should be infrequent. I believe a more careful martingale approach would show an exponentially small possibility of such large deviations (Russell said their original proof used Azuma's inequality, which would probably suffice).

NO on Prop 8

2008-10-24T14:08:00.000-04:00

If you are straight, would you join a club that disallowed gay people? Or keep your membership in a club that stopped admitting them? Would you feel distinguished by your membership? To the contrary, I think most people would feel embarrassed and cheapened by it.

That's why everyone who is or hopes to get married in California (or anywhere, really) should feel alarmed about Proposition 8, why everyone whose tax dollars fund the Marriage Club should feel affronted by this attempt to make it an exclusionary one (by amending the state constitution). Even though we also fund the similar and inclusive Civil-Union Club next door (at least, until the next wacky voter initiative comes along), who can ignore the fence-builders' zeal for insisting on this petty distinction for heterosexual couples, or fail to grasp its underlying message?

Nothing in the existing laws force clergy of any religion to give ceremonies or `recognize' marriages they don't accept. There remains, in fact, plenty of space in private life to speak and practice intolerance, but we can't let it be done in the name of all Californians.

For thoughtful posts on the subject, see e.g. Luca's, Ben Casnocha's, and the No on Prop 8 website. They are outspent by the opposition and need help to run TV spots up thru the election, to sway what seems like a very volatile public opinion on this issue.
For an amazing photo-essay on California's ever-expanding diversity, and a powerful argument for mutual acceptance and respect, check out the book Under the Dragon. (Hat-tip to Chaya!)

David Foster Wallace

2008-09-14T13:23:00.000-04:00

About a week ago, at great risk to my studies, I gave in to temptation and checked out 'Infinite Jest' from the library. Last night, ~300 pages into rereading this wonderful novel, I learned that David Foster Wallace, its author, has died in an apparent suicide.

I never met DFW, and know little about his personal life--probably as he wished it--although he seems to have been widely regarded as a kind and generous person. I also never connected too closely with his short fiction and journalistic writing, although I read most of it eagerly. My relationship to DFW centered on `Infinite Jest' (1996), an immense book that captivated me when I discovered it in high school.

Briefly, IJ consists of about 1000 pages of chronologically free-form and narratively heterogeneous episodes from the lives of several characters, generally connected either to the Enfield Tennis Academy of metro Boston or to the nearby Ennet House, a drug rehabilitation center. It is supplemented with ~200 pages of footnotes--a generous helping of asides, extra scenes, and background info (it's set in the slight future, culminating around 2008, better known as the Year of the Depend Adult Undergarment in the era of Subsidised Time).

IJ is at once:

-a lush entertainment, addictive in ways I can't fully explain;

-a barrage of observation, alternately expansive and minute, in which the struggle for readers and characters alike is not so much to find meaning as to hold on to it in the face of various compulsions and distractions, to exercise discernment in a world of spectacular banalities and banal truths;

-a compendium of contemporary striving and suffering, in turns putting up for scrutiny: pleasure and addiction, competitive pursuit, narcissism and dismorphic thinking, irony/withdrawal as survival strategies in a surreal political climate... and more, all in memorably original fashion;

-a genuinely moving book, never dominated by its theses or formal experiments, with deeply rendered characters who, despite their glaring and costly mistakes along the way, become friends you wish would hang around for another 1000 pages.

It's a huge loss to learn that David Foster Wallace won't publish a follow-up to IJ. It's a blow to learn that the person who produced such a sustained meditation on suffering (and our resources to overcome it) has taken his own life. It's a sadness to know that the spirit that breathed into those pages has passed.

What's left is his remarkable work, and his readership, which I hope will continue to grow. Pick up 'Infinite Jest' today!

Update: Arts & Letters Daily has collected a number of DFW retrospectives (see 'Essays and Opinion'). This site, by the way, is an excellent aggregator of new and noteworthy online writing.

Heh...

2008-07-10T17:50:00.000-04:00

Funny web comic touching on complexity theory.

From Request Comics. Handed across the room by Madhu to Brendan, who showed it to me.

Earlier I'd seen another, slightly more reverent, comics treatment of Interactive Proofs, by Larry Gonick of 'Cartoon History of the Universe' fame.

To briefly discuss the Request Comics scenario: suppose an alien claims to play perfect chess (in all positions) on an n-by-n board; is it possible to efficiently test this in a poly(n)-length randomized interaction?

If there's only one alien, this might be too hard, since the 'correct' generalization of Chess is EXPTIME-complete. If we instead play a PSPACE-complete game like Hex (or Chess with a truncated game length of poly(n)), things change: Shamir's Theorem tells us how a Verifier can be convinced that any particular board set-up is a win.

But this is not the same as Prover convincing Verifier that Prover plays perfectly! However, additional ideas can help. Feigenbaum and Fortnow showed that every PSPACE-complete language L has a worst-case-to-average case reduction to some sampleable distribution D on instances.

This means there exists a randomized algorithm A^B using a black-box subroutine B, such that for all problem instances x, and for all possible black-boxes B that correctly answer queries of form 'is y in L?' with high probability when y is drawn according to distribution D,

A^B(x) accepts with high prob. if x is in L, and rejects w.h.p. if x is not in L.

Thus for the Prover to convince Verifier that Prover is 'effectively able' to solve L in the worst case (and L may encode how to play perfect Hex), it's enough to prove that Prover can decide L w.h.p. over D. Since D is sampleable, Verifier may draw a sample y from D, and the two can run an interactive proof for L on it (or L-complement, if Prover claims y isn't in L). Repeat to increase soundness.

A Must-See Site

2008-05-23T12:53:00.000-04:00

It's called Theorem of the Day. I just found it, so I can't judge how accurate the frequency claim is, but Robin Whitty has stacked up an impressive collection of short, illustrated introductions to major theorems. I like his taste... two that were news to me and I especially liked in my first sampling: Nevanlinna's Five-Value Theorem and The Analyst's Traveling Salesman Problem.

Sign Robin's guestbook, spread the word, and recommend a theorem of CS theory! (I see at least 3 already, if you count unsolvability of Diophantine equations.)

Random bits

2008-05-15T14:43:00.000-04:00

This morning I was delighted to learn that Alan Baker, the Swarthmore professor whose Philosophy of Science class I took senior year, recently won the US Shogi championships--read his account here. Congrats, Prof. Baker!
I never learned Shogi, although Go--another Asian board game--was a big part of my youth and probably a decisive factor in my eventual interest in math/CS.

In other news, I am coauthor on a paper, 'The Power of Unentanglement', recently released on ECCC (and headed for CCC '08), jointly with Scott Aaronson, Salman Beigi, Bill Fefferman, and Peter Shor. It's about multiple-prover, single-round, quantum interactive proofs, and I encourage those whose cup of tea that is to take a look.

This is my first appearance in a conference paper, but not quite my first time in print--it happened once before, by accident. As a freshman in college, I asked my Linear Algebra professor, Steven Maurer, a question on an online class discussion board. Here it is, in the breathless and overwrought prose of my teenage years:

"This question has been haunting me, and I know I shouldn't expect definite answers. But how do mathematicians know when a theory is more or less done? Is it when they've reached a systematic classification theorem or a computational method for the objects they were looking for? Do they typically begin with ambitions as to the capabilities they'd like to achieve? I suppose there's nuanced interaction here, for instance, in seeking theoretical comprehension of vector spaces we find that these spaces can be characterized by possibly finite 'basis' sets. Does this lead us to want to construct algorithmically these new ensembles whose existence we weren't aware of to begin with? Or, pessimistically, do the results just start petering out, either because the 'interesting' ones are exhausted or because as we push out into theorem-space it becomes too wild and wooly to reward our efforts? Are there more compelling things to discover about vector spaces in general, or do we need to start scrutinizing specific vector spaces for neat quirks--or introduce additional structure into our axioms (or definitions): dot products, angles, magnitudes, etc.?

Also, how strong or detailed is the typical mathematician's sense of the openness or settledness of the various theories? And is there an alternative hypothesis I'm missing? "

Steve gave a thoughtful reply, years passed, and then a similar topic came up in coversation between himself and the mathematician and popular math writer Philip J. Davis. The conversation sparked an essay by Davis in which he quoted Maurer and I (with permission), the essay recently became part of a philosophy-of-math book ('Mathematics and Common Sense: A Case of Creative Tension'), and I got mailed a free copy--sweet! Once again, I recommend the book to anyone who enjoys that kind of thing. The essay is online.

Free on Friday?

2008-05-10T23:26:00.000-04:00

You should come to Johnny D's in Davis Square and hear No Static, a 9-or-10-piece Steely Dan tribute band (standard preemptive clarification: Steely Dan is the band name, not a person).

No Static plays regularly in the area--I saw them in the fall and they were excellent, channeling the Dan's recordings with amazing care and fidelity.

Like most great artists, Steely Dan affords a unique perspective on the world, one best imbibed by listening to multiple albums in their weird entirety. This is exactly No Static's approach, so if you don't know Steely Dan, or have only heard a few catchy radio numbers, here's your chance to get hooked. Hope to see you there!

Complexity Calisthenics (Part I)

2008-05-01T14:02:00.000-04:00

Today I want to describe and recommend a paper I quite enjoyed: The Computational Complexity of Universal Hashing by Mansour, Nisan, and Tiwari (henceforth MNT). I think that this paper, while not overly demanding technically, is likely to stretch readers' brains in several interesting directions at once.

As a motivation, consider the following question, which has vexed some of us since the third grade: why is multiplication so hard?

The algorithm we learn in school takes time quadratic in the bit-length of the input numbers. This is far from optimal, and inspired work over the years has brought the running time ever-closer to the conjecturally-optimal n log n; Martin Furer published a breakthrough in STOC 2007, and there may have been improvements since then. But compare this with addition, which can easily be performed with linear time and logarithmic space (simultaneously). Could we hope for anything similar? (I don't believe that any of the fast multiplication algorithms run in sublinear space, although I could be mistaken. Here is Wiki's summary of existing algorithms for arithmetic.)

As MNT observe, the question is made especially interesting when we observed that multiplication could be just as easily achieved in linear time/logspace... if we were willing to accept a different representation for our integer inputs! Namely, if we're given the prime factorizations of the inputs, we simply add corresponding exponents to determine the product. There are two hitches, though: first, we'd have to accept the promise that the prime factorizations given really do involve primes (it's not at all clear that we'd have the time/space to check this, even with the recent advances in primality testing); second, and more germane to our discussion, addition just got much harder!

The situation is similar over finite fields of prime order (Z_p): in standard representation, addition is easy and multiplication is less so, while if we represent numbers as powers of a fixed primitive root, the reverse becomes true. This suggests a woeful but intriguing possibility: perhaps no matter how we represent numbers, one of the two operations must be computationally complex, even though we have latitude to 'trade off' between + and *. So we are invited to consider

Mental Stretch #1: Can we prove 'representation-independent' complexity lower bounds?

Stretch #2: Can we prove such lower bounds in the form of tradeoffs between two component problems, as seems necessary here?

In the setting of finite-field arithmetic, MNT answer 'yes' to both problems. The lower bounds they give, however, are not expressed simply in terms of time usage or space usage, but instead as the product of these two measures. Thus we have

Stretch #3: Prove 'time-space tradeoffs' for computational problems.

To be clear, all three of these 'stretches' had been made in various forms in work prior to MNT; I'm just using their paper as a good example.

The combination of these three elements certainly makes the task seem daunting. But MNT have convinced me, and I hope to suggest to you, that with the right ideas it's not so hard. As the paper title indicates, their point of departure is Universal Hashing (UH)--an algorithmic technique in which finite fields have already proved useful. Use upper bounds to prove lower bounds. We can call this another Stretch, or call it wisdom of the ages, but it deserves to be stated.

So what is UH? Fix a domain D and a range R. a (finite) family H of functions from D to R is called a Universal Hash Family (UHF) if the following holds:

For every pair of distinct elements d, d' in D,

and for every pair of (not necessarily distinct) elements r, r' in R,

if we pick a function h at random from H,

Prob[h(d) = r, h(d') = r' ] = 1/|R|^2.

In other words, the randomly chosen h behaves just like a truly random function from D to R when we restrict attention to any two domain elements. (In typical applications we hope to save time and randomness, since H may be much smaller than the space of all functions.)

Here is what MNT do: they prove that implementing any UHF necessitates a complexity lower bound in the form of a time-space product. (To 'implement' a UHF H is to compute the function f_H(h, x) = h(x).)

This is in fact the main message of the paper, but they obtain our desired application to + and * as a corollary, by citing the well known fact that, fixing a prime field Z_p = D = R,

H = {h_{a, b}(x) = a*x + b mod p}

is a UHF, where a, b range over all field elements. (Left as an easy exercise.)

Note the gain from this perspective: implementing a UHF is a 'representation-invariant' property of a function, so Stretch 1 becomes possible. Moreover, Stretch 2 now makes more sense: it is only jointly that + and * define a UHF, so whatever complexity measure M we lower-bound for UHFs implies only a tradeoff between + and *.

It remains only to sketch the proof of time-space tradeoffs for UHFs, which in fact is a manageable argument along classic lines (the basic form of the argument is attributed to earlier work by Borodin and Cook). The upshot for us will be that for any program computing (any representation of) f(a, b, x) = a*x + b over an n-digit prime modulus, if T denotes worst-case time usage and S worst-case space, T*S = Omega(n^2). Very nice! (Although what this actually implies about the larger of the individual time-space products of + and * under this representation is not clear to me at the moment.)

Let's adjourn for today... wouldn't want to pull a muscle.

A simple plan to improve your graduate program

2008-04-16T19:50:00.000-04:00

It's just this: Food is key. We need more food. (In what follows, I'm speaking not just for MIT theory students, but for all students everywhere.)

Cancel the subscription to 'Journal of Timed Networked Multithreaded Aqueous Automata', and a few others. You've just saved about $20,000.

Use the money to provide copious snacks for students and faculty. Weekly receptions help, but really we're hungry all the time. To elaborate on that point:

-The student center is a tiresome 5-10 minutes away.

-Graduate students are low on cash. We work strange hours that discourage grocery shopping (and may not own a car). Some of us are newly weaned from the meal plans of our undergrad days, and we're only slowly learning to provide for ourselves. The food around here is expensive.

If department budget is truly an issue, there is another way, practiced with admirable success by UC San Diego's CSE department: recruit grad student volunteers to maintain a stocked snack-room, with foods purchased cheaply in bulk and paid for on the honor system. Of course, a snack-room should also be a social space.

Candy and tasty treats help, but it's too easy to over-rely on them and come crashing down. At some point we all wish there were less of these around the office. Consider in their stead:

-bagels
-raisins
-apples and bananas
-peanuts and peanut butter

...all cheap, real-tasting, and calorific.

That's it! An easy, cost-effective intervention that will keep students and faculty working happily in their offices on their next theorem or patentable device.

Some babies grow in a peculiar way

2008-04-04T22:23:00.000-04:00

Today I bumped into an order of growth I hadn't seen before, and thought I'd share it for a modest bit of mental aerobics.

Readers may well have seen functions of form

f(n) = (log n)^c,

known as 'polylogarithmic'. These are important in, e.g., query complexity, where we like the number of queries to be much smaller than the input size n when possible. Also emerging from such studies are the 'quasipolynomial' functions, of form

g(n) = 2^{(log n)^c}.

As a warmup--how fast do these things grow?

OK, now the main course tonight is the following:

h(n) = 2^{2^{(log log n)^c}}.

What do you make of these? And what questions need answering before we understand such a growth rate 'well enough'? I'm unsure and would love to hear your thoughts.

News, and some Number Theory

2008-03-21T14:30:00.000-04:00

Time for a personal update: I'm enjoying myself greatly here in Cambridge, and was recently admitted as a transfer student to MIT's EECS department. The move has both personal and academic advantages for me, but let me emphasize that I think UCSD has a lot to offer prospective students, and in addition is home to many cool people whom I miss... I would be happy to offer advice about either school.

When I started writing here as an undergrad, I knew very few people in the worlds of TCS and Complexity, and the blog was a way of reaching out to a community I wanted to join. Now, thanks in part to blogging (thru which I met Scott, my advisor), I'm immersed in that community at a school with a large, vibrant Theory group. This is to say that, though writing here still interests me, it no longer answers an urgent personal need, and I am most likely to post new material in response to a request for specific topics or post types.

Today I was perusing a favorite book of mine, 'Gems of Theoretical Computer Science' by U. Schoning & R. Pruim. One chapter partially treats the undecidability of determining whether systems of Diophantine equations (polynomial equations where solutions are required to be integral) have a solution. This was one of Hilbert's problems from 1900, solved in 1971 and full of deep math.

The authors pose the following exercise: show that the version where variables must take nonnegative values, is reducible to the integer version. (And vice-versa; also the rational-values version is reducible to the integral version; the converse appears to be open...)

Think about it...

The reduction they give: Given a set of polynomial equations {P_i(X_1, ... X_k)}, we want to determine if they're simultaneously satisfiable with nonnegative values. Introduce, for each j <= k, the variables Y_{j, 1}, Y_{j, 2}, Y_{j, 3}, Y_{j_4}.

Now add to the system, for each j <= k, the constraint that

X_j = Y_{j, 1}^2 + Y_{j, 2}^2 + Y_{j, 3}^2 + Y_{j_4}^2.

Claim: the new system is satisfiable over the integers iff the original one is satisfiable over the nonnegative integers! The proof, of course, is an easy consequence of Lagrange's Theorem that every nonnegative integer is the sum of 4 integer squares.

So, my question is, could a reduction be found that doesn't rely on Lagrange's Theorem? Or its weaker variants where the constant 4 is replaced with some constant c > 4. Or maybe for some constant c, the proof is really so simple that I will be satisfied that we are performing this reduction with the cheapest tools.

If our plan in the reduction is to constrain the original variables in a form analogous to the above, namely

X_j = Q_j(Y, Z, ...),

where Y, Z, ... are new integral variables, is there any way around proving a version of Lagrange's Theorem? Generally we show that polynomials are identically nonnegative by expressing them as a sum of one or more squares, e.g.,

Y^2 + Z^2 - 2YZ = (Y - Z)^2.

Using this template, we'd be reliant on Lagrange. However, in his thesis, Minkowski conjectured that there exist nonnegative real polynomials *not* so expressible, and this was proved by Hilbert. A simple example I found online is

Q(X, Y, Z) = X^4*Y^2 + Y^4*Z^2 + Z^4*Y^2 - 3X^2*Y^2*Z^2,

and another counterexample is derived systematically in the classy and useful inequalities book 'The Cauchy-Schwartz Master Class' by J.M. Steele. (Artin proved, however, that every poly that's identically nonnegative, is expressible as the sum of finitely many *rational* functions squared.)

Could it be that one of these creatures is easier to use in the reduction (both to prove it's nonnegative, and ranges over all nonnegative values)? Somehow I doubt it. Anyways, I just wanted to point to an instance where a reduction one would expect to be straightforward seems to require fairly nontrivial understanding of the problem domain.

Beasts of Probability and Plane Geometry

2008-03-07T16:43:00.000-05:00

Say you're trying to predict whether some event E occurs or not. There is another collection of events I_1, I_2, ... I_k, which are positive predictors of E: for every j, E occurs with probability at least .99 conditioning on the event that I_j occurs.

Can we lower-bound the probability that E occurs conditioning on the event that *at least one* I_j occurs?

(Think about it before reading on.)

Here's a simple example of what can go wrong: let the underlying probability space be a sequence of n unbiased coin flips. Let E be the event that at least 2/3 of the flips come up heads. For each subset S of {1, 2, ... n} of size exactly
.4n, let I_S be the event that all the coin flips indexed by S come up heads.

If n is large enough, we have that

i) E is almost surely false, yet

ii) Almost surely, some I_S is satisfied--even though

iii) Conditioning on any fixed event I_S, E becomes almost surely true (since we then expect half of the remaining flips to come up heads, yielding about a .4 + .5*.6 = .7 fraction of heads total).

One can also modify this example to make conditioning on the union of the I_j's actually decrease the probability that E occurs.

This kind of conclusion seems somewhat pathological and inconvenient, so it's natural to look for restrictions that prevent it from arising. The simplest would be to restrict the number, k, of predictor variables: for the above hypotheses, we have that the probability of E conditioning on the union of the I_j's is at least

.99 / (1 + .01(k - 1)).

(to see this, think about the worst possible case, which resembles a 'sunflower' in probability space.)

A more interesting direction is to restrict the structure of the predictor events within probability space. For instance, suppose that the probability space is a uniformly drawn point from the unit interval, E is some arbitrary subset of the interval, and each I_j is the indicator variable for some fixed subinterval. Then, regardless of the number of I_j, we can conclude that E occurs with high probability conditioning on the union of I_j's; not quite .99, but close. See my closely related earlier post for details.

It is natural to try to extend this result to higher dimensions, and for predictor indicator-sets given by axis-parallel rectangles this succeeds by an induction (although the effect gets exponentially weaker with the dimension). Similar results hold if the sets are required to be 'fat' convex bodies, in which case an argument much like the 1-dimensional one works.

However, allowing rotated rectangles destroys the effect even in two dimensions. Here's one interpretation: consider the unit square as a city, and take the set S to be the set of Democratic households.

In pathological cases, it's possible to find a covering of the square by overlapping convex 'precincts', such that

i) in each precinct, 99% of the households are Democratic, yet

ii) overall, 99% of houses are Republican!

Such sets seem truly bizarre. For a long time I was convinced they couldn't exist, but after failing to prove this, I finally tracked down a construction in a Harmonic Analysis textbook by Elias Stein (who, besides seeming impressive in his own right, was PhD advisor to Fields Medalists Charles Fefferman and Terence Tao). These sets, whose construction resembles a kind of hydra spawning ever more and tinier heads, are related to the more well-known Besicovitch/Kakeya sets. One can even achieve a kind of fantastical limit, in the following theorem for which Stein provides a reference:

There exists a subset S of measure zero in the unit square, such that for every point x on the square, there exists a line L thru x, such that S contains all of L except, possibly, x itself!

That's a Wrap

2007-12-24T23:34:00.000-05:00

I had some gift-giving duties to attend to today... halfway into the wrapping phase, my mind wandered in a predictable direction:

Given a set of rectangular box dimensions, what is the smallest amount of paper that will wrap the box?

One would assume we want to cut out a rectangle of wrapping paper, since otherwise we get annoying scraps (and also the problem is mathematically trivial if we can cut a cross-type shape).

I haven't had any time to toy with this problem, but I had a feeling one particular MIT dude might have... and I was right. True to form, Erik Demaine delivers a whole page about various wrapping problems he's explored with colleagues.

To anyone reading who teaches a programming course, I would suggest that a fun algorithms assignment could be spun out problems of the above type. If the program outputted folding instructions too, so much the better.

Happy holidays, all!

Cardinal Rules

2007-12-17T15:13:00.001-05:00

1. Pick your favorite countable set S. Let F be a 'nested' family of distinct subsets of S; that is, if A, B are members of F, then either A is contained in B or B is contained in A.

Then clearly F can be at most countable... right?

A puzzle from Bollobas' recent book.

2. Given a collection C of functions from N = {1, 2, 3, ...} to N, say that C is unbounded if for any function f (in C or not), there exists a function g in C such that g(i) > f(i) for infinitely many i.

Clearly the class C of all functions from N to N is unbounded. Also, standard diagonalization techniques tell us that no countable collection C can be unbounded (exercise).

The question then becomes: what is the smallest cardinality of any unbounded collection C? Assuming the Continuum Hypothesis is false, where does the threshold lie?

Fortunately or unfortunately, there seems to be little we can say about this issue within the standard axioms of set theory. Assuming CH is false, the threshold could be as low as the first uncountable cardinal, or as large as the continuum, or in between--this I learned from Jech's encyclopedic book Set Theory. There are many questions of this flavor, where the key construction (in our case, constructing a 'bounding function' for a given 'small' collection C) is easy to do in the countable setting, but essentially impossible to analyze when there are uncountably many requirements floating around.

The need to satisfy uncountable collections of requirements in a construction is so common that new axioms for set theory are put forward expressly to assert the possibility of doing so (under some restrictions that make the axioms plausible); 'Martin's Axiom' is an especially widely used axiom of this type. Kunen's book on set theory seems like a good reference for MA (though I'm just starting to learn about it).

Of course, the Continuum Hypothesis itself makes it easier to satisfy collections of requirements of size smaller than continuum, since such requirements are then at most countable! This leads to some bizarre constructions, the possibility of many of which stands or falls with the CH itself. The excellent book Problems and Theorems in Classical Set Theory gives many of these, and Bill Gasarch recently exposited one such application in Euclidean Ramsey theory. On the other hand, Martin's Axiom, which is independent of CH, allows set theorists to prove many interesting results while remaining more 'agnostic' about cardinality issues.

I think that set theory is a blast, and that its logical structure resonates with issues in computer science. But I'm far from expert on the subject, so if I've said anything inaccurate please let me know.

So a Puzzle Walks into a Bar...

2007-12-12T19:21:00.000-05:00

In the Boston area, two American values--higher education and beer--converge in a big way. Possibly as a result of this convergence, it's a good bet that on any night of the week, there's a bar where you can watch or participate in a trivia contest. (Or so friends tell me.)

These contests have two features that make them interesting from this blog's perspective. First, there's apparently a company that sends its quizmasters all over town, and presumably supplies them with fun questions. So let's assume that the questions are drawn from some fixed distribution D, unknown in advance.

Second, these are team games. So now--let's say you've got n trivia-loving friends, and you're trying to form a team of k < n of them to maximize your chances of winning. k might grow with n.

To help you choose, you can take your friends out for drinks and watch the contests for a few weeks or months before deciding on your team. You can record who out of your friends answered which questions correctly as they watched. (For simplicity, let's say that if someone answers correctly, they know they're right, and if they don't know the answer they keep their mouths shut.) But you can only afford poly(n) of these expensive outings before you decide your team and start trying to rake in gift certificates or stuffed bears or whatever.

So--what are your prospects in general for determining the best team?

(i.e., we're looking for algorithms that, for any group of friends and any D, perform well with high probability.)

If one has only been exposed to computational problems in which all the necessary information is presented as a single input, a problem like this can be disconcerting. There appears to be both a computational and a statistical puzzle to solve, simultaneously. (If the computational aspect doesn't seem challenging, keep in mind: your friends' various knowledge-bases may be similar, disjoint, or anywhere crazily in between...)

My challenge to readers is to think about how this problem fits into algorithms/complexity theory. Not necessarily to solve it--I've found it touches on published research, and I will give references in a future post--but to relate it to what you've seen before. I'm hoping this might be a good warm-up to thinking about ideas from computational learning theory which I also have been wanting to exposit.

I should note that even slight tweaks on this problem could lead to questions I haven't thought about, but which I encourage others to (e.g., what if player ability is affected by drinking?).

Quick Links

2007-12-11T15:12:00.000-05:00

First, a plug: Aaron Roth, a grad student at CMU is keeping up a cool, informative TCS blog that deserves to be on the map. Check it out, especially if you want an insider's perspective on the rapidly growing area broadly referred to as 'algorithmic game theory'.

Bill Gasarch has been posting a number of nice puzzles lately. A couple have served as direct illustrations of ideas I've tried to exposit here, so I thought I'd point to them as follow-ups. In both cases I tried to describe the connection within the comments section.

1) For readers who followed my two posts on statistical distance, Bill gave a CS puzzle (about the possibility of 'zero-knowledge distributed consensus') that is exemplary for the use of reasoning about distance between distributions.

2) Bill described variants on Van der Waerden's Theorem, one of the classic results that presaged ideas of Ramsey Theory. He asked about the relation between Van der Waerden's Theorem for the natural numbers and its immediate extension to the real numbers. In particular, is the latter simpler? In the comments, I describe how the idea of compactness in logic, exposited here a while back, can be used to derive VDW's theorem from its real-number version.

New TOC Aggregator! And, a Puzzle.

2007-12-01T15:35:00.000-05:00

Getcher daily Theory dose here, courtesy of Arvind Narayanan. It collects content from many of the best TCS blogs online... and somehow mine made it on there too.

In other news... recently a friend named William Torres (ordinarily more musical than mathematical) asked me an intriguing question:

Can you rotate a rigid, hollow sphere in space, holding its center fixed (but possibly varying the axis of rotation), in such a way that every point moves the same nonzero total amount?

Note that we're not referring to a point's net displacement; in fact, the net motion of the sphere will always correspond to a rotation about some axis (you shouldn't necessarily find this obvious... see wiki), hence two points will always have zero net displacement. What we're interested in is equalizing the path lengths of points' trajectories--how much 'exercise' they get. Of course, the amount should be finite.

I don't know the answer to William's question, but this doesn't mean it's hard. As a warm-up, see if you can prove the following (which I think I can show): It is possible for each point on Earth (understood as a sphere) for each point to have the same nonzero average wind speed over a 24-hour period (where wind is understood as a continuous vector field on the sphere, with vectors tangent to the sphere's surface, and varying continuously over time).

This contrasts with Brouwer's classical 'Hairy Ball Theorem', which states that at any given time, the wind speed will be zero at two or more points on Earth.

Limits of Transcendence: Our Failure to Protect Prisoners

2007-11-08T14:03:00.000-05:00

One thing I'd long been planning to post about is just how positive a role math has played in my own life. Since I came to enjoy it (relatively late--around senior year in high school), I have become: less restless; less materialistic; clearer and more self-reliant in my thinking; able to think longer and more fruitfully about all kinds of things, with nothing but a pen and paper.

All of these beneficial effects constitute, to my mind, a 'practical application' for math that warrants mentioning in the same breath as its uses in science and technology. In particular, I always thought these virtues seemed especially well-suited to empower and improve the constrained lives of prisoners. I know of one example--Paul Turan seems to have invented extremal graph theory in a Hungarian labor camp during WWII--but Turan was admittedly already a professional mathematician. Of course math isn't for everyone, but I would be very interested to know whether it's been taught specifically for enjoyment in prisons, and with what results.

It's an exciting idea to me, and I hope it excites others. However, it'd be irresponsible and dishonest to pursue it without acknowledging math's limits as a life practice. Coping with boredom is one thing, but, speaking personally, my mathematical thinking goes to pieces when I'm in acute distress or suffering. There's a limit to what we should reasonably expect to transcend through math, just as with art, religion, meditation, and other such 'soft' techniques... which brings me to what actually prompted this post: news from California that makes me ashamed of the state of affairs in my home state.

According to this article (see also this Times editorial), Gov. Schwarzenegger recently vetoed a bill that would allow nonprofits to distribute condoms in prisons. (He claimed it would conflict with the law against sexual contact between inmates.) It seems he did something similar two years ago. There are some condom distributions in CA prisons, and Schwarzenegger authorized one new, small-scale pilot program, but he derailed the state legislature's decision to make such distributions a statewide reality.

I hope the cruelty and stupidity of this decision speak for themselves, but I'll make a few comments to encourage further thought, because a decision this bad needs to be understood as well as denounced. To try and make (partial) sense of his decision, let me suggest that, in policymaking and debate around HIV/AIDS and other sexually transmitted infections, there are various gradations of the position that would block direct public health initiatives.

First, there are those who simply disapprove of a particular behavior, be it pre- or extramarital sex, same-gender sex, sex in prisons, or intravenous drug use. It doesn't necessarily lead them to disregard other social issues or form a blanket policy statement.

Then there are those who, through a combination of wishful thinking and manipulation, reach the idea that the health threat posed by risky behaviors might itself be the best deterrent against these behaviors, superior from a moral and public health perspective to interventions that would make those behaviors safer (condom distributions, needle exchanges, HPV vaccinations, etc). They accept arguments to this effect without sufficient critical thought, and neglect contrary evidence.

Then there are those who publicly espouse this best-of-both-worlds notion, but whose prolonged refusal to engage with the evidence leads one to suspect that either (a) they no longer feel compassion for victims of infection from their designated 'deviant' population groups, or (b) they feel that infection's (supposed) role in discrediting and deterring 'deviant' behavior outweighs its human costs (so, in a sense, they ally themselves with the epidemic).

Finally, at the far end you have those who feel only contempt for 'deviants', and openly exult in public health crises which they see as just punishment.

But can we explain Schwarzenegger's behavior as occupying a point along this spectrum? I'm not so sure. As soon as incarceration comes into play, the debate seems to get much more complex (i.e., crazier). Are these notions of morality and deterrence even operative in the (supposedly kinda-socially-liberal) Governor's decision? Is he offering a feeble cover for the prison industry from the already-widespread recognition that, in many cases, they fail to protect their inmates from sexual coercion? (For a discussion of the state of available statistics on prison rape see this Human Rights Watch page.) Or is he merely bowing to the time-honored tradition of abusing prisoners?

I would love to hear what others think, because I can't decide the issue myself. All that's clear to me is that he's taken citizens in a position of enforced vulnerability, who are contracting HIV at eight times the rate outside prison, and cut off one of the most important means of protecting them. (I don't believe the state was even asked to pay for the condoms....!)

Meanwhile--Governor Schwarzenegger, withdraw your veto!

Goofball DNA-Bonanza

2007-11-06T18:21:00.000-05:00

Since this blog's readership is, I'm guessing, essentially a (very-)proper subset of the readership of Shtetl-Optimized, you may be familiar with his recent musings and observations on DNA rewriting rules (to which I refer readers before looking further at my post). I've been finding this stuff a fun alternative to my usual research (the last time I got this worked up over DNA might've been when I heard about ANDi the monkey), and have come up with three simple results in the past couple of days. The latest is a bit too long for Scott's comments section, so I wrote it up in LaTex and am putting it here.

I encourage all readers to generate, pose, and/or answer additional questions on related themes! Collaborative online research is lots of fun in my experience, and something I'm considering trying to do more of with this blog.

Let me explain the third result after reviewing the other two. But before I begin, I want to emphasize that I make no claims as to the biological realism of any of the models under consideration, though I'm happy to try to work out results in more realistic models if they still seem like interesting puzzles.

First, I showed that, in synthesizing a string x via Scott's model of DNA rewrite rules, the substring-reversal rule can be eliminated at the cost of increasing by constant factors the number of steps and the size of intermediate strings.

Then, I showed that a factor-2 increase in steps allows one to hold the intermediate string to within a factor 2 of the final string length at all times. This result, by constrast, holds whether one is trying to synthesize x de novo or to transform some other string x' into x (although I only wrote up the first case, the other is essentially the same analysis). In the process, I was especially pleased to introduce an analytical tool called 'garbage monsters'; Scott and I hope the terminology will catch on in mainstream biology.

The newest result is the following: suppose you want to implement an error-correcting code x --> C(x) via DNA rewrite rules, where the choices of operations made can depend on x; then unfortunately, something on the order of n/(lg n) operations are needed in the encoding process to ensure that the code is actually robust. A matching upper bound can be easily extracted from Scott's observations in his comments section, and it's a dispiriting bound because for that price, you could synthesize C(x) without even manipulating the string x that you're given! (A similar, simpler result holds for the decoding process, but I haven't written this up.)

For completeness, I'll reproduce my sketch proofs for the first two results below... but first let me note that monkeys continue to make news (thanks again, Chaya!).

***First Result, Comment 21 on Scott's post***

"So how powerful is the reversal operation, really?

Suppose we can produce string x in k applications of operations (1)-(4). I claim we can do it in 4k + 1 operations, without reversals. (Of course, this will show that the Lempel-Ziv approach is also a constant-factor approximation in our setting.)

First, note that, if you can produce x in k steps with (1)-(4), you can also produce x^R, i.e. the reversal of x, in k steps with (1)-(4), by ‘flipping’ each operation.

Second, note that you can produce x.x^R, their concatenation, in 2k steps by running both productions in parallel, interleaving steps on the two halves. If the i’th step in the original production of x was s, then the 2i’th step in the new production will be s.s^R.

Now, in this ‘joint’ production we eliminate reversals as follows: say in the production of x, at the i’th stage we wish to move from

s = a.b.c to s’ = a.b^R.c …

well, in the joint production, at stage 2i we’ve got the string

a.b.c.c^R.b^R.a^R

By two copy and two deletion operations, we reach

a.b^R.c.c^R.b.a^R,

as needed to advance both sides’ progress.

Finally, when the joint production’s finished, delete the right-hand side to yield x. That’s 4k + 1 steps."

***Second Result, Comments 30-31 on Scott's post***

"I believe I can show that, if we’re producing a string x of length n, we can keep the intermediate strings to length at most 2n, while incurring at most a factor-2 blowup in the number of steps used.

As Scott suggested to me in conversation, let’s keep track of which symbols in the intermediate workstring will and won’t make it into the final string x without deletion. If they won’t, call them ‘nonterminals’. (If a symbol will be replicated, and at least one of its descendants will be included in the final string, it’s not considered a nonterminal.)

First note that, if in a production of x there appears at some stage a block of consecutive nonterminals, we can modify the production so that they are treated as a ‘unit’ in subsequent steps, i.e. no string operation takes an endpoint that’s properly inside the block. They get shuffled around together and eventually destroyed together. The production’s length is not affected.

In a stage of such a production, for analysis purposes, we call a maximal block of nonterminals a ‘garbage monster’. Each time a new garbage monster is created (and many may be created by a single copy operation–even if there were no nonterminals in the original substring), we give it an unused, goofy monster name.

When string manipulations cause two garbage monsters to become adjacent, we combine them under one of their two names (and say that that one ‘eats’ the other one).

Key claim: in our modified type of production, at most one garbage monster gets eaten or destroyed at every step! Draw some pictures to see if you agree.

Now, with this fact in hand, we can modify the production again and argue it gives what we want.
Here’s the strategy: given a production of x of the type we described, modify the production so that between each step, we stop and delete all garbage monsters, one deletion per monster.

This is a bit wasteful since some of these might’ve been eaten by other garbage monsters; but if our production had k steps to begin with, only at most k monsters got eaten total, and all garbage monsters must die somehow, so we only add at most k new steps.

Finally, observe that the string is culled to length at most n after every new round of ‘executions’, and since the workstring’s length is at most doubled by any string operation, its length is bounded by 2n throughout."

The Scientific Canon (I)

2007-10-27T16:31:00.000-04:00

What is the scientific canon? A pantheon of immortal brilliance? A self-serving narrative of the dominant paradigm? A paean to dead white males?

Let me suggest a simpler, working definition: you know you've made it into the scientific canon when your name is writ large on the main building at MIT, stately-like, with any U's written as V's.

There's quite a procession of them, and I was struck by how many of their names were unknown to me. If I know at least half of the names in the latest Theory conference, shouldn't I also know who's made a lasting impression on science as a whole? Well, readers, here's part one of the list; how do you fare?

If anyone wants to chime in about interesting people on the list, please feel welcome. The names appear in blocks, as indicated, with certain key names especially large, and there is definitely some amount of thematic/historical grouping... what can you observe? There's a slight possibility some names are misspelled, since a few were well-hidden by tall trees.

Finally, I should note that some of these people might not, strictly speaking, be considered scientists. But, I've set my criterion--they're up on the wall, so into the canon they go.

BLACK * RUMFORD * JOVLE * CLAVSIVS

CARNOT * TELFORD * STEPHENSON

DE LESSEPS * RANKINE * EADS

COPERNICVS

GVERICKE * TORRICELLI * CHLADNI

HVYGENS * YOVNG * ARAGO * FRESNEL

LAGVERRE * KIRCHHOFF * ROWLAND

DARWIN

ICTINVS * PHIDIAS * VITRVVIVS * GIOTTO

ANTHEMIVS * DE COVCY

BRUNELLESCHI * WREN * BVLFINCH

LEONARDO DA VINCI

GVTENBERG * WATT * ARKWRIGHT

WHITNEY * PERKINS * FVLTON * FAIRBAIRN

FROVDE * OTTO DE LAVAL * WRIGHT

ARCHIMEDES

GILBERT * COVLOMB * VOLTA * OERSTED

AMPERE * OHM * HENRY * MAXWELL

MORSE * SIEMENS * GRAMME * HERTZ

FARADAY

More Wordplay

2007-10-22T16:47:00.000-04:00

Call a word 'orderly' if its letters are in alphabetical or reverse-alphabetical order. Consecutive appearances of the same letter is OK.

-Find a famous mathematician whose name is orderly.

-Now find a complexity theorist.

-How long an orderly word can you find?

-Have any other challenges for the rest of us? A CS research problem related to orderliness?

In a different but still-wordy vein, Free Rice is a fun site, where you donate rice to the UN by testing your vocabulary. The words get impressively obscure as you score more correct (multiple-choice) guesses, much more so than, e.g. the also-recommended Word of the Day page, and once you're arguing with friends about what 'carronade' means it's a good bet that you're not fighting poverty in the most effective way possible, but I still recommend it. What this quiz underscores for me is how much verbal knowledge we hold at the very edge of awareness and competence. (Hat tip to Chaya for the link.)

Space is a Lonely Place

2007-10-19T19:15:00.001-04:00

Puzzle time again--this time a dressed-up version of a problem in Claude George's book 'Exercises in Integration'--not as boring as it might sound!

The year is 2100. SETI, having failed to make contact with any extraterrestrials, is facing termination. They haven't lost faith, but everyone else on Earth is pretty tired of them, so they decide to spend their remaining budget by blasting themselves off into space--a reconnaissance mission of no return.

The SETI folks are interested in coming near as many potentially-inhabited star systems as possible. They've watched 'Biodome' a few times, and they're pretty sure they can get their spaceship to support human life indefinitely. But fuel is limited to their blast-off needs, so they have to plan on following a straight-line path at constant velocity thru space (which is 3-dimensional, or 2 if you like, Euclidean, and devoid of gravity or other impedances--stars can be passed thru, e.g.).

A star-system is defined as the billion miles surrounding a star, within which SETI figures they'll have a good shot at communication with any planets in the system. In the first version of the problem, they also assume, somewhat optimistically, that candidate stars do not move and that candidate star-systems occupy a nonzero asymptotic fraction of the universe's volume. E.g., for any N, if we draw a ball of radius N around the Earth, at least .001 of its volume lies in some candidate star system.

Here's SETI making contact with 3 star systems:

Problem 1: Can the crew plot a straight-line course that will put them in contact with infinitely many candidate star-systems?

Problem 2: What if their navigation equipment forces their initial bearing to be a rational angle?

Problem 3: There's all sorts of potential crazy variants: do the stars move? How fast? Adaptively or non-adaptively? But I've already wasted enough time on this problem, so dear readers, I leave it to you.

Is This Right? Is This Legal?

2007-10-10T10:34:00.000-04:00

This post may not approach the heights of quandary Scott has been facing lately, but I think it's worth discussing.

I typed in 'Computational Complexity' on amazon.com to get the reference info for Christos H. Papadimitriou's textbook of the same name. Here's what I got instead.

It's a 'Cram101' production, an outline of Papadimitriou's textbook. His last name appears on the cover, but not his first name or classy middle initial, suggesting he had nothing to do with it.

So, is this right? Does such an outline contribute enough to warrant its own copyright, or does it infringe on Papadimitriou's?

One might argue from the precedent of 'Cliffs Notes' for novels, but there are some obvious differences. Cliffs Notes summarize, but do not reproduce, the artistry or enjoyability of novels, whereas cram101 presumably makes a direct substitution: their skimpier expository writing, modeled directly on Papadimitriou's careful exposition. Cliffs Notes add a modicum of clarification, criticism, thematic discussion, etc., whereas it's not clear what if anything Cram101 adds (please note that I haven't looked inside, and am prepared to reconsider the issue if the publisher or anyone else wants to show me the book).

I have heard it expressed that Papadimitriou's book is hard reading, but there are other, more elementary textbooks out there
covering much of the same content. The things in the text that are not in most TOC books (extensive logic and some necessarily hard advanced topics like Razborov's Theorem) are probably not going to be tested heavily in class, other than familiarity with the theorem statements--and you can get that easily enough from the textbook.

So I'm guessing the motivation and main selling point for this book is its much lower price compared to the original text. I can sympathize--I spent more than a semester ducking into Cody's Books to read from 'Computational Complexity''s sumptuous, glossy pages before my parents bought it for me as a high-school graduation present. Expensive textbooks (and journals) hurt science just as they hurt the college students who are forced to buy them, and outlines like Cram101's are a by-product. (Let me add that a) I don't blame Christos for his book's price, b) it was for me a life-changing book, worth its price many times over and still one of my favorite books.)

Still, Cram101's costs are low partly because they are free-riding on Christos' considerable labors. Is a discussion of the larger academic publishing industry really necessary in this case? Again I ask--is this right?

As an independent point, I think amazon's presentation of the product is slightly duplicitous: though it does point out this is not
the textbook, it lists 'Papadimitriou' as the author, and it gives reviews of the textbook in place of reviews of the outline. Also, Christos' book comes up much lower in the search results.

Update 12/02: After being alerted to the Cram101 phenomenon, Christos said he'd see what he could do about it. Now I see that some changes have been made on the amazon page:

i) Papadimitriou is no longer linked to as the author;

ii) The title header has been changed--now it is prefaced as 'Outlines & Highlights for' C.C.;

iii) It now comes up below Papadimitriou's book in searches (though this may have more to do with sales-rank than intentional policy).

These are all positive steps. On the other hand, one still might wish that

i) Comments on Papadimitriou's book weren't displayed with this one, as they still are;

ii) amazon would have the sense to stop selling a book that is not only of questionable legality, but that multiple readers have characterized as a scam that doesn't even deliver the plagiarized content it promises. At the very least they could comment on their decision to sell it, offer customers a look inside this book, etc.

Random Freaky Facts

2007-10-09T14:02:00.000-04:00

While it may not be at all apparent, I've been somewhat particular about the types of posts I make to this blog. I've realized, however, that there should be no real harm in loosening up, and it'd probably increase my post frequency. So today, let me report two theorems that caught my eye in recent weeks. If I had to find a common theme, it'd be: finding interesting constraints in seemingly very unconstrained settings.

1) Let G be an infinite (undirected, simple) graph. Let the 'density' d(H) of a finite subgraph H of G be the fraction of pairs of vertices (u, v) from H that are connected by an edge. Let the 'upper density' d*(G) of G be the greatest number p such that we can find arbitrarily large finite subgraphs H, with d(H) as close as desired to p.

(i.e. for all n, epsilon there exists an H with |H| > n, d(H) > p - epsilon.)

Then, bizarrely, d*(H) must be one of the following numbers: {0, 1, 1/2, 2/3, 3/4, 4/5, 5/6, ...}

This result follows from the 'Erdos-Stone Structure Theory', generalizing Turan's Theorem in extremal graph theory. It is presented, in context, in Bollobas' excellent textbook 'Modern Graph Theory'. Basically, the idea is that, if H is large enough and of density greater than, e.g., 5/6 + epsilon, it must contain a particular subgraph H', of density 6/7.

2) Let X be a probability distribution over R^d. Choose d+1 points independently, each distributed as X. Then the probability p that their convex hull contains the origin, cannot exceed (1/2)^d.

Wild!

Unfortunately, I forget where I saw this last one, or who it's due to, but if I find out I'll attribute it here. I'm, uh, 90% sure I've got the numbers in the statement correct.

Another Heads-Up for Puzzlers

2007-10-05T14:02:00.001-04:00

Two puzzle collections (both drawing on diverse sources) caught my eye recently. The first is 'The Art of Mathematics: Coffee Time in Memphis', by the famous mathematician Bela Bollobas. It's got a number of gems, for instance: is it possible to 'load' two dice, i.e. skew their faces' probabilities, possibly in distinct ways, such that when both are rolled the resulting distribution is uniform on {2, 3, ... 11, 12}?
The book is definitely worth looking at, but, perhaps as a function of its ambition to teach some important (and cool) math along the way, it is rather difficult on the whole, and ridiculously so in some cases (one of his 'puzzles' is to disprove the Borsuk conjecture, a problem that had been open for something like 60 years. Granted, there is a hints section, but come on...). The Amazon page lets you browse a number of the more approachable puzzles, so check it out.

The second is 'Mathematical Mind-Benders', Peter Winkler's much-anticipated sequel to the instant classic 'Mathematical Puzzles: A Connoisseur's Collection'. I haven't spent enough time on the new one to see how it stacks up to its predecessor, but it definitely contains some beguiling problems. Many are 'old friends' of the puzzle genre (bugs, prisoners, hats, etc.), but remade and fiendishly harder--think of the fight with Super Shredder at the end of 'Turtles II'...

However, while Winkler's books are also quite hard, they generally involve much less 'higher math' than Bollobas', which is really written for readers interested in mathematics proper. Another emphasis of Winkler's new book is on surprise answers, as in the following two puzzles from the first, warm-up chapter:

-A pencil has a regular pentagon as its cross-section, and its maker's logo on one face. If the pencil is rolled on a table, what is the probability that it comes to rest with the logo facing up?

-You have 15 bags. How many marbles do you need to produce an arrangement where each bag contains a different number of marbles?

Winkler also unveils a neat word puzzle called 'the HIPE game', something he co-invented as a teenager. One player comes up with a string of letters and challenges the other players to find a word containing it (as a block of adjacent letters): for instance, can you place HIPE in a word? Of course, the problem poser should actually have a word in mind...

Some other challenges he gives: BG, CM, FC, FW... and the book has many more (and harder). I'm normally pretty decent at word games, but this one is killing me so far.

Thanks, Bollobas and Winkler!

In Plane Sight

2007-09-26T14:49:00.000-04:00

Flatland is in tumult after a spate of triangle-on-triangle violence, and the prevailing attitude is one of utter paranoia. The triangles, which can see out of each of their three vertices, are so mistrustful that they will not tolerate the presence another triangle unless they can see each of the other's vertices, and, moreover, see it with each of their own eyes. Triangles are assumed to be disjoint and opaque.

It is your job to help as many triangles as possible congregate, in a fashion acceptable to all participants, to promote dialogue and peace. Find yourself a pen, paper, and a bag of Doritos, and consider:

Problem: Can three equilateral triangles of equal size be placed in a 'acceptable' arrangement? (If yes, what is the upper limit, if any?)

Notes:

-I do know the answer, but it took me awhile. I've never really understood triangles...

-I haven't read Abbott's 'Flatland' since maybe age 12, so I have no idea how faithful this scenario is, or whether related visibility issues were explored in the book. As far as I know this puzzle has not been posed elsewhere, but I do recall there being at least one interesting visibility puzzle in Engel's book 'Problem Solving Strategies'.

-Notice how I refrained from saying 'acute paranoia'... it wasn't easy, but I think I'm a better person for having done so.

Information is not a Substance

2007-09-16T22:35:00.000-04:00

I wanted to share a cool idea from the young field of 'network coding', which explores techniques for efficiently disseminating information over networks like the web. I believe it originated in this seminal paper, which I learned about indirectly by reading Michael Mitzenmacher's very interesting research blog My Biased Coin (which reflects his professional activity in network coding and is a good source; ref. #7 on this link is a good first article to read).

Consider the following directed network:

Here, each of the three top nodes have a stream of data they need to communicate to the node of corresponding color on the bottom. Each edge shown can transmit a bit per second in the direction indicated, and the purple nodes in the middle are willing to assist in communication.

The perverse structure of this network seems to pose a problem: each node on top has two pink edges which are headed towards the wrong parties on the bottom. Since bottom nodes cannot themselves communicate, the pink edges appear useless. It would seem that all information flow must happen thru the black edges, whose bottleneck would allow only one party to get a bit across each second.

WRONG! (puzzle: stop reading and figure out a better strategy.)

Here's the idea: Say the top nodes want to send bits x, y, z respectively on a round. They send their bit on their every available edge. The top purple node receives all of them and computes their XOR, that is, x + y + z (mod 2). It sends it to bottom-purple node, which then broadcasts it to the three receivers.

Then, for instance, bottom-red receives y, z, and x + y + z, so it can add up all the bits it receives to get y + z + (x + y + z) = x, just what it wanted. Similarly for the other nodes. Repeating this process, the network transmits at three times the rate we were led to expect by our faulty initial reasoning (a line of thought which restricted us to the best so-called 'multicommodity flow' on the network).

If these were roads, and we were sending formed substances to their destinations, our first approach would be valid. But information is not a substance--it obeys zany laws of its own, and can at times be merged, fractionalized, and delocalized in unexpected and useful ways (often involving that mischievous XOR). Better understanding the information capacity of networks more complex than the one above is a fascinating and important research frontier--so keep following Mitzenmacher's blog!

Be Rational

2007-09-14T11:15:00.000-04:00

Today, enjoy a home-baked puzzle in real analysis--a somewhat old-fashioned subject that I can't help but love (much like automata theory).

We know that pi = 3.1415... is transcendental, i.e., it is not a zero of any nontrivial univariate polynomial with rational coefficients. Is it possible we could generalize this result?

Part I. Is there a continuous function f: R --> R, such that

a) f takes rational numbers to rational numbers,

b) f(x) is zero if and only if x = pi?

Part II. If you think no such f exists, then for which values (in place of pi) does such an f exist?
On the other hand, if f as in Part I does exist (I reveal nothing!), can it be made infinitely differentiable?

For those new to real analysis, 'weird' objects like the desired f above generally have to be created gradually, through an iterative process in which we take care of different requirements at different stages. We try to argue that 'in the limit', the object we converge to has the desired properties. (Does this sound like computability theory? The two should be studied together as they have strong kinships, notably the link between diagonalization/finite extension methods and the Baire Category Theorem.)

Passing to the limit can be subtler than it first appears; for example, a pointwise limit of continuous functions need not be continuous. Here is a pretty good fast online introduction to some central ideas in studying limits of functions.

Correlation Reversal

2007-09-09T21:44:00.000-04:00

In an earlier post, we discussed Kleitman's Theorem, which tells us that monotone events are nonnegatively correlated. So, for example, if we generate a random graph G, including each edge with probability 1/2, and we condition on the event that G is nonplanar, that can only make it more likely that G is Hamiltonian, not less.

There's a further wrinkle we could add to make things more interesting. By a witness for the event f(x) = 1 on a particular bitstring x, we mean a subset of the bits of x that force f(x) = 1. (This event could have multiple, overlapping or disjoint, witnesses.)

Let f, g be monotone Boolean functions, and consider the event we'll call f^^g, the event (over uniformly chosen x)that f(x), g(x) are both 1 and that, moreover, we can find disjoint witnesses for these two conditions.

Problem: Is P(f^^g) greater or less than P(f = 1)*P(g = 1)?

On the one hand, f and g `help each other' to be 1, by Kleitman's Theorem. On the other hand, the disjoint-witness requirement seems to undercut their ability to positively influence each other. Which tendency wins out?

I'll tell you: P(f^^g) <= P(f = 1)*P(g = 1). The latter tendency prevails, although ironically enough, Kleitman's Theorem can actually be used to show this! It's a not-too-hard exercise in conditioning, which I recommend to the interested reader.

Here's the kicker, though: the inequality above is actually true for arbitrary f, g, not just monotone ones! This result, however, took a decade of work to prove; it was conjectured by van den Berg and Kesten, and proved by Reimer in 1994; see this article. Reimer's Inequality appears fruitful in probabilistic analysis, including in theoretical CS, see this article (which I have yet to read).

On the Move

2007-09-08T16:12:00.000-04:00

Time for a personal update: this week I began a stay as a visiting student at MIT's CS and AI Lab (CSAIL)--a very exciting place to be for a young would-be theorist. For this privilege I have friend, fellow blogger, and new MIT prof Scott Aaronson to thank--thanks, Scott!

While here, I'd absolutely love to meet, get to know, trade ideas or collaborate with any Boston/Cambridge readers. Drop a line or come by my office, 32-G630. I'd also welcome advice on where to eat, how to furnish an apartment on the cheap, how to stop getting lost constantly around town and campus, and all that good stuff.

Speaking of getting lost, a small PSA: did you know that in a long random walk on a finite undirected graph, you can expect to appear at any given node with frequency proportional to its degree? A node's location and degree of centrality in the graph are ultimately irrelevant. Equivalently, every edge gets traversed with the same limiting frequency, and with equal frequency in either direction.

Despite its simplicity, this was an eye-popper for me as an undergrad, and my favorite result in our probability seminar, along with the theorem that the harmonic series 1 + 1/2 + 1/3 + ... converges with probability 1 when each term is instead given a random sign.

Loopy Thinking

2007-08-27T15:43:00.000-04:00

Earlier I posted on the 'backwards orientation' in mathematics, aimed at finding new characterizations or 'origin stories' for familiar objects. Here is an exercise in this kind of math, hopefully amusing.

We'll consider the class of simple, rectifiable closed curves in the plane, that is, non-self-intersecting continuous 'loops' in R^2 to whose segments a definite finite arc-length can always be assigned.

Given two points x, y on such a curve C, let d_C(x, y) denote the distance along the curve from x to y (in whichever direction is shorter). On the other hand, let d(x, y) denote regular Euclidean distance.

We say that a curve respects distances if, for all u, v, x, y on C, we have

d_C(u, v) < d_C(x, y) if and only if d(u, v) < d(x, y).

Now, a circle respects distances in this sense; do any other curves in our class?

Would your answer change if we used a weaker notion of respecting distances? Namely, for all x, y, z in C,

d_C(x, y) < d_C(x, z) iff d(x, y) < d(x, z).

Bonus problem: the analogous question for rectifiable-path-connected, closed plane sets with nonempty interior. Convex bodies respect distances; do any others? (Recall that we previously discussed a very different kind of characterization of convexity.)
It may help to know that between any two points in such a set, there exists a path of minimum length (see Kolmogorov & Fomin's book on functional analysis, Sect. 20, Thm 3.).

More on Couplings

2007-08-25T12:08:00.000-04:00

Last time I described how couplings can be used to establish 'closeness' of two random variables. In fact, the results I stated imply that couplings can always be constructed when RVs are close. That still begs the question of whether couplings are a practical method of analysis for important RVs. Well, they definitely are, although to judge the full extent of it you'd have to ask a probabilist.

Beyond their direct usefulness, however, I think couplings also illustrate a broader idea: that to reason effectively about a probability distribution, it often pays to find new ways of 'generating' that distribution to better highlight certain features. This is something I learned to do by example in my classes, but always with lingering doubts as to the legitimacy of such reasoning and without an explicit awareness of the method and its generality. (Have readers had similar experiences?)

Here's a very simple example--the simplest--as a warm-up. Let X, Y be 0/1 random variables, with probabilities p, q respectively of getting a 1. Say p < q and the two numbers are 'close'.

Even though it is immediate from the definition of statistical distance that X, Y are close as RVs (which does not mean they are correlated!), let's see this in a second way by 'coupling' the variables.

Let T be a uniformly chosen real number in the unit interval. Then we can build a pair of coupled RVs by defining

X' = 1 iff T > 1 - p, Y' = 1 iff T > 1 - q.

Clearly X', Y' are individually identically distributed to X, Y respectively. (We said nothing about the joint distribution of X, Y, so it is irrelevant and distracting to ask if they are really 'the same' RVs as X', Y'. This is the kind of question that used to hang me up.) Moreover, X' = Y' unless T lies in the interval [p, q] (which occurs with prob. p - q). This shows X, Y are close via the coupling characterization of statistical distance.

Hope that was clear; here's another simple example.

Let m > n > 0 be natural numbers, m even. Fill an urn with m balls, half red, half blue. Draw n balls at random without replacement, and record the sequence of red and blue outcomes as a length-n bitstring X_n.

Compare X_n with U_n, the uniform distribution on {0, 1}^n; fixing m, how large can n be before the RVs cease to be close?

First, note the extreme cases:

-if n = 1 the RVs are identical;

-if n = m then they have a statistical distance on the order of 1 - 1/sqrt(n), since then X_n always has a Hamming weight of m/2 while U_n usually doesn't (so, we can construct a succesful distinguisher--recall the other characterizations of statistical distance from the last post).

Let's use coupling to examine an intermediate case: we will show that if n << sqrt(m), the RVs remain close. First, note that U_n can be generated by sampling balls with replacement. Let's sample with replacement n times to generate U_n, but now each time 'marking' the ball we draw before throwing it back in the urn. The marks don't affect the outcome of U_n.

To generate X_n in a coupled fashion, use the same sequence of draws, except that we ignore draws that bring up a marked ball, and we perform additional draws if needed until we record n outcomes.

Standard 'birthday paradox' reasoning assures us that if n << sqrt(m), then with high probability no marked ball is ever drawn, hence the two coupled RVs are identical, as needed.

What is the critical value of n for which X_n, U_n 'part ways' and become distinguishable? Is it O(sqrt(m)), or much larger? I could say more, but I still don't understand the issue as fully as I'd like, so I'll leave it as a (hopefully tantalizing) question for readers.

Next time: couplings applied to convergence of random walks on graphs.

Another Public Service Announcement

2007-08-08T14:16:00.000-04:00

We've all heard that randomness and probability are becoming more and more important in computer science. A number of good references exist for learning the basic techniques of probabilistic analysis. Many of these techniques are radically simple and incredibly powerful, even for solving problems where probability does not seem to play a role (such as design or optimization problems where what is wanted is a highly 'uniform' or 'balanced' structure, e.g. in exhibiting Ramsey graphs, expanders/extractors, low-discrepancy sets, etc.). As such they are a very good investment. One can go very far, for instance, granted only familiarity with the meaning and some applications of the following simple concepts:

-linearity of expectation

-the second moment (a.k.a. variance) method

-union bounds

-Chernoff-style deviation bounds

As I've said in the past, The Probabilistic Method by Alon and Spencer is the most delightful way to develop an appreciation for this stuff. I have blogged before on some of these ideas, and will happily do so again, but today I want to discuss an aspect of probabilistic analysis that receives somewhat less thorough discussion in the references I've consulted.

Namely: given two random variables X, Y, how should we quantify their similarity or difference? As an example of a case where such a question might be important, suppose we have a randomized algorithm that correctly solves some problem with high probability if given access to fair coin flips, but we don't have a 'perfect' source of random bits; we want to find conditions under which an imperfect or pseudorandom source will be 'close enough' to the uniform distribution to play the role of the algorithm's random bits, without destroying its correctness.

Is there one 'right' notion of similarity, or do we need multiple notions depending on application? The answer is, 'both'. There is a very widely useful quantity, called the 'statistical distance', which is effective in many cases, but to recognize these cases it is important to have several perspectives on the matter.

I will present the definition and three variants. I encourage readers to submit any others, and also to point me to official nomenclature and references for the variants (I'm working from memory).

Let X, Y be random variables. Let's say they take on (real-number) values from the finite set {a_1, a_2, ... a_n}, just to keep the discussion nice and safe. Suppose X, Y take on value a_i with probabilities p_i, q_i respectively.

The 'statistical distance' d(X, Y) is then defined as

d(X, Y) = .5 * (Sum from i=1 to i= n: |p_i - q_i|).

(That's an absolute value in there.)

Also denoted ||X - Y||, the statistical distance should not be confused with the L_1 distance, which is just twice the statistical distance when applied to probability vectors.

Readers should verify the following: d(X, Y) is a metric, taking values between 0 and 1. d(X, Y) = 0 if and only if X, Y are identically distributed, and d(X, Y) = 1 if and only if X, Y never take on the same values.

Now consider the three following questions we could ask about X and Y:

1) Say we want to build a 'distinguisher' to tell apart the two variables: that is, a function A: {a_1, ... a_n} --> {0, 1} that maximizes the quantity
|P[A(X) = 1] - P[A(Y) = 1]|. (I believe this is the 'distinguishing probability' of A, but don't quote me.) Call Q1(X, Y) the maximum quantity achievable in this way.

(Note that we could allow A to use additional randomness; it wouldn't affect the value Q1. This is important in applications.)

2) Now say a friend secretly chooses one of the two variables X or Y, each with probability 1/2. She then takes a random sample from the chosen variable and presents it to us. We are asked to guess which sample it came from, and we wish to find a rule that'll maximize our probability of guessing right.
Let Q2(X, Y) denote the maximum achievable probablity of correctness (which again is unaffected by the use of randomness in guessing).

3) Finally, say we wish to design a random variable Z = (Z_1, Z_2), outputting a pair of real values. We require that Z_1 be distributed identically to X
(i.e. d(X, Z_1) = 0), and that Z_2 be distributed identically to Y, but we do not require independence. Our goal is design the pair (Z_1, Z_2) (called a 'coupling' of X and Y) to maximize the probability that Z_1 = Z_2. Denote by Q3(X, Y) this maximum achievable probability.

Now, it is a pleasant fact that all of Q1, Q2, Q3 are completely determined by the value d(X, Y), and conversely, they also each determine d(X, Y) (and each other). Moreover, the quantities are all linearly related, so if you forget the precise relationships (as I invariably do, which motivated this post), they're easy to rederive by considering the extreme cases and interpolating. For the record, here are the relationships:

Q1(X, Y) = d(X, Y)

Q2(X, Y) = .5 + .5 * d(X, Y)

Q3(X, Y) = 1 - d(X, Y)

I recommend verifying these facts once or twice and then taking them for granted. Note that the first two (of which Q1 is more frequently used) are measures of distance, while Q3 is a measure of similarity. Both perspectives come in handy.

Note too that, while d(X, Y) is defined by an equation, Q1-Q3 are defined by an ability to do something; Q1-Q2 in particular are framed around an agent's ability to distinguish between cases, and it is natural that computer scientists often prefer to take such a view.

In future posts, I hope to elaborate somewhat on these perspectives (couplings in particular, which are probably the most interesting).

A Tricky Vote

2007-07-15T18:38:00.000-04:00

An election is being held to select one of two candidates, A or B. n voters turn out in a long, orderly line. A motley crew of pollsters show up to predict the turnout, but none is diligent enough to survey the entire line, or savvy enough to conduct a proper statistical sample. Instead, each pollster arbitrarily selects some single interval of the line and queries everyone in that interval. The intervals may be of various sizes, and they may overlap.

After comparing their haphazard data, the pollsters notice that candidate A, the presumptive favorite, has more than two-thirds support in every survey interval.

Assume the process is 'nice' in the following senses:

-Everyone truthfully reveals their intentions to the pollsters, and intentions don't change;
-Everyone in line eventually votes (once) for their intended candidate, and votes are faithfully counted;
-No one changes position in the line.

Also assume that everyone is surveyed at least once.

Can you conclude that candidate A is the winner?

Note that 2/3 is the lowest threshold one could hope for: for consider 4 voters, with prefereces going B A A B, and with 2 survey intervals consisting of the first three and last three voters respectively; then A has exactly 2/3 support in each, yet the outcome is a tie.

If this problem gives you trouble, try solving it first with 'two thirds' replaced by 'ninety-nine percent'.

I enjoy questions like this one, that try to deduce 'global' conditions from a collection of 'local' observations. With the advent of 'property testing' in computer science, they have become increasingly important to the field. I hope to make further posts on the subject soon, and possibly also discuss generalizations of the above problem (Does anyone know if/where it's been studied before?)

Update, 9/27: I've since learned that this problem falls in well-trod territory of functional and harmonic analysis; specifically, the (affirmative) answer to this problem essentially states that a certain 'maximal operator' over a function space is 'bounded'. The solution techniques described by David and myself in the comments are standard and fall under the rubric of 'covering theorems', the most basic one being due to Vitali. I'll try to blog more soon on what I've learned about this problem, which gets very interesting in 2 dimensions...

Guardian Angel Decoding

2007-07-09T15:26:00.000-04:00

In the conventional setting of error-correcting codes (ECCs), there are three parties: Sender, Receiver, and Adversary. Sender wants to send a message m to Receiver; problem is, Adversary may intercept the message string and modify as many as e > 0 symbols before Receiver gets the message.

The idea of an error-correcting code is to encode the message m in a redundant fashion as some 'codeword' C(m), so that even after as many as e errors are introduced, the original message m is uniquely recoverable.

For a simple example (not representative of the sophistication of more powerful codes), say Sender wants to transmit a single bit of information, and e = 1. Then we could have C(0) = 000, C(1) = 111, and Receiver can correctly recover the message bit by taking the majority vote of the 3 bits received.

For a much more comprehensive introduction of ECCs from a TCS perspective, see e.g. this survey by Sudan, or this one by Trevisan.

Now here's a slightly whimsical idea: suppose we add a fourth party to the scene, a Guardian Angel allied with Sender and Receiver. The Guardian Angel watches Sender encode the message; though it cannot completely stop the Adversary from making its modifications to the codeword, it can step in to prevent as many as d < e of these modifications. These 'saves' are performed all at once, after the Adversary reveals its intended modifications, and the Angel can choose which sites to protect; it cannot make new modifications of its own.

Clearly the Guardian Angel is a boon. Consider an ECC in the standard setting (no Angel) with an encoding/decoding system that successfully recovers messages even after as many as e errors are introduced; the same protocol can recover the message with as many as e + d errors, with the help of a 'lazy Angel' who arbitrarily selects d of the adversary's errors and corrects them.

So here's the question: is this as good as it gets? Or can the Angel act more cleverly to help Sender and Receiver succeed in the presence of even more errors?

Note that we might want to change the encoding/decoding protocol itself, to optimize for the Angel's presence. For example, suppose d = 1; then we can successfully transmit a single bit in the presence of any number of errors, by simply having the Angel encode the intended bit in the parity of the message sent (convince yourself this works). The challenge is to use the Angel effectively while preserving the information rate and other positive properties of our ECC, as much as possible.

This is meant as a puzzle, but a somewhat open-ended one (in particular, one that ought to be investigated in the context of specific ECCs) that feeds into active research in coding theory. I'm hoping it will stimulate readers to rediscover some of the important notions in the area. I'll give hints and/or literature pointers sometime soon.

***

...Ok, here goes:

Hint: 'List Decoding' is a concept which has seen a lot of applications recently. Its starting point is the realization that, if we are willing to not always uniquely recover the codeword after errors are introduced, but instead narrow down the possibilities to a 'short' list of candidate messages, we can, for many natural codes, tolerate many more errors. For instance, with a binary alphabet, we cannot achieve unique decoding for nontrivial codes beyond the threshold of a .25 fraction of errors. On the other hand, if we allow list decoding (say, returning a poly(n)-sized list of candidate messages given a corrupted codeword of length O(n)), then we can tolerate almost a .5 fraction of errors.

For more discussion and references, see this post of Lance's.

So: does list decodability of a code imply unique decodability with the help of a Guardian Angel, perhaps an Angel making only a relatively small number of 'saves'? And if the list decoding procedure is computationally efficient, can the Guardian Angel and its associated decoder be efficient as well?

***

For a more thoroughly whimsical puzzle scenario, check out Conway's Angel Problem.

Paths to Discovery: The Valiant-Vazirani Theorem

2007-06-21T22:19:00.001-04:00

This post aims to give a plausible reconstruction of the discovery process behind the Valiant-Vazirani Theorem, a beautiful and important result in complexity theory. If you haven't heard of this before, don't worry, read on. This theorem's discovery path, which I'll render as an internal dialogue (not portraying Valiant or Vazirani themselves), illustrates well, I think, some characteristic patterns of complexity research.

***

So today is the day... I will prove P = NP via a supremely clever algorithm for Boolean Satisfiability! Let me just arrange my pencils and paper, have a snack, and... let's go!

[Tries, fails; gets another snack; putters.]

Alright, this is hopeless. What is a possible source of the difficulty?

Maybe when algorithms are building up partial satisfying assignments, in different stages they stumble upon fragments of different satisfying assignments, and get caught up trying to combine them in a 'Frankenstein' assignment that doesn't work.

For instance, say we have a formula expressing that the 6 variables all take a common value. Then 000*** and ***111 are fragments of satisfying assignments, but they don't combine successfully.

Is there a specific way to overcome this difficulty, to spot-check fragments for mutual compatibility? Well, that sounds as hard as the original problem.

But what if this problem didn't arise? Maybe I could find satisfying assignments under the restrictive assumption that the formulae I'm given have at most one solution. Such an algorithm would still be useful (e.g. for finding prime factorizations)--and, I'll add, impressive... OK, time for round 2!

[Tries, fails]

Damn, useless! Ah well, it's a hard problem. 'A' for effort, now how about some more chips and salsa?

NO! Keep it together. What did your predecessors do when they failed to solve SAT? Did they throw up their hands and walk away? Or did they invent a sophisticated justification for their own failure? The latter: NP-completeness. They're feeling pretty smug about their 'failure' now... can we do something like that?

Well, ideally, we'd show that solving this restricted problem is JUST as hard as solving general SAT. How would we show this? The general reduction method would be--make sure I've got the directions straight...

We want to find a polynomial-time computable function R mapping formulas to formulas, such that:

-If P is satisfiable, R(P) has exactly one satisfying assignment;

-If P is unsatisfiable, so is R(P).

Then, if we had an algorithm A for our restricted SAT problem, and we wanted to determine the satisfiability of a general formula P, we'd just compute A(R(P)) to get the answer.

But how would such a reduction work? Deciding which assignment to preserve seems like a tall order, granted that we don't even know an efficient way to find any assignment. If we fashioned the formula R(P) as a more constrained version of P, the danger is that we'd snuff out all satisfying assignments. On the other hand, what other technique could we possibly use to build R(P)? We can't allow in spurious new satisfying assignments that have nothing to do with those of P.

Let's stick with the idea of making R(P) a more restrictive version of P, but let's abstract from our problem a bit. We need to stop being tempted by the desire for information that would be useful in the reduction, but is itself NP-hard to compute. Instead of a boolean formula with potentially analyzable structure, suppose we are faced with an arbitrary, 'black-box' 0/1-valued function f on a domain of size m = 2^n. We want to modify f in a way that 'kills' all but one of its 1-values. Can we succeed in this setting?

One way to kill 1-values is to create a function g(x) = f(x)*h(x), where h(x) another 0/1-valued function. Then g is indeed a restricted version of f.

If we choose h(x) = 1, g = f and we make no progress. If we choose h(x) = 0, g = 0 and we have erased the information we need. We need some happy medium, but we don't have the resources to analyze f in any meaningful way while producing h.

Thus, the idea of letting h(x) be a random function is almost forced on us! Let's try it. (Note that at this point we are more or less committing to a reduction with some probability of error... oh well.)

Oops, there's a problem: suppose that f has many 1-values. Then the probability that g has at most one 1-value is very low. We could instead let g(x) = f(x)*h[1](x)*...*h[j](x), for a larger number of random functions, but this would almost surely kill all the 1-values of f if there were few to begin with.

Luckily, the range of sensible choices for j isn't too large: if j >> n, then almost surely all 1-values of f are killed off. So let's just plan on guessing the 'right' value of j for the f we are given.

Does this approach do what we want it to? Is there with fair probability some j where g(x) = f(x)*h[1](x)*...*h[j](x) has only a single 1-value? Let's think of multiplying by the h[i]'s sequentially--with each stage, each 1-value in the 'population' is independently 'killed' with probability 1/2. It seems not unlikely that at some stage exactly one remains (call this event 'Isolation'). [Try verifying this.] And since we can guess the right j with at least an inverse-polynomial probability, if we repeat the experiment a poly(n) number of times, we should succeed in Isolation at least once with high probability--assuming f has any 1-values, of course.

There is one hurdle: choosing even a single truly random function h on n bits is computationally expensive, since almost certainly this h takes around 2^n bits even to describe. We can't afford this. Is there some smaller stand-in for this sample space, that is 'random enough' for our purposes? Maybe 'pairwise independence' of the values of h is enough (this is the condition that, for any x != y, the values h(x), h(y) are independent of each other)... [Show that, indeed, this is true: Isolation occurs for some j with probability at least 1/8.]

If so, each random function h[i](x) can be replaced by the much more concisely represented function (a*x - b), where a is a random n-vector and b a random bit. These can be added (in conjunctive form) to the formula representation of f, allowing us to work within the original problem framework.

Let's review the technique: given our formula f, we repeatedly produce functions of form g = f*h[1]...*h[j], where j is random and the h[i] are mutually independent and individually pairwise independent over their domain. If f has a 1-value, then each g has exactly 1 1-value with non-negligible probability, so if we repeat many times, with high probability we achieve Isolation at least once, and our assumed algorithm for finding unique satisfying SAT assignments finds a solution to this g, which is also a satisfying assignment to f. If we don't find such an assignment, chances are f was unsatisfiable to begin with.

***

(I left some of the final steps as exercises both because they're nifty, manageable puzzles, and because they're not distinctively complexity-theoretic.)

What are the methodological ideas illustrated here? Let's see:

-Don't single-mindedly pursue goals (like showing P = NP); look for more modest achievements (like finding unique satisfying assignments), that attempt to remove some important perceived difficulties (here, 'interference' between multiple satisfying assignments).

-Sometimes seemingly modest goals, like this one, are essentially as difficult as the original problem. Keep this in mind, and be explained not just to report success, but also to explain failure.

-Try stripping away problem details that one doesn't know how to exploit effectively (here, by 'forgetting' the logical structure of the input formula).

-When you don't know what to do, try acting randomly. Be prepared to sacrifice in the process: here, our reduction can't prove that producing unique assignments is hard from the assumption P != NP; we must resort to the assumption RP != NP.

-Limited randomness is often almost as effective as full randomness, and much cheaper. k-wise independence (and, in other settings, almost-independence) are one such example; 'min-entropy' is another. On the other hand, it can be conceptually simpler to initially design algorithms with full randomness in mind (as we did), then inspect the analysis to see the extent to which derandomization is possible. In fact, more randomness-efficient versions of the V-V Theorem do exist (I will try to track down the papers).

I'm thinking about a 'Paths to Discovery' sequel on hardness-of-learning results, another area (also bearing the mark of Les Valiant) where the theorems are ultimately simple, but the challenge is determining the right form and target of the reduction. Any feedback, or other suggestions?

Flooding and Kleitman's Theorem

2007-05-30T18:21:00.000-04:00

In their classic, and highly entertaining, survey book on probabilistic methods in combinatorics, Alon and Spencer pose the following question: suppose we generate a random graph on n vertices, independently including each edge with probability 1/2. Suppose we do not look at the graph right away, but are informed that the graph we got contains a Hamiltonian path, that is, a path visiting each vertex exactly once.

Does this knowledge make it more or less likely that the graph is nonplanar?

Of course, it should make it more likely. Please stop and verify that this ought to be true. Can you prove it?

Results that prove facts like this are called 'correlation inequalities', and the simplest one that applies here is called Kleitman's Theorem. (In Alon and Spencer, Kleitman's Theorem is derived from more general results, but I encourage you to try to prove it directly.)

Say a subset A of the Boolean cube is monotone if, whenever x is in A and y >= x (bitwise domination), then y is in A too. We may also say that A is 'upwards closed'.

Kleitman's Theorem states that, given two monotone subsets A, B of the Boolean cube, if we pick a random cube element z, the chance of z being in B cannot decrease if we condition on the event that z is in A.

So, in the example, let the bits of the cube represent the presence/absence of edges in a graph of fixed size. Let A and B be the properties of Hamiltonicity and nonplanarity, respectively. Then Kleitman yields the intuitive fact we were looking for.

***

Now I am going to describe how Kleitman's result solves the previous flooded-city puzzle I posed last time. In fact, trying to reprove Kleitman's Theorem was what led me to pose the flooding puzzle in the first place, although I now tend to think of Kleitman's as the logically prior result.

To do this requires an easy generalization of Kleitman's Theorem, where we replace the boolean cube in the statement with {0, 1, ... m}^n. So, e.g., vector (3, 4, 5) dominates (3, 3, 4), but is incomparable with (4, 0, 0). In fact, we'll only need this result for n = 2.

Create a bipartite graph U x F, with unflooded houses on the left and flooded houses on the right. Add an edge from an unflooded house h to a flooded house h' if there exists an h-to-h' path with all steps running north or east.

Given a set S of unflooded houses, let N(S) denote the flooded houses adjacent to some house of S in the bipartite graph.

In the example above, the green-circled houses are S and the orange-circled flooded houses are N(S).

Each unflooded house contains a unit amount of water to be delivered, while each flooded house needs an amount |U|/|F| of water delivered, which can only be delivered from a house that is adjacent in the graph we defined. Then, by a version of Hall's Theorem, not difficult to derive from the original formulation, the delivery plan we seek exists if and only if for every subset S of U, the total water-need of N(S) meets or exceeds the amount of water available from S.

Suppose that the desired allocation does not exist. Then by Hall's Theorem, there exists some subset S of U such that the water supplied by S exceeds the need of N(S).

We take such an S and iteratively add into S all the unflooded north- and east-neighbors of houses in S. This doesn't increase the size of N(S), but it does increase the amount of water supplied by S, so the resulting modified S is still a witness to the impossibility of our desired allocation.

We repeat this until the union of S and N(S) is upwards-closed. Call the resulting set S'. Since S' supplies more water than N(S') demands, the ratio |S'|/|N(S')| exceeds |U|/|F|.

If S were as in the example above, S' would be the purple-circled set of houses below:

This means that, if we pick a house at random from within the union of S' and N(S'), we are less likely to get a flooded house than if we picked a house uniformly at random from the whole city. This means that, in picking uniformly from the whole city, the (upwards-closed) event of getting a flooded house is negatively correlated with the upwards-closed event of getting a house from the union of S' and N(S')--a contradiction to the generalized Kleitman's Theorem.

We conclude that the desired delivery plan exists, and can be found in polynomial time using known algorithms for bipartite matching.

Not Social Commentary

2007-05-23T22:45:00.000-04:00

There's been some unfortunate flooding in Grid City:

The water swept in from the Northeast, so if any house is currently flooded, and it has neighbors to the North or East, it's a safe bet they're flooded too. (Other than this fact, and the grid layout, you should disregard the specifics of the map given.)

The water is low and flooded houses are still livable, but they need tap water. In a show of social cohesion befitting Grid City, each non-flooded household immediately donates 50 gallons of water to the effort. The goal is to distribute this water evenly among the flooded houses, and there is no shortage of volunteers to help. Also, quantities of water can be poured and combined or subdivided with precision.

But water is heavy and, let us say, has to be carried around on foot, so some plan is needed. An ideal of efficiency would be that water is never carried in the South or West directions.

Can both objectives be met simultaneously?

***

In the next post, I'll explain how this puzzle came up and my solution. But I'm curious to hear other approaches first, if you care to try.

Dogs in the Mineshaft

2007-05-16T23:41:00.001-04:00

A couple posts ago I described some shenanigans with cats in a binary tree.
But that was just the front yard. The back yard is worse: it contains the opening of an old mineshaft that descends infinitely far into the earth's depths.

Well, there's some funky smell down there that dogs just have to investigate. So, every day, some finite number of dogs may enter or go further down the (unbranching) shaft. They never go back upwards. Here's the scene:

As before, you've got angry owners on your hands. You refuse to close off the shaft (it's too nifty) but again you're willing to try and ensure that any individual dog descends only finitely far into the shaft. Your tool this time: it turns out that after enjoying a good steak, a dog will curl up and fall asleep indefinitely.

The difficulty is that, before eating any steak you give it, the dog may carry it arbitrarily far further down the tunnel. If it passes sleeping dogs, they may be awakened by the steak aroma, and resume their descent.

Money, time, and steaks are no object, and you can outrun the dogs, who won't smell the steaks if they're sealed in your coat pocket. Can you keep your promise to the owners?

To get you started, consider a simple but unsuccessful strategy of giving a steak to every dog every day. The problem is that some dog D may have a sequence of 'accomplice' dogs: every time D falls asleep, a new accomplice will run into the tunnel and hang out above D in the shaft. When you give the accomplice a steak, it'll scamper past D, who'll rouse and go further. In fact, it may happen that every dog goes infinitely far down the tunnel!

Another simple idea is to give a steak every day to the dog furthest down the tunnel, if that dog is not already asleep. This avoids ever waking up sleeping dogs (assuming that the previous day's steak has had its effect; if not we can just wait longer), but it falls victim to a 'rear-guard' attack: a dog that trails constantly just above/behind the current leader.

***

This is a challenging puzzle (unless there's a glitch in the set-up, which I've checked over). But it's well worth thinking about, because the solution strategy--the 'finite injury' or 'priority' method of Friedberg and Muchnik--revolutionized computability theory. Some would say it marked the end of its comprehensibility to outside observers, but I'm optimistic that is not the case. The ingenious strategy is lovely, simple, and, fingers crossed, easier to see in a puzzle setting. I will discuss the solution in a future post, so stay tuned.

Update: Scratch that, Gareth Rees has solved the puzzle and clearly explained the solution for us, in the comments section of 'Trees and Infinity, part III'. I may still talk more in the future about its significance to computability.

Feed Me

2007-05-14T20:14:00.000-04:00

A note to readers: I now have an RSS feed, accessible on the right toolbar ('Atom'). When used with appropriate software/sites (I have feeds on my homepage at My Yahoo), this will let you know when I've put up a new post--useful for a blog like this, where posts come strictly at random intervals. As always, I encourage feedback, which will bring more-frequent and more closely-tailored posts.

I try not to do throwaway posts, so how can I salvage this one? Hmm... a puzzle suggests itself:

Modern undergraduate that you are, you're watching bootleg 'Scrubs' episodes on your laptop. This goes on for three hours or so. Meanwhile, your site-feeds page occasionally updates to display someone's new blog post. When your favored blogs post, the content hits your feed within 10 minutes, but the precise delay is nondeterministic--could be 0, 10, or anything in between.

You register the order in which the feed updates come in. Now: is there an efficient method to calculate the number of 'true orders' in which the bloggers could have made their updates?

For example: say updates A, B, C came at 12:30, 12:35, and 12:41 respectively. Then this is consistent with the true-orders ABC, BAC, ACB, but not with, e.g. CAB. Thus the answer here is 3 ways.

Good luck! Does your method work if each individual blogger has their own (known) interval of possible delays?

Clarification: I haven't solved this problem. It might be #P-complete, and the proof of this might be very technical. It seems related to work on counting linear extensions of posets (which is #P-complete in general), discussed by Suresh here.

The 'Sack of Potatoes' Theorem

2007-05-14T16:13:00.000-04:00

Tired of packing ham sandwiches for lunch every day? Have some spuds for a change.

You've got a countable collection A_1, A_2, A_3, ... of potatoes. A potato is a convex body of diameter at most 1.

(That is: if p, q are points in a potato P, P also contains the entire line segment between them; furthermore, p, q are at a distance at most 1 from each other.)

Furthermore, most of these spuds are incredibly dinky: the total volume of the entire collection is at most some finite value v, say, 4 cubic inches. You'd really like to eat them all.

Trouble is, mashing or cutting them up beforehand would ruin their freshness. You want to bring them all to work whole in your lunchbox.

Prove that these spuds can be packed into a box of finite dimensions. In fact, such dimensions can be computed solely in terms of v, independent of the precise shape of the potatoes.

***

How to get started on a puzzle like this? One should try to find a sequence of reductions to simplify the problem. So, first, suppose we could do it for rectangular potatoes. Show how to pack a single potato of volume c into a box of volume at most a constant multiple of c, also with bounded diameter. Then, if you can pack these boxes (which have finite total volume), you've packed the potatoes they contain.

I solved the 2-D case, but haven't yet worked on 3-D or n dimensions (where it is also true). I read about this result in a charming volume: The Scottish Book, a collection of research problems (some simple, some still open) compiled by high-caliber, and very imaginative, mathematicians, including Ulam, Banach, and Mazur, who met regularly in the 'Scottish Coffee House', confusingly located in Lwow, Poland, during the '30s. Their book of problems was kept there by the management and notes the prizes--'A bottle of wine', etc.--offered for various solutions. It's definitely worth looking over, both for its diverse contents and for the image of mathematical community it offers.

Trees and Infinity, part III

2007-05-08T23:28:00.000-04:00

(Hat tip to Gareth--my first fan art!)

Today, a computability theory-inspired quickie puzzle. Can you face down the infinite in its many guises?

Cats in a Tree

Some GMO-contaminated sludge washed onto your property during the latest freak weather event. A few weeks later, a mysterious tree has sprouted on the lawn, and its progress is astounding--every day, a new layer of binary growth appears:

This would be peachy, but there's a problem: your neighborhood suffers from a plague of cats. Mangy, poorly drawn, tree-climbing cats:

On any given day, some (finite) number of cats may start climbing the tree, or continue their climb from a previous day. What they don't know how to do is come down, not even a single level.
The cats all have irate, protective owners. They want you to cut down this cat sinkhole at once (after rescuing their pets). But you're not going for that--you want the world's largest tree, with unending growth.

Here's the compromise you'd like to offer the owners: a guarantee that every cat C will eventually be prevented from climbing above some level n (which may depend on C).

To achieve this, you have the following means: on any day, you can climb to any number of nodes of the tree and strip the bark there, preventing further growth above the stripped nodes.
Of course, stripping the root node would stop the cats. The challenge, again, is to achieve unending growth as well (though not necessarily the full binary tree).

Good luck!

***

This puzzle models the theorem that there exists an infinite recursive tree with no infinite recursive path. (Interestingly, however, no recursive tree T can have the Halting problem computable with the aid of an arbitrarily chosen infinite path from T. Promise problems are subtle...)

Can the whole theory of computability be 'sweetened up' this way, like the Flintstones vitamins I gobbled up in my youth? Here's a proposal: once students understand programs' capacity to simulate other programs and other computational models, dovetail search procedures, and other 'infrastructural' techniques, it may be preferable to actively 'forget' the computational statement of a problem one aims to prove.
So, in the above puzzle, the cats correspond to different simulated programs in an enumeration, but we are so profoundly unable to predict in advance the behavior of these programs that it might be better to think of the situation adversarially--hence, mischievous cats who do just as they please.
Of course, one could also make a case for the aid to visualization, and possibly generalization, given by the metaphoric puzzle format, but here I mean specifically to ask whether metaphors might help students develop a stronger familiarity with the black-box methodology of computer science.

Next time: the Finite Injury method!

The Antichain King

2007-05-03T21:57:00.001-04:00

Some readers should be familiar with the classic Kruskal-Katona Theorem. Well, legend came to life today... Gyula O. H. Katona (of the Renyi Institute in Hungary) just came to our department and gave a talk about his main area of expertise, extremal set theory.

Sperner's Theorem was the result that launched this now-sprawling field. It addresses the following question: How large a family of subsets {S_1, ... S_m} of {1, 2, ... n} can we find, such that no S_i contains another S_j? (Such a family is called an antichain in the lattice of subsets of {1, 2, ... n} partially ordered by set inclusion.)

Sperner states that the collection of all sets of size (floor-of-) n/2 gives the biggest such antichain you could hope for. It's clear that this set is a maximal antichain (can't be augmented); the claim is that it's also globally optimal.

Katona mentioned some nice applications of Sperner's Theorem. Here's a cute one: given a set of real numbers all greater than 1, use Sperner's Theorem to bound the number of subset sums taking on a value in any interval [x, x+1), x a positive real. This bounds the concentration of the random variable that outputs a randomly chosen subset-sum.

He mentioned many generalizations as well. Sperner's Theorem can be viewed as a statement about the number of sets necessary to guarantee an ordered pair, but we can ask about guaranteeing ordered triples, diamonds, or any poset P for that matter. He and colleagues have results of this form, and he conjectures that for any poset P, there exists a constant c depending only on P such that, for all n, there exists a maximum P-excluding family of subsets of {1, 2, ... n}, such that all sets in the family have size in the range (n/2 - c(P), n/2 + c(P)). So, the structure of optimality in Sperner's result could extend way further (Erdos proved a result of this type for all chains P).

Finally, Katona mentioned the 'group testing' problem that first drew him into this whole web of intrigue:

Given n, r, there are n boxes, r < n of which contain (say) radioactive material. We can in one step test any subset of the boxes for presence of radioactivity (but get no sense of how many radioactive boxes are in the group, just 'some' or 'none'). How many tests are necessary to determine the r hot boxes?

Sperner theory is relevant to the nonadaptive-query case.

Well? Can you see such an elegantly posed question and not try your hand at it? Thanks, Professor Katona!

Where Does Convexity Come From?

2007-04-22T17:59:00.001-04:00

I sometimes find it useful to distinguish between 'forwards' and 'backwards' orientations in mathematics. Given some object or family X, we can (in the 'forwards' direction) see what the existence of X entails--what kind of X there are, what more complex objects we can build out of X, etc.

In the backwards direction, we try to tell an 'origin story' about X. What is the question for which X is the answer? What is the process of which X is the result? There's usually no unique answer, and working in this direction gives a measure of creative freedom.

One important subset of backwards-focused activity is finding 'variational characterizations' of concepts. This means looking for maximization (or minimization) processes underlying the formation of the objects X. So, e.g., spheres at first sight seem like the most boring objects in geometry--they're easy to describe, they look the same from every direction, etc.--but the fact that they enclose volume with maximal efficiency is profound, and leads quickly to even deeper math when you look at double bubbles, tilings of space, and so on. Nature often 'tries' to minimize certain potential functions, and social agents try to maximize various perceived benefits, so whatever your area of interest, variational characterization may be an important way of making sense of observed patterns.

Here's a simple example. Why should we study convexity? I'll give a variational characterization from an economic perspective, which gives an origin story for a broad class of convex functions.

***

Peggy and Otto are friends, with different attitudes about nutrition. Peggy thinks it's all about the protein; Otto is buzzed over Omega-3 oils. (They read different magazines.)
In the first flush of enthusiasm for their new health ideas, protein and Omega-3's are the only food variables they care about.

This raises an issue whenever they buy food together: who gets what part of the food item? Ideally, they'd separate out the two key ingredients in a centrifuge, but for now, food items should be assumed to have, in each region, local 'densities' of the two nutrients that are nonseparable. The best the friends can do is break the food into tiny bits, estimate the protein and Omega-3 in each, and use this information to decide on an allocation.

We're not sure what's 'fair', exactly, but we can describe the 'frontier' of best possible trade-offs between Peggy and Otto's perceived benefits. Given a food item, define a function f(x) to be the maximum amount of Omega-3 that can be consumed by Otto, subject to the constraint that Peggy gets at least an x amount of protein.

Then f maps nonnegative reals to nonnegative reals. Moreover, it's convex down on the region where it's positive, that is, its underside is a convex body:

Why? Intuitively, we arrange the crumbs of the food item in increasing order of their protein-to-Omega-3 content ratio. As we begin giving Peggy more and more protein, we initially can do it most 'cost-effectively' by feeding her the crumbs for which this ratio is highest, but as we go on we are forced to give up more and more Omega-3 for each marginal unit of protein.

I leave it to hard-core readers to fill in details about exactly when this logic can be made rigorous; I have in mind continuous additive set measures over a compact set, and by 'maximum' I mean 'supremum'. However, I regard this result as 'morally true' (a phrase I adopted from Prof. Thomas Hunter at Swarthmore), that is, true with 'reasonable' assumptions and relatively robust to changes in the model.

What's more, the converse is also true: given any such function f(x) (nonnegative-to-nonnegative, convex down on its bounded support), I can make you a food item such that f(x) represents the set of optimal trade-offs between protein and Omega-3's.
($19.95 shipping and handling. Warning: product may taste like a soggy brick.)

So there you have it: a variational characterization of convexity, a 'recipe' if you will, with additive measures and optimization as the basic ingredients. Since many results in theoretical economics assume convexity of various types, recipes like this one (which is not new, but amounts to folklore as far as I can tell) are an important part of the 'pre-theory' of the discipline, motivating and making plausible such assumptions. Challenges to the use of these assumptions, then, should critically engage the pre-theory, for instance, by identifying cases, in both production and consumption of goods, where interaction between inputs makes additivity unrealistic. In the case at hand, of course, we know that the two friends are both wrong--nutritional 'value' is not an additive function of food consumed, as e.g. fats and protein are both necessary. (It's not even clear that nutrition should be considered a real-valued function, since there are multiple health/fitness goals one might be interested in.)

***

I'll end with a question to the readers: I am interested in the origin stories of probability distributions, and have from time to time skimmed over the literature regarding the trendiest distributions of them all, the power laws. I know there are a multitude of settings that give rise to them. So which ones should I study, and from which references?
I have no single criterion in mind, but am receptive to any of the following: rigor, interest, plausibility, generality, simplicity. I am also interested in critical analyses of the apparent power-law 'gold rush' in complexity studies. Thanks!

Out of My Depth

2007-04-22T01:45:00.000-04:00

You are in a pitch-black room. But don't be alarmed.

Someone is pouring liquid at a slow, uniform speed into a thin, transparent vessel; it is pooling at the bottom. The fluid itself is dark, but when in direct contact with the atmosphere it glows purple. So what you see is precisely the evolving shape of the fluid's surface. It seems that you stand to learn something: the shape of the inside of the vessel will be gradually revealed in cross-sections.

But wait--this seems to rely on the assumption that the vessel itself is not moving. Suppose, instead, that the vessel is almost perfectly weightless, and may roll as the heavy liquid's center of gravity shifts.

Can you reconstruct the vessel's shape in this case?

I'm curious to know, but probably underequipped to solve this question, which was the result of a momentary hallucination during a long concert. There are some potential messy issues with cusps, and questions of whether the vessel is open at the top, etc., to which I advise that one assumes whatever makes the problem interesting or tractable.

Money Colliding at High Speeds

2007-04-15T01:39:00.001-04:00

Are there any gamers among my vast readership? Here is a simple auction-based card game I once toyed with; I'm curious what others think, and how it might be souped up for greater replay value.

For two or three players. Each receives all 13 cards in a suit, which they hold privately; the remaining suit (diamonds) is shuffled and put face down. On each round, a diamond card is flipped face up; players simultaneously submit a 'bid' card from their suit. The highest bid gets the diamond (ties can be handled in one of several ways, suit yourselves), and all bid cards used get discarded.

To score when all diamonds have been auctioned: each player gets m points for the m of diamonds, 11 for the jack, etc.

This game can reach a maniacal level of second-guessing--exciting, but perhaps too little in the way of underlying strategy and calculation. It is easy to show that no deterministic strategy is 'undominated' (i.e. there is always a victorious counter-strategy); but I don't see that any simple randomized strategy is undominated either.

Suggestions? Pointers to successful auction games already on the market? I'd look into them myself, but then half of my attraction to the auction genre is that I'm a cheapskate.

Math and MarketThink

2007-04-13T18:45:00.000-04:00

I recently stumbled upon a book that made me really happy. It's called 'No One Makes You Shop At Wal-Mart: The Surprising Deceptions of Individual Choice', by Tom Slee (who has a very nice blog going as well, called Whimsley). This is a clearly written, engaging treatment of classic game-theoretic situations as encountered in consumer decision-making. It outlines what I think are some of the simplest and most powerful ways to challenge the thesis that consumers can reliably 'vote with their dollars' to promote the goods, services, social structures, and way of life that they most value.

I say 'challenge', not 'refute'. Slee takes a patient approach, showing readers how to construct simple economic models and reason about their consequences. The models, in fact, are deliberately oversimplified in order to isolate patterns and identify their potential recurrence in a variety of situations.

Slee's title example is a schematic fable of the rise of big outlet stores on the fringes of town: Wal-Mart comes in, underprices the smaller and economically interdependent downtown stores; consumers, who value access to a vibrant downtown, nevertheless 'selfishly' shop at Wal-Mart when it suits them, relying the patronage of others (upon which they 'free-ride') will keep downtown afloat. Downtown declines, and consumers are (potentially) all made worse off as a result.

This little story alone is (as Slee recognizes) hardly an indictment of Wal-Mart. But it is an internally consistent model that is no more schematic than the implicit model of commerce (which Slee calls 'MarketThink') underlying much economic discourse. It puts failure of 'market democracy' on the table as a thinkable, plausible outcome; as such it can shift the terms of debate and orient more empirically-grounded investigation.

As I see it, unregulated free markets, and crude forms of MarketThink, have at least two serious weaknesses:
1) they fail to adequately address concerns about equity and the welfare of the worst-off;
2) they fail to give adequate provision of public goods (like clean air and water, nature, community development, etc.), and they overproduce public 'bads' (like traffic), with similar potential problems involving fashion goods, network goods, and other goods proeducing 'externalities' of various types.

The claims of the disadvantaged upon public conscience and policy in the US have, on the whole, come a long way in the past century; but as no objective measure of human welfare has been widely accepted, their foothold within economic theory remains tenuous. GDP, 'consumer surplus', and other measurable constructs--generally biased towards markets and equity-insensitive--serve as dominant proxies for human welfare. Problem 1) poses a serious challenge, in discourse as well as on the ground.

On the other hand, problem 2) (which is Slee's focus) has (to an extent not realized by many people) long been recognized and taken seriously by economic theorists. The 'Welfare Theorems' inspired by the writings of Adam Smith, which undergird the general confidence in markets by neoclassical economic theorists, explicitly assume away the possibility of goods whose production and consumption directly affect anyone except buyer and seller. (They also make a certain technical assumption, involving convexity, that is meaningfully restrictive and worth pondering--another post, maybe.) Economists have acknowledged real-world violations of these assumptions, and proposed various remedies (often market-based), at least since Pigou in the '30s. Game theory has expanded and clarified these debates (as Slee shows, while also showing how little in the way of 'hard math' is really involved to make the basic points).

Still, the Welfare Theorems form the 'core message' of most introductory econ texts I have perused or studied from, and the Invisible Hand is the most pervasive idea (often implicit) in popular discussions of markets. Further, I believe that many critics of market absolutism have, in their suspicion of economics, insufficiently tapped the Prisoner's Dilemma and related ideas of game theory, which combine

-simplicity;
-generality;
-memorability;

-establishment credentials and currency within the discourse of economics, without being dependent either on the crudest assumptions (e.g. "money's all that matters") popularly and incorrectly attributed to that field, or on assumptions and concepts foreign to it;

-considerable integrity and truth.

This is not to say game theory doesn't have shortcomings--it does. Nor is it to say that game theory points the way to any clear solutions to the dilemmas it diagnoses, or that any rival to market liberalism can definitively solve them. Again, Slee's book doesn't aim to describe a master theory, or match theory to observation, or save the world. Instead it illustrates that mathematics can help us think (and argue) about social reality without laying claim to full knowledge, denying the world's complexity, or suppressing and devaluing the unmeasurable. This alone is enough to make me hope 'No One Makes You Shop At Wal-Mart' gets widely read.

Math for Little People

2007-04-08T23:51:00.000-04:00

I'm 22. There's a part of me that's asking: "Why haven't you proved any great theorems yet?" But I can't beat myself up too much over this--with Republicans in the White House, and with so much HBO magic happening lately, the odds are stacked against me.

But there's a different kind of math anxiety creeping up: one of these days, I might have kids. Those kids are going to be curious about the world around them, and they're going to look to me for answers--at least when their mother isn't around.

For the most part, I'll be happy to fend them off with a mix of idle speculation and propaganda. But... what if they ask why honeycombs have six sides?

What if they want to know why scooting towards the middle of the see-saw makes you go up? What if they ask why the rubber chain-links on the swing don't ever come apart, if they're not 'connected'? Could I in good conscience give sloppy answers to questions I know involve beautiful math?

I know the Feds wouldn't come and take them away; I know the kids won't be too disappointed; I know their appetite for rigorous proof will come slowly, if at all. But could I live with myself? No, I've got to get a better grasp of the 'basic facts' of life in our spatial world before I help bring someone new along, if only for my own sake.

But what are these? It's up for grabs, but here's the category I've had in mind mostly: qualitative features of structures, arrangements, and movement, observable by 'medium-sized' agents like children, and generated by/consistent with a naive 'block-world' understanding of matter and physical law (not referring to the AI environment of that name, but in a similar spirit). This is the conceptual space in which I've lived most of my life (and thought about discrete math and computer science), and if it's good enough for me it's good enough for my kids. Molecules and lightning bolts I won't sweat so much, but Block World I want to get right.

So then... how to pick out, think about, and explain its most important facts?

Some of them are, I think, topological, as I've alluded with the swing example. But kids won't swallow homotopy theory any more than they'll eat lima beans, even if I can still remember it by then. Anyways, there's a potential save here: Block World is basically discrete, so the space of 'topological' deformations of objects is much smaller and more well-behaved (I've already posted on discretization in topology).

A good place to start would be the Jordan Curve Theorem, famed for its difficulty in spite of its surface obviousness: what could be clearer than the fact that a non-self-intersecting loop in the plane divides the plane into two components, 'inside' and 'outside'?

As one discrete formulation, consider the loop as a path on the grid, where each step in any direction is of even length. Then it appears that the inside is path-connected, also by grid paths (without the even-length restriction), and separated from the outside. For example:

I think this problem is excellent fodder for thought, and I would encourage anyone who's been scared away by the Theorem in the past to work on it in this friendlier setting.

No hints, though--would your kids respect you?

(Clarification for concerned parties: there are no children on the horizon; I do believe in responsible parenting; and I don't get HBO, although I do swear by Curb Your Enthusiasm.)

Assignment Testing and PCPs

2007-04-05T14:36:00.000-04:00

Would anyone like to improve their understanding of the PCP Theorem? This is, in my opinion, the most amazing result in all of computer science, and with the recent work of Irit Dinur its proof should be within reach of a much larger audience. However, there is still considerable complexity involved.

I recently finished writing an expository paper called Building Assignment Testers that presents one key step in Dinur's proof, the step which is most algebraic and most indebted to previous PCP constructions. In my paper I state the PCP Theorem, build and analyze 'assignment testers', and explain why this step is also sufficient to give a weaker version of the PCP Theorem, in which the proof string supplied by the prover is not required to be polynomially bounded.

Several good references are available already, but in the paper I explain why I hope my work represents an expository advance. Essentially, I aim to make clearer how assignment testing can be viewed as a natural composition of simple statistical tests, and how these tests can be first analyzed in isolation, then combined by a general lemma.

For anyone who saw and enjoyed my talk on Property Testing, or read the Powerpoint, Assignment Testers are an important and very interesting application of the testing paradigm--a natural next step for study.

Enjoy the paper! Of course, I welcome questions and comments.

Public Service Announcement

2007-03-27T12:32:00.000-04:00

I'd like to share a heuristic for problem solving in mathematics. It is easy to state and apply, and seems very useful, but many students I've talked with or tutored seem either not to have learned to use it, or not to have recognized its role in their thinking.

Here it is:

When attempting to prove a statement, try to find a logically equivalent statement (e.g. the contrapositive) whose hypothesis and conclusion are more 'constructive'.

What do I mean by 'constructive' statements? Ones which assert the existence of objects, preferably small, easy-to-exhibit ones. By constrast, universal statements, often asserting the nonexistence of certain objects, are 'nonconstructive'.

Here's an example:

Claim: A connected metric space with more than one point is uncountable.

If you're familiar with these terms (wiki them), it should be clear that hypothesis and conclusion are both nonconstructive. Thus, try to prove the contrapositive instead:

A countable metric space with more than one point is disconnected.

This way, we start with an enumeration of points and try to construct a separation.

This strategy is related to 'proof by contradiction', but I'm trying to give some sense of when such strategies are likely to succeed. An example from complexity theory, where this heuristic is close to the heart of our existing methodologies:

Karp-Lipton Theorem: If the Polynomial Hierarchy is infinite, then NP does not have polynomial-sized circuits.

This form of the statement gives the 'lesson' that we want to take home: one plausible complexity hypothesis implies a further kind of complexity. But the proof (like most complexity proofs) is constructive, showing how one kind of simplicity (small circuits for NP) implies another (a PH collapse).

Finally, a beloved classic, arguably prophetic of diagonalization: the infinitude of the prime numbers. This time we find a more constructive equivalent statement that is not quite a contrapositive: 'given a finite list of primes, there exists a prime not on the list'. Then we show a simple algorithm to produce such a missing prime (and if you haven't seen this, I strongly encourage you to try.)

NOOOO!!!!!!!!

2007-03-26T10:01:00.000-04:00

All good things must end (in polynomially-bounded time, naturally). Today, sadly, brings the announced retirement of one of my favorite blogs, Computational Complexity by Lance Fortnow.

Lance's blog didn't introduce me to the field (that honor goes to my high school graduation present, Papadimitriou's textbook), but it did much to orient me to current research, conceptual trends in complexity, and the culture and institutions behind the theory. Having gone to a small liberal arts college without much in the way of CS theory, this was invaluable.

Lance's four decades of Favorite Theorems in complexity are a great read, and his early posts build complexity literacy with a Complexity Classes of the Week feature. Along the way, of course, we got Lance's perspective on life, love (in a profession rife with geographic insecurity and perceived nerdiness), and truly appalling food.

Thanks Lance! Your posts will be missed.

Update: The blog is back, with frequent guest-poster Bill Gasarch taking over for Lance. Cool!

The Vulcan in Me

2007-02-26T20:38:00.000-05:00

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'

2007-02-24T19:58:00.000-05:00

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?

2007-02-15T22:42:00.000-05:00

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

2007-02-15T20:37:00.000-05:00

...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

2007-02-06T20:24:00.000-05:00

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

2007-02-04T21:30:00.000-05:00

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?

2007-02-01T21:29:00.001-05:00

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.

Going Live

2007-01-28T21:58:00.000-05:00

Coming soon: irrefutable evidence that I exist in the physical world! To anyone in the San Diego area, I am giving a talk this Wednesday:

(Update: the talk has been delivered, and the powerpoint is here. Pdf version is here, thanks to the mysterious S...)

Property Testing-- A talk by Andy Drucker

Property testing is a recently developed algorithmic
paradigm inspired by the need for fast (even
constant-time!) approximate solutions to problems with
very large data sets. I will introduce the field,
give representative examples of testing algorithms and
their analysis, and describe lower bounds for the model.

At UCSD, in 4109 EBU3b (CSE building). I will link to my powerpoint when it's complete, should be essentially self-contained.

Despite its bland label, property testing is a fascinating area, and I am looking forward to sharing some of what I've learned about it--so be there!

Addendum: Here is the modest wisdom I have gained from this experience:

i) Don't put too much information on one slide.

ii) Do a practice run--it really helps, and in this case, also made me realize point i).

iii) Don't be afraid to focus on simple results in a talk.

iv) If you are preparing a talk partly to help learn a subject (as I was), you should realistically expect to learn more about public speaking and pedagogy.

PPuzzle

2007-01-18T14:52:00.000-05:00

Today I'd like to present an exercise about PP and related complexity classes, requiring only basic familiarity with reductions in complexity theory. The result involved has almost certainly been discovered before, and I'd appreciate any references.

But first, why do I present so many exercises and puzzles? It's not just to skimp on exposition; it's because, for me anyway, doing puzzles is a joyful activity and the best way to really learn a field. When I pose a puzzle, you have my promise that the solution is both interesting and not too complicated, unless I say otherwise. I will give a sense of the basic background you need, so e.g. I won't ask you to reinvent the probabilistic method (as Kuhn says, puzzles are within and relative to a paradigm, whatever that means).

If theoretical computer science wants to compete with other areas of math in enticing and effectively training young problem-solvers, it needs to have a better sense of what its puzzles are. I hope to say more about this soon.

Here is a computational problem, which I'll call CONTEST:

**********************************************
GIVEN: A boolean circuit C on n input bits, outputting a single bit;

DECIDE: is there a z in {0, 1}^n such that at least half of the outputs {C(y): y <= z in the lexicographic ordering} are 1's?
**********************************************

In other words (and supposing for illustration n = 4), if the outputs {C(0000), C(0001), C(0010), ... C(1111)} give votes for candidates 0 and 1, in the order in which they were received, was candidate 1 ever ahead or tied in the running tally? (i.e., does candidate 1 make a 'contest' of it?)

Problem 1: Show that CONTEST is hard for PP, whose standard complete problem is the following:

**********************************************
GIVEN: A boolean circuit C(x) on n input bits, outputting a single bit;

DECIDE: Are at least half of C's outputs 1's?
**********************************************

Problem 2: Show that CONTEST is in the class NP*(PP), whose standard complete problem is the following problem:

**********************************************
GIVEN: A boolean circuit C(x, y) on 2n input bits (|x| = |y| = n), outputting a single bit;

DECIDE: is there an x in {0, 1}^n such that at least half of the outputs {C(x, y): |y| = n } are 1's?
**********************************************

Problem 3: CONTEST is complete for either PP or NP(PP); which one?
The proof is simple and, I think, amusing.

For those who've been bit by the computability bug (as I've been recently, witness some previous posts), there are many related problems:

GIVEN: A polynomial-time machine M outputting 0's and 1's, viewed as a sequence.

DECIDE: a) Do 1's ever outnumber 0's in an initial segment of the sequence?

b) Do 1's outnumber 0's infinitely often?

c) Does the sequence a_n = (number of 1's up to length n ) - (number of 0's up to length n) diverge properly to positive infinity?

These decision problems are listed in increasing order of unsolvability, and their exact complexity can be pretty readily determined using the k-round game characterization of level k of the Arithmetic Hierarchy that I mentioned in the post 'Trees and Infinity II'.

The Spirit of Modern Math: from Compactness to VC Dimension

2007-01-13T20:43:00.000-05:00

Helly's Theorem was, I think, the first geometry result I ever loved. It was my first exposure to 'combinatorial geometry', a body of results with much looser hypotheses and exploring more large-scale scenarios than classical geometry.
(If you can find it, definitely check out the out-of-print problem book 'Combinatorial Geometry in the Plane' by Hadwiger & Debrunner, or ask me for sample problems.)

Here is the theorem: Suppose a finite collection C of convex sets in the plane is such that any 3 of them has a nonempty intersection; then there is a point common to every set in C.

There is a simple proof by induction on the number of sets in C, which directly implies a polynomial-time algorithm for finding the point claimed to exist, given only a list of points {p[i, j, k]}, where p[i, j, k] is common to sets i, j, and k and we range over all such triples. It'd be interesting to know the exact complexity for this search problem--is there an outright formula for the common point?--but I haven't given it much thought, although the problem is definitely amenable to parallel processing.

Many more general results are available. From the general perspective, the 2-dimensional version of Helly's Theorem above states that the 'Helly number' of R^2 is 3. Helly also proved in the same fashion that the Helly number of R^n is n + 1. There is a result for infinite collections of sets, too, which I invite you to think about.

Think of a convex set in terms of its membership function; Helly's Theorem says that if any 3 of a finite set of these functions are simultaneously satisfiable, then they are all simultaneously satisfiable. This might sound familiar: recall the Compactness Theorem of Propositional Logic (see my 'Trees and Infinity' post), regarding simultaneous satisfiability of finite Boolean functions; Helly's Theorem says that something even stronger holds for convex membership functions, even though they have an infinite domain.

So we find that, even though the finite-domain condition seemed to play an essential role in our proof of the Compactness Theorem, there is a powerful thread of truth running beyond that theorem's scope. It was an important step to formalize abstract properties like compactness and Helly numbers on the basis of more concrete theorems, and then to seek out zones of applicability beyond the ones theorists were originally interested in. This spirit of generalization is part of the greatness of modern mathematics, although it can certainly be taken to extremes.

Note that the Helly property of families of collections of functions(simultaneous satisfiability of any size-k set of functions from a collection implies simultaneous satisfiability of the whole collection), and the weaker compactness property (simultaneous satisfiability of any finite set of functions from a collection implies simultaneous satisfiability of the whole collection) are more useful than natural. They're a mouthful to formulate, and they don't necessarily correspond to what we think 'ought to happen' most of the time, but whenever we're interested in satisfying a bunch of conditions at once in a construction (which is frequent throughout math), Helly and compactness properties can prove invaluable. Furthermore, they apply surprisingly often (especially compactness). This well justifies the study, in real analysis and topology courses, of compact metric and topological spaces, even though the definitions bewilder many students.

In future posts I hope to say more another great (and more recent) concept that also arose out of generalization and is also more useful than natural: the VC dimension. Interestingly, VC dimension (don't worry about the definition for now) can be seen as a probabilistic analogue of the Helly property. Let me explain.

Suppose you've got a finite collection C of sets, and each set S[i] is big enough (relative to some probability distribution) that a randomly drawn element lies in S[i] with probability p > 0. Then if we draw a large number of elements, each individual S[i] is hit at least once with a very high probability 1 - e; then, using the union bound, every set gets hit at least once with probability at least 1 - |C|*e, and if we get the numbers right this will still be 'large enough' (m = O(log(|C|)/p) will do).

The idea sketched above is the core of the conventional probabilistic method in combinatorics. In applying the union bound, it seems to rely crucially on |C| being finite. However, this is not the case. A much more relaxed condition on C--that its VC dimension be finite--will also gain us the same conclusion, albeit with some differences in quantitative strength.

I am grateful to Professor Sanjoy Dasgupta of UCSD for teaching a wonderful course in Learning Theory that much improved my understanding of VC dimension. He showed us a very slick, sophisticated proof of the result about VC dimension I alluded to. However, I am still looking for a truly simple proof, and would happily accept suboptimal quantitative strength in order to be able to share this amazing phenomenon with a wider and more pressed-for-time audience. If anyone has references or ideas on this, please let me know.

For those familiar with the VC concept, I invite you to show that set/function families can have a finite VC dimension without compactness, and compactness (even the Helly property) without finite VC dimension.

Fun with Censorship: the Finite Case

2006-12-27T14:45:00.000-05:00

This post was inspired by Elad Verbin's insights and question about the 'Damn Good Puzzle'. See that post's comments section for the buildup.

Here is a finite version of the censor puzzle (which readers should review for the scenario):

Given k > 0, there is an N (independent of the alphabet and allowed/forbidden word classification system), such that any text of length N has a parsing into k words, with all but possibly the first and last words sharing a classification.

Elad's comments suggested this theorem and implied the bound N <= R(k, k) + 1,
where R(k, k) is the kth Ramsey number. But R(k, k) is super-exponential in k.
In this post I will show how to get a quadratic upper bound.

Following Elad, given a text s_1, ... s_n of length n we define a graph coloring on the complete graph on vertices 0, 1, ... n. Edge (i, j) with j > i is colored red if the word s_{i+1} ... s_j is allowed, otherwise, it's blue. Now, if we can guarantee there exists a monochromatic path of length k in the graph, such that the path is ascending on vertex labels (call this an ascending path), it will naturally induce a parsing into at least k words (possibly k+1 or k+2, depending on whether vertices 0 and n get visited) that meets our condition.

Given an index i <= n and a 2-colored complete graph G on n+1 vertices, let R_i be the number of edges in the longest all-red ascending path in G that ends at vertex i.
Similarly let B_i be the number of edges in the longest all-blue ascending path in G ending at vertex i.

Say i < j. If (i, j) is colored red, then R_j >= R_i + 1, since any ascending red path ending at vertex i can be extended to vertex j via edge (i, j).

Similarly, if (i, j) is blue, then B_j >= B_i + 1.
In either case the (nonnegative) integer vector (R_j, B_j) does not equal (R_i, B_i).
There are only k^2 distinct nonnegative integer vectors having both terms at most k-1;
so if n >= k^2 + 1 some R_j or B_j must be at least k. QED.

What I think is cool about this proof is that the measure of progress is very loose. (R_j, B_j) doesn't strictly dominate (R_i, B_i), it just isn't equal, and the vectors just pile up until some vector--we can't predict which--necessarily exceeds our 'victory' bound.

The result may still be suboptimal for e.g. graph colorings induced by binary alphabets, since these are quite restricted. Who knows, maybe there's a linear upper bound in this case.

If you liked this result, you should definitely check out the book Extremal Combinatorics by Stasys Jukna, which has all sorts of cool related stuff (and complexity theory applications, no less! This is my second plug for the book, so take heed.). So much stuff that I can't even rule out that it contains this result, perhaps as one of its many exercises--but my copy is in San Diego and I'm up in Berkeley on winter break.

It's been a year since I started this blog. I intend to keep it rolling, and have several post ideas queued up, but I'd love to hear from you, dear reader, to get to know you and develop this site in conversation.

Addendum: I now realize that this result can also be derived from Dilworth's theorem (exercise, for those who care). While it doesn't seem to follow from Erdos-Szekeres (a special case of Dilworth), that theorem can be proved analogously to ours, so I probably read such a proof at one point. Nothing new under the sun...

Trees and Infinity, part II

2006-12-23T13:02:00.000-05:00

Previous: Part I

Next: Part III

Time for another short installment on trees and recursive combinatorics, that will address a question raised by the previous puzzle and take us on an journey beyond the arithmetic hierarchy (cue your favorite sci-fi theme music...).

To recap, Konig's Lemma guarantees that a locally-finite infinite tree has an infinite path.

Suppose some machine M(x) computes membership of x in a locally-finite tree T; if x is in T then M(x) outputs the parent and immediate children of x. Then there is no guarantee that T has a computably-describable infinite path; however, such a path can be computed, uniformly in M (assuming we know the root node), given oracle access to the Halting set.

Konig's Lemma fails if the nodes can be infinite-degree, even if the tree is infinite at every height (Exercise). But consider the following computational problem:

INF: Given a Turing machine M describing a tree T (not necessarily locally finite), does T have an infinite path?

This question has a superficial simplicity: it is purely existential. However, the object it seeks is infinite, and unlike in the case where Konig's Lemma applied, there is no obvious finite 'no' certificate. Here's the astounding truth of the matter:

Problem 1: There exists an algorithm which, given any formula F of first-order logic, outputs a polynomial-time Turing machine M describing a tree T such that T has an infinite path if and only if F is true.

Solving the problem boils down to this: suppose we've got a statement of the form Q: "there exists a number x such that P(x) is true", and we know how to convert each individual P(i) to a tree that has an infinite path if and only if P(i) is true; we now need to use this knowledge to build a tree corresponding to Q.

Only slightly harder is the other case that arises: if Q is of form "for all numbers x, P(x) is true", where we again know how to build trees for each individual P(i). Still, this is pretty cool, since you are effectively reducing a universal condition into an existential one. Once you can handle both cases, you can systematically attack an arbitrary first-order expression.

***Interlude: A Review***

If you're not up on first-order logic, just consider F a statement of form

"the game G(X1, X2, ... Xk) is a win for player 1 (assuming perfect play)",

where G is a computable function from N^k --> {0, 1} that defines a game as follows: player 1 and player 2 take turns in choosing values the k values X1, X2, ... Xk, and player 1 wins if and only if G evaluates to 1 under the input chosen.

This 'computable game' formulation turns out to be equivalent to first-order logic; i.e., given any F we can produce a G such that G is a win for player 1 if and only if F is true, and the number of play-rounds of G equals the depth of alternating quantifiers in F; there is also a reduction in the reverse direction.

***

So how hard is the computational problem of checking for infinite paths? If I've got my definitions right, it's complete for the first level of the analytic hierarchy: existential second-order logic.

Now here's a tie-in to the 'censor puzzle' I discussed recently. Given a 'classification' C of finite words over {0, 1} as allowed or forbidden and an infinite 'text' bitstring D, both poly-time computable, let PARSE be the computational problem of determining whether D can be parsed so as to appear wholly allowed with respect to C.

Problem 2: Show that PARSE and INF are Turing-equivalent.

The challenge in reducing INF to PARSE, which is not too hard to overcome, is that because our alphabet is finite, the same words pop up again and again, so our decisions in building up C keep on bugging us, whereas we want continual freedom of movement in encoding new and higher levels of the tree we are attempting to model in a PARSE instance.

In the reduction I came up with, it's always easy to find a wholly-forbidden parsing of the text string. Thus, as an open problem (update: solved! In the negative. See discussion in comments of Part I.) I ask,

Problem 3: Exhibit a PARSE instance, such that any parsing that is either wholly-allowed or wholly-forbidden (with the possible exception of the first word in each case) is not describable in the arithmetic hierarchy.

Conclusion

NP-completeness theory has transformed the way we regard finite optimization problems.
NP-complete problems require hard search, but on a basic level it's 'the same' hard search
in all cases.

Perhaps less widely known is that a similar phenomenon pervades higher
mathematics. Of course, computer scientists know that most natural
undecidable problems are so because they can be used
to solve the halting problem. If they are much harder (as with PARSE),
they are still likely to have a natural classification using the analytic
hierarchy or some other 'mega'-complexity class.

But there is more. If a highly nonconstructive proof seems to require
the axiom of choice, chances are the theorem being proved also
constructively implies some version of the axiom of choice and can be
classified as 'complete' for a certain logical class. This is a theme
explored by 'reverse mathematics', an area I'm only beginning to
learn about.

Revisiting familiar theorems with a view towards establishing their
complexity, informational, or logical content lends them new grandeur
and enriches our sense of the interconnectedness of the mathematical world.

A Damn Good Puzzle (Oops)

2006-12-05T19:26:00.000-05:00

Feel like an exercise in the kind of infinite mathematics I described two posts ago? What follows is a slightly dolled-up version of a puzzle posed by the great mathematician Kolmogorov to an auditorium of Soviet middle-school students, and solved by a young Leonid Levin, future co-discoverer of NP-Completeness. This I learned from the entertaining and important book Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists by Dennis Shasha and Cathy Lazare. (Shasha is also a noted puzzle-poser.)

The Great Censor has, in his inscrutable wisdom, laid down a judgment on every finite string of letters in our alphabet--each is either allowed or forbidden.

We, the petty censors he commands, are to intercept various texts and classify them according to his precepts. However, when spaces are not used in texts, there is a potential ambiguity that makes life difficult.

For example, suppose ab is an allowed word and ba is forbidden (there are all sorts of other judgments as well).

Say the petty censors intercept the infinite string of symbols ababababab... .

One way to 'parse' it would be ab ab ab ..., and we'd judge it wholly allowable.

But another way would be as a ba ba ba ba ... and this would be wholly forbidden except for possibly the first word a.

The Great Censor doesn't mind a little arbitrariness in our choice of parsing--he is one arbitrary dude himself. However, he expects our judgments to be resounding; he doesn't like it if a parsed text alternates back and forth between allowed and forbidden words.

Achieving this has been a matter of great vexation among the censors. However, one day a clever young apprentice censor, still far from internalizing the entire system of judgments, had a realization:

No matter how the set of finite strings is divided between allowed and forbidden by the Great Censor, and no matter what infinite string of letters a petty censor is presented with, it will always be possible to parse the infinite string in such a way that the parsed words are either all allowed or all forbidden--with the possible exception of the first word, which may disagree with the others.

So why is this true?

Drawing on the Hyperanalytical Side of the Brain

2006-11-27T21:12:00.000-05:00

1. Introduction

What's the deal with drawing? Why's it so hard for most people? By 'drawing' I specifically mean an attempt to reproduce on paper some thing or image that's actually in front of you.

Way back when I had a serious interest in drawing; the most important and useful book I ever read on the subject is called Drawing on the Right Side of the Brain, by Betty Edwards. Its basic point is that most of us are hobbled in our attempts to draw by our persistent tendency to overcode visual information with symbolic meaning; doing so causes us to draw our symbols rather than what we are actually seeing. Realizing and addressing this can quickly and profoundly improve people's ability to draw; I've seen it happen to a friend who was hopeless before reading the book.

Of course, an artist's technical development can hardly end there; what's the next step? Making our drawings more accurate, presumably. Is this just a matter of practice, transcribing shape after shape until our basic ability to perceive lengths, angles, and ratios is finely honed? No. I believe that becoming proficient at drawing has more to do with the strategic management of error (analogous to error management in scientific computing) than with the elimination of one's basic susceptibility to error.

I don't think this is a novel or controversial thesis. Furthermore, plenty of books, like Edwards', will teach you various ways to do this better than I could. So why am I writing this? I want to propose an analytical model of the activity of drawing that will give a precise (albeit idealized) account of error and justify techniques of error-management. I hope this model might make the act of drawing seem more interesting and approachable to the sort of people who might stumble on this blog in the first place.

Of course, great drawings involve a connection between artist and subject that goes beyond simple fidelity to its spatial proportions. However, I hope to convince readers that even achieving spatial accuracy is a richly complex activity. The artist is not just a passive photocopier of reality, but must perceive the high-level structure of an image and plan her drawing accordingly.

Warning: I'm a barely-competent artist with no knowledge of the current state of drawing research. You should probably stop reading now.

2. Working Assumptions and Model Criteria

Here are my starting points for the model, which will use a modest amount of mathematics.

1. The target image, i.e. the thing the artist wants to reproduce, is a finite set of points (p[1], ... p[n]) in the x-y plane (the target plane). The drawn image is another set of points (called marks, labeled m[1], ... m[n]) in another x-y plane (the drawing plane, initially empty), each with an intended correspondent in the target plane.

Obviously, this is purely a modelling assumption and reflects no conviction about 'the way things are'. I don't think that the visual field is truly describable as an x-y plane; I'm arbitrarily suppressing questions of 3-D rendering by assuming a flat target; and I'm throwing out lines, shading, color, etc.

2. Drawing is sequential; one point at a time. Moreover, drawing is local. By this I mean that, in determining the location of the next mark, the artist consults only a 'small' number of previously drawn marks, along with their corresponding points. I think this assumption can be falsified, but generally it's too taxing to bring very much information usefully to bear in the production of a single mark.

3. Each mark-making action is error-prone (stochastic, if you like). For simplicity, rather than a probability distribution, I will assume a possibility set of possible positions for a new mark that's a function of the positions of the marks and points taken into consideration by the artist's local rule.

4. Error is scale-invariant. That is, if we shrink or grow the target image, holding proportions fixed, the possibility-sets for new marks will not be affected. This reflects the experience that shifting one's distance from a drawn object does not reliably make for a better drawing (assuming the object wasn't too close or too far away to be clearly perceptible).

Similarly, if we shrink or grow the drawn image-so-far, the possibility-sets for new marks will shrink or grow proportionally. (If error was an absolute quantity, e.g. the drawn point would fall at most an absolute distance e from the correct point, we could all just make very large drawings and the errors would become insignificant flaws on an essentially-perfect rendering. Alas, it doesn't work that way. Now, the implausibility of the absolute-error model doesn't prove the scale-invariant model--there's probably a more nuanced alternative--but I'm going to go with it.)

5. More reference points are useful in determining a new mark. Example: you are given the target image on the left, and have marked A' and B' on the drawing plane (not quite to scale, but that's OK as long as you get C' placed accordingly).
Now you've got to mark C'. My contention is simply that having both A' and B' already placed makes it easier to place C' well; you can check the new mark's relation to two points instead of just one. Of course, it takes at least two reference points just to get a sense of the scale being used in the drawing; but beyond that, there is also additional helpful angular information.

3. The Model

OK, here is a model that I believe honors 1 thru 5 above. 1 and 2 are obeyed verbatim. I don't directly in the model describe how the artist chooses which mark to make next, or which reference points to use in making it (since my main goal is to suggest strategies for making such choices). Therefore, the remaining task is to define how the possibility-sets for new mark location are formed.

First, the artist has two underlying accuracy parameters which we'll call theta and epsilon. Lower values will mean greater accuracy; the first parameter relates to angular accuracy, the second to distance accuracy.

The artist chooses a length-reference pair m[i], m[j], of distinct marks from those already made. The presumptive size-inflation factor of the drawn image relative to the target is then estimated as the ratio of lengths R = L'/L, where L is the distance from p[i] to p[j] and L' is the distance from m[i] to m[j].

This value R is not consciously available to the artist (that's exactly the kind of precision we don't possess); rather, it helps determine the possibility-set for the new mark m[k], as we will describe.

For each additional reference point m[l], a constraint C[l] is placed on the possibility-set (so, more reference points mean less room for error). C[l] has two components. The first one, the length constraint, states that the distance from m[l] to m[k] must be between R*(1 - epsilon)*D and R*(1 + epsilon)*D, where D is the distance from p[l] to p[k].

(Note: I think that this constraint actually becomes tighter when D is approximately L; that is, it's easier to copy a length than it is to scale it up or down. But I won't model this.)

The second component, the angular constraint, states that the vector connecting m[l] to m[k] must form an angle A' with the horizontal that differs by at most theta from the angle A formed with the horizontal by the vector connecting p[l] to p[k].

Thus each such reference point m[l] poses a constraint that looks like the following (C[l] forces m[k] to be placed in the shaded region):
This completes the description of the model. There is only one technicality: what if the constraints cannot all be satisfied? This is a sign that something is wrong with the drawn image, since a fully faithful partially drawn image (at any scale) will always impose constraints satisfied by the 'perfect' marks which complete the drawing, no matter which reference points are chosen. Maybe an inconsistency causes the artist to start over, or pick a mark position satisfying as many constraints as possible.

4. Drawing Strategies Suggested by the Model

In what follows, I'm going to assume that the technicality just mentioned never arises.

1. When possible, choose orthogonal reference points.
Notice that if two such reference points are chosen that lie very close together (both in the target and drawn images), they will impose nearly identical constraints and be functionally redundant, whereas reference points forming a larger angle with the point to be drawn cut down more on wiggle-room, as depicted below.
If the constraint regions were circular, rather than slices of an annulus, this effect wouldn't appear; one constraint region would be contained in all the others, and the corresponding reference point would subsume the usefulness of all the others. This would be a violation of assumption 5, and contrary to my general experience.

2. When possible, choose reference points that are close to the point to be drawn (on the image plane).
For, the shaded area of the constraints we described grows directly as the distance to the reference point increases, giving more wiggle-room for error.

Take a target image like this one of two faces (using lines for ease of illustration):

Suppose you've accurately copied the first face and want to start on the second. It seems clear that using the first face as sole reference point for drawing each of the features on the second face would be foolish; the difficulty in assessing the length of the gap between the faces would give a result like this:

You don't see too many drawings like this one. I think the close-reference-points strategy is intuitively understood by even inexperienced artists. In fact, they cling to it (perhaps also because it involves less eye movement). However, it is problematic as an exclusive strategy, and understanding why is at the core of what I want to impart about managing error in drawing.

3. Maintain a 'confidence' model of the drawn points; when possible use reference points with high confidence.

Suppose you've got the two faces drawn correctly. Say now the target image is altered to include two arms:
(I realize arms don't grow out of people's heads.)
The question is, how should we add in the arms to our drawing? Let's consider two options. First option: draw the leftmost arm, starting from the left face, up to its point of contact with the right arm, then continue the right arm down to the left face.
Second option: draw the left and right arms separately in turn out from their faces, meeting the two in the middle.

In either case we allow any previously drawn marks to serve as reference points. In both cases, except for the discontinuity of switching arms in executing the second option, the dominant (because tightest) constraints are consistently provided by the portions of arm just drawn (these are the closest to the marks about to be made).

As an arm being drawn 'grows' outward from its head, under our model the possible absolute distance of each drawn point from its 'correct' point (relative to the faithfully drawn heads) grows as at least epsilon times the distance to the head from which the arm is growing. This suggests that we should prefer the second drawing option; in fact, since the left arm is longer, we should probably grow part of the left hand out of the right hand--this minimizes the maximum distance from any point-to-be-drawn from its reference 'source' on the two heads.

4. Watch out for error-accumulation in reference lengths; use confidence models here as well.

The importance of using confident reference points is heightened by the fact that error can accumulate in length-reference pairs as well. Inexperienced artists, when drawing a feature in a vicinity of their picture, over-rely on that vicinity to determine scale as well as relative position. So, if features have gotten too enlarged in a picture region (typically an 'interesting' region with lots of detail), they will continue to be drawn overly large thereabouts because the length-reference pairs will be chosen locally.

Note that in the discussion of the arm-drawing, we strategically chose not only reference points, but also which points we were to draw next. So, generalizing:

5. Choose points to be drawn next that have close, orthogonal, and/or confident reference points available.

All these goals may conflict, and need to be weighted in decision-making. I don't think I could say anything quantitive here that would be of much value.

There is one issue we skirted over. In drawing the arms, we assumed we had two distant and accurate reference points (the two heads). What reason do we have to assume this? Well, the first large length we draw can be nominated as the governing scale factor for our drawing, i.e. presumed accurate; but beyond this we necessarily face significant error in drawing points at significant distances.

I think the most honest account of how this is to be overcome is to admit that our accuracy is a parameter that varies with effort.

5. When 1-5 are inapplicable or insufficient, use more effort.

A good drawing begins with a modest number of key reference points being drawn with high effort and high accuracy; these points are chosen to 'cover' pictorial space, so that the remaining points are each reasonably close to one of the key points. The key points each then serve as the seeds of 'arborescences' of new, close points which depend on the accuracy of the initial points from which they grow (the artist may also put down secondary and tertiary layers of less-key reference points, giving a finer cover to work with); these later stages of the drawing require less strict accuracy because they are less relied-upon. In summary:

6. Draw with a plan.

Visualize ahead of time the reference-point dependencies to be used among the points that need drawing. Aim for this dependency graph to be shallow, with individual points backed up either with effort or with good (confident, close, orthogonal) reference points. Since there is an initial paucity of reference points, intelligently applied initial effort plays an important role for the drawing, as described in the previous paragraph.

That's all I've got! Of course, I would love feedback from anyone, experienced artist or otherwise.

Trees and Infinity

2006-11-09T15:52:00.000-05:00

With this post I hope to do a little to strengthen readers' (and my) understanding of the mathematics of the infinite (something easy to neglect in the study of resource-bounded computation), while focusing on the discrete infinite structures that arise in computability theory.

In mathematics, a tree is an important kind of structure. It consists of a set of nodes, with one designated the root. Each node has a (possibly empty) set of 'children' (of which it is the parent), and any node is reachable from the root in a unique way by a finite series of steps, where each step takes you from a node to one of its children.

The genealogies of asexual organisms, for example, are naturally describable using trees. An important tree in discrete math is that formed with the finite bitstrings as nodes, where the root is the empty string and where the children of x are x0 and x1. (Exercise: use this tree to exhibit the following, somewhat startling, phenomenon: there exists an uncountable collection of subsets of N, the natural numbers, such that any two subsets have at most a finite intersection.)

This tree on bitstrings is an infinite tree, but it has the nice property of being 'locally finite': every node has only finitely many children. Konig's Lemma (the 'o' in Konig needs an umlaut) asserts that any infinite, locally finite tree contains an infinite path (hopping parent-to-child at each step).

The proof is simple: we build such a path. Start at the root; by the pigeonhole principle, one of the root's children c must itself be the root of an infinite subtree. Hop to c, repeat the same process, ad infinitum.
QED.

This innocuous Lemma is in fact very powerful. I will describe some basic applications.

1) The Compactness Theorem for Propositional Logic: Suppose {F_i} is an infinite family of Boolean functions over x_1, x_2, ..., such that i) each F_i depends on finitely many variables, ii) for each K we can find a setting of the variables that satisfies F_1, F_2, ... F_k (i.e. makes them all equal 1).
Then we can find an assignment satisfying all the F_i simultaneously.

Proof: For any finite bitstring y, say of length j, interpret y as an assignment to x_1, ... x_j. Say y is in T if there is no particular F_i that y has already forced to output 0.

T is clearly a tree, and locally finite. If it has an infinite path, that path describes an assignment satisfying all of {F_i}. So assume it does not. But then, by the contrapositive form of Konig's Lemma, T must be finite, say with no node representing a bitstring of length K or more.

This means that for any length-K bitstring y, there is some formula F_{i[y]} forced to be 0 by setting x_1 ... x_K = y.

How, then, can one find any assignment to x_1, x_2, ... that satisfies all of the finite set of formulas {F_{i[y]}: |y| = K } ? One cannot. This contradicts the assumptions of the Theorem, completing the proof.
QED.

Here's a nice application of the Compactness Theorem:

2) show that the 4-color Theorem of graph theory holds even for infinite planar graphs, as long as each graph node is of finite degree. (Assume the finite 4-color Theorem is valid. Or, hey, don't...)

Konig's Lemma or The Compactness Theorem can each yield a simple proof (exercise!) of the following 'query complexity'-type result:

3) Suppose f is a Boolean function on x = x_1, x_2, ... Say whenever f(x) = b, for b = 0 or 1, there is a finite subset of the variables which force f to equal b.
Then f in fact only depends on finitely many variables.

This result is redolent of the statement 'REC = RE intersect coRE' in computability. It also has an analogue in a more finite setting--a kind of moral equivalent of 'P = NP intersect coNP' in query complexity--which I invite readers to discover or ask about.

It's interesting to wonder to what extent Konig's Lemma can be 'constructivized'. Let D be an infinite subtree of the prefix-tree over finite strings (as described above). Suppose membership in D is computable. Say infinite string s refines D if all of its finite prefixes are in D.

4) Is it necessarily the case that for such D there is a computable s refining D? (Hint: Diagonalize.)

4.5) If the sequence of functions from the Compactness Theorem (1) is a computable one, is there a computable assignment to x_1, x_2, ... satisfying every function?

5) What if, in 4, there is an additional guarantee that only countably many s refine D?

For readers interested in Kolmogorov complexity, the following somewhat challenging result rewards similar tree thinking:

6) Suppose that for some infinite string s there is a constant C such that for all n, there is a Turing machine M_n which, on input n, outputs the length-n prefix of s.
Then s is computable. (The converse is easy.)
(Source for 6: the gorgeous Li-Vitanyi book on Kolmogorov complexity.)

Addendum: I just found a good source for further material related to 4-5 and other aspects of 'recursive (infinite) combinatorics': Bill Gasarch's chapter in the hefty Handbook of Recursive Mathematics, Vol. II.

Shifting quite a bit now, I'd like to briefly describe a nice probabilistic result about infinite genealogical trees. Consider an idealized asexual organism in an idealized environment. Each individual alive at time t (an integer) gives birth to some number (possibly zero) of offspring, whose number is determined by the outcome of a random variable X. Then the individual dies as we enter time t+1. Each new individual's reproduction is governed by the outcome of an independent copy of X (so, just because your parent had reproductive success doesn't make you more likely to).

X could be very complicated. But it turns out that the expectation E(X) is still quite powerful in understanding the population dynamics: if E(X) is less than 1 then an eventual extinction occurs with probability 1, while if E(X) is greater than 1 then extinction happens with probability less then 1, and conditioning on the event that extinction does not occur, then with probability 1 the population size goes to infinity rather than oscillating indefinitely.
The proofs I've seen of these results are generatingfunctionological. Are there more 'natural' proofs out there? Or a relation to Konig's Lemma?

I should note that real trees are worth thinking about too. I would recommend the site Carbonfund.org as what seems to be the most well-run and cost-effective place to buy carbon credits, reducing global warming and deforestation. $55 will offset 10 tons of CO2, a significant chunk of the direct yearly impact of an average American.
P.S. Anyone who uses PayPal for this kind of thing should be aware of the fraudulent emails sent by PayPal impersonators to solicit credit card numbers.

Finally, for a more soulful/whimsical take on trees and the infinite you might check out Calvino's novel The Baron in the Trees. (Thanks, Chaya!)

Theory and Me

2006-11-04T15:57:00.000-05:00

Recently Columbia U. Press published a large anthology of literary criticism and metacriticism with the provocative title Theory's Empire. It aims to describe, from a fairly critical standpoint, the trajectories of various influential 'isms' in the recent study of literature: postcolonialism, postmodernism, deconstructionism, etc. I haven't read it yet, but judging from the blog-buzz it could be an important retrospective. I hope that some scientists too are persuaded to look it over and learn something (by way of comparison) about the vicissitudes of theory in humanities departments.

What is it that makes 'theory' so enticing? I think it can simultaneously convey feelings of surprise, hidden connections, and newfound mastery that together bring the theorist or reader into a charmed state. Thinking becomes an urgent activity, and big thoughts make contact with the world, resonating in the air like gongs.

Anyway, this was my experience as a junior and senior in high school when I discovered and got feverishly involved in the 'postmodern' theorists--Foucault, Deleuze, Baudrillard, etc. At a point when I was still fairly uninterested in math/science, tired of school, and resentful of the authority of both, these authors offered an exhilerating counternarrative and an alternative standard of intellectual rigor. Although they generally disavowed systematic thinking, their writing was characterized by a small number of patterns (often taking the form of a surprise inversion) that operated repeatedly in diverse settings to yield radical consequences--a set of 'magic keys' to experience.

That experience gradually turned sour. I realized that in my eagerness to apply these new theoretical ideas anywhere and everywhere I was becoming insensitive to the world; my thinking was driven by the need for radical contrarianism rather than the desire to truly understand. Then, too, I took my first computer science course, which opened up a whole new chapter in my adventures in theory (a tale for another time). Today I am very far removed from the person I was in that period. My relationship to theory has cooled down considerably even as it's grown happier and more productive; this is, I'm sure, due both to the nature of mathematics as a field and to my changing temperment as I leave adolescence behind (of course, the factors are related).

But mathematical and scientific theories are not necessarily so different from others. They too can form empires in our minds and govern our search for meaning, and it is up to scientists to choose their masters wisely. Just as philosophical systems like postmodernism run the risk of becoming vacuous in their generality and predetermined in their findings, I think there are significant risks in becoming absorbed in scientific trends, like 'nonlinear science', that combine emotional resonance, polemicism, and seemingly unbounded applicability.

Not to say that good science doesn't appear under that rubric. None of this should be taken as criticism of particular theories, in particular of the pomo theorists mentioned, whom I've seldom read since high school (oh yeah, and their appeal wore off even faster once I got to Swarthmore and they became commonplace..). I'm just describing an individual relationship to theory, in the hopes that it might help others reflect on theirs.

Some people have 'break-up songs', that help them both to look back and to move forward; for me and postmodernism I'd say it was Pynchon's novel 'The Crying of Lot 49', which captured in transmuted fashion a lot about my own search for meaning in high school: the growing uncanniness, the thrill of transgression and revelation; the need (without clear motive) to uncover patterns of power, domination, and covert resistance; the eventual nausea and disillusionment, along with an unshakeable sense that a mystery has slipped thru one's fingers.

And on that note--new Pynchon out this month. Fingers crossed!

WLOG

2006-10-29T12:10:00.000-05:00

WLOG is mathematics-speak for 'without loss of generality', which means 'restricting ourselves to considering a special case, which is not really a restriction'. For example, is there a drive from Berkeley to Las Vegas that's less than 500 miles? WLOG we can look for one that doesn't involve visiting any one spot twice.

The above example illustrates two features of WLOG claims:

i) They are frequently commonsensical observations;

ii) They can eliminate a great deal of dross very easily, making efficient algorithms possible.

Using dynamic programming to solve construction problems is a prime example. Here we have construction tasks where the 'worth' of a partial solution can be completely summarized with a few well-chosen parameters; if two competing partial solutions have the same parameters, we can WLOG throw one of them away.

So, in our example, our idealized travel problem has length and stopping point as the sole relevant parameters for partial trips: if we think the shortest trip to Vegas might take us through Reno, and we've found two equally short shortest-paths to Reno, WLOG we can flip a coin and store only the winning path as we try to extend it from Reno to Vegas. Of course, we also need to consider paths that don't pass thru Reno (which, as it turns out, is way too far north).

Note that, while the no-looping-paths restriction has a distinct preference when it makes restrictions, this second dynamic-programming restriction has a symmetric character--indifferent to which candidate it keeps--and is motivated purely by a desire to reduce the size of our search space and save computation time. Both types of restriction are common.

As a challenge, try to apply domain-specific WLOG-reasoning to give a solution (not necessarily efficient) to the following geometry problem:

Circle Packing: Given a set of circles of rational radii r_1, r_2, ... r_n > 0, and the dimensions of a rectangle R, can the circles be packed into R without overlap or dissection?

Probably an old problem, and close to NP-complete problems if not NP-complete itself (?), but I cribbed it from this book which, although insubstantial, I recommend skimming for puzzles.

Mathematics of the Worst-Case Scenario

2006-10-28T14:28:00.000-04:00

Optimization is an obvious and major theme of applied mathematics. What may be less obvious to the public is the extent to which mathematics relies on a dual process, which one might call 'pessimization'.

Suppose we want to partially relate two functions, f and g, with a statement of the form

"f(x) >= M implies g(x) >= N". So, f and g are positively correlated, and we want to quantify this relationship.

How do we get the strongest possible relationship? Fixing M, we choose x to minimize g(x) subject to the constraint f(x) >= M. This value of g(x) is the tightest lower-bound N we can get, and the most informative statement.

Why is this 'pessimization'? We look for statements of the above form when we are interested in ensuring that g(x) is high (g is some measure of 'goodness', and f is some simpler measure that we can more easily estimate and which is heuristically related to g); but, to achieve this we have to spend much of the time thinking perversely about how low g could wriggle subject to the constraint that f is high.

This kind of thinking is ubiquitous. The subject is too general (really only a 'theme') to have truly distinctive methods or theoretical constructs (in particular, there is no fundamental difference between optimization and pessimization--the latter is just optimization from the devil's perspective), but where it treats discrete, finite objects and collections it is sometimes called 'extremal combinatorics'; I recommend Jukna's book by that name.

Sometimes the heuristic relationship between our two functions has a clear logical grounding. For instance, let f(G) measure the number of edges in a graph, and let h(G) measure the number of triangles; adding an edge to a graph can never decrease the number of triangles. However, f(G) > f(G') does not imply that h(G) >= h(G'); G' may be more 'pessimally' organized than G with respect to triangles. Turan's Theorem, giving exact conditions on f to guarantee that h > 0, is considered the founding result of extremal combinatorics. Can you prove such a theorem? What do triangle-pessimal graphs on m vertices look like?

The preceding example is really a special case. Having a triangle and having at least a certain number of edges are both 'monotone properties' in the sense that they are monotone functions of the 0/1 adjacency matrix of a graph. A simple result of Kleitman, provable by induction, says that if A and B are two such properties and we uniformly generate a graph on n labeled vertices, Prob[A & B hold] >= Prob[A holds]*Prob[B holds].

So, e.g., being informed that our graph has diameter at least 10 cannot make it less likely to be planar, as should be intuitive ("diam >= 10" and planarity are antimonotone properties, so we apply the result to their negations and then rephrase).

A pleasant feature of investigations in extremal combinatorics is that they can be jump-started with simple questions; the exotic structure emerges naturally in exploring pessimal objects. Or, sometimes, the pessimal structures end up being very simple and familiar, but meeting them in the context of the investigation sheds new light on them. For example, we may heuristically observe that collections of 'many' distinct numbers contain 'many' distinct pairwise differences; even though the pessimal structure that pops out when we pursue this relationship is nothing more than n points in arithmetic progression, it's still a nice problem (which becomes more interesting when raised to 2 or more dimensions).

Some quite simple results of extremal combinatorics have important uses in elementary probability and in complexity theory. For example, take a square 0/1 matrix with 'many' ones; we'd like to conclude that it has many rows with many ones each; if we're willing to settle for either many 1-heavy rows or many 1-heavy columns, we can do much better (since pessimal examples against the 'many-rows' conclusion promote the 'many-columns' conclusion) when we quantify our various 'manys'. If we'd also settle for even a single 1-heavy row or column, we can do still better.

Such results have some immediate interpretations in terms of conditional probabilities. They also fuel a kind of robust reduction from any function f(x) on n bits to the function g(x, y) = (f(x), f(y)) (with the two matrix dimensions in our analysis corresponding to the two inputs to g). This is at the heart of a certain approach to hardness amplification, including a proof of Yao's XOR Lemma, given in this paper (see also my earlier post on the XOR Lemma). In fact, Jukna's book is rife with complexity apps, and was written with computer scientists in mind.

As I've said, no 'deep' unifying theory of extremal combinatorics exists, and I feel more inclined to share problems than to exposit. But this time, instead of belaboring my idiosyncratic preferences, let me point you to a great site with more problems than you'll ever solve: Kalva, a clearing-house of old Olympiads with many solutions. Many sterling combinatorics puzzles lie amidst the usual geometry and number theory. Olympiads are hard, but with this many problems to peruse you WILL find ones you can solve--and that feels good.

In Praise of Automata

2006-10-08T20:18:00.000-04:00

I have a confession to make: I am inordinately fond of automata theory.

Yes automata, those unfashionable creations: once-proud denizens of Complexity Castle, they have been reduced to gatekeepers--frozen, homely gargoyles to frighten off undergraduates who have strayed into Theory Woods.

Well, they may not be the 'right' model of feasibility or tomorrow's hot topic; they may be innocent of the Unique Games Conjecture, and they may not know how to count past a constant. But to all who have written them off, or--worse--taken to pumping them for sport, I say automata are computational processes too, and as such worthy of respect--even love.

So join me now in a scenic stroll through some of the historic sites of automata theory. My aim is not to introduce the subject (for that see Wiki and its refs), or even to give vital theorems or unifying ideas you might have missed, but simply to point out the opportunities for intuitive problem-solving that automata provide. You can think about these things through the lens of logic, languages, games, pure visualization, or what have you, but in my experience they reward even casual thought.

All results mentioned are offered as puzzles, since that's generally the spirit in which I approach the subject, although difficulty varies hugely and some I've never solved. Oh, and I won't be giving many citations, but unless noted these results are older than I am.

Swingin' Both Ways

What is the least we can do to augment a finite automaton, while preserving its distinctive flavor? We could let it go back and forth on the tape. For decision problems, however, this gives us nothing. (As we'll see, the robustness of the basic model is remarkable; however, unlike Turing machines, the invariance only goes so far, so tooling around is actually worthwhile. Less robustness = more research opps.)

There is a much more subtle result, due to Hopcroft and Ullman, that shows how thoroughly automata dynamics can be comprehended. Take two FSAs, M and M', one of which scans left to right, the other right to left. Then there is a third FSA P using 2-way motion, with a subset of its states called 'display states', such that on any input x, when P enters a display state for the jth time, it is on square j and its state tells us the states of both M and M' upon arriving there (from their opposite directions). Chew on that!

Alright.. guessing/nondeterminism? As you probably know, this gains us no new languages, though it can yield exponential savings in automaton size. (This is the only truly quantitative result I'll mention... automata-land is a place to forget your troubles with big-O and theta, a place where all you need to know is that infinity is larger than N for any N.)

How about giving the finite automaton a brief chance to imitate its big brother the Turing machine? We'll give it a constant k > 0 modifications of the input string. Will anything come of it?

Try throwing in all of these augmentations in at once, along with unlimited alternating nondeterminism: one by one, the bells and whistles can be stripped away.

Pebble Pushers

What happens if you give a finite automaton a pebble? It's not quite on par with the mouse/cookie scenario, but outrageous hijinks are to be expected nonetheless.

Let's qualify that. The first pebble is a bit of a letdown; they can still only decide the regular languages. With the second things get interesting (how interesting?), and with with an arbitrary number of pebbles you can do logspace computation.

How about function computation with a single pebble? This was a big concern of mine much of a summer internship. First, what is our model? Say that the automaton can announce an output symbol anytime it wants, but the symbol gets added to the end of an output string that the automaton cannot reconsult. This kind of automaton is called a 'transducer'.

A 2-way transducer can compute functions that a 1-way one cannot; for example, the reversal of the input. Additionally, it's obvious that adding a pebble helps us: with our state space enlarged, we can get quadratic run-time, hence, quadratic output. But isn't this a little bit cheap? That's what I thought, and with the aid of the Hopcroft-Ullman result I eventually showed that, if the automaton is required to have linearly bounded output, 1 pebble does not help.

Logic Chopping

I later found out that the result had been known for a few years; or rather, it followed easily from some more general result. What did those crafty theorists have that I was missing? I forget the specifics, but most likely they made a perspicuous transformation of the problem. I'd like to illustrate one such paradigm for transforming automata.

Let x be a bitvector, and let PAR(x) = 1 iff |x| is odd. Then PAR(x) = 1 if and only if there exists a 2-coloring of the symbols of x such that

a) the first symbol is red if equal to 1, and blue otherwise;
b) for i > 1, x_i has the same coloration as x_{i-1} iff x_i = 0;
c) the final symbol is red.

Looking at this from a formal perspective, we can write it using position comparisons, bit-readings, and logical connectives, along with existential and universal quantification, where quantifiers are over either positions or subsets of the positions. This is 'monadic second-order logic (MSO)' over strings (a set is a monadic relation). Clearly the same approach can be applied with PAR replaced with any regular language, with colors for each state and constraints embodying the state-update rule.

In fact, the converse is also true! Namely, given an MSO formula, the set L of strings satisfying it is regular. This isn't hard to show if you start by giving an automaton using alternation to mirror the quantifiers, along with other bells and whistles for the set-guessing, and then patiently eliminate each augmentation in turn.

Combining this result with the first half of our discussion, we find that every MSO formula is equivalent to one with only constant-depth quantifier alternation--cool. Could also probably use the FSA equivalence to study how quantifier use can allow MSO formulae to be more concise.

Ad Infinitum

I recently learned about some very elegant models that give new life to FSA. Take pumping to the limit--give them infinite strings! And let automata perform infinite computations.

To define languages of infinite strings, we need a notion of acceptance. There are at least three major models available:

-Buchi: automaton accepts if it enters one of its 'happy' states infinitely often.

-Muller: an automaton with state-space Q accepts if the set S of infinitely recurring states is among a family S_1, ... S_k of 'good' subsets of Q (states themselves are not good or bad).

-Rabin: there's a collection {P_i, N_i} of pairs of states, and automaton accepts if for some i, P_i is visited i.o. while N_i is visited only finitely often.

Then if I've got it right, the following statements hold:

-Nondeterministic Buchi = conondeterministic Buchi = deterministic Muller = deterministic Rabin;
-deterministic Buchi is weaker than nondeterministic;
-If L is a nondeterministic Buchi language, there exist regular languages V, W, such that an infinite string x is in L iff x = v w_1 w_2 w_3 ..., (where v is in V, and each w_i is in W). The converse holds too.

Also, Buchi automata capture MSO with the successor relation over infinite strings. All of these facts are worth thinking about; some are not hard.

Apparently these infinite models are relevant to practical nonterminating computer systems--bank tellers, operating systems, and so on. Whatever.

The Joy of Dimensionality

Remember when you could have thoughts like, "woah... what about a 2-dimensional Turing Machine?" Well, replace TMs with FSAs and this becomes interesting.

-Can a two-dimensionally wandering FSA look at a map of a maze and determine if escape is possible?

-What if it's not a map, but the FSA is in the maze?

I worked on this unsuccessfully for a while. Apparently the first impossibility proof was 175 pages! But the basic idea is to watch an FSA's behavior and design 'traps' for it. I should mention that the traps are much, much easier to design on a torus or in 3-space.

-What is the least 'leg up' we can give to make maze exploration possible? Forget laying down string: Blum and Kozen showed that having just 2 pebbles does the trick. I believe the 1-pebble case is still open.

Conclusion

A single tear cracked the surface and rolled down the gargoyle's face as it remembered what it had once been, and could still become..

Feel free to chime in with your own favorite results. And seriously, automata theory seems to be in very healthy shape, despite its relative neglect in the Complexity world, where it still pops up, as in the following result (Barrington's?):

-There exists a regular language L and a nondeterministic polynomial time machine N(x, y) (|x| = |y|) such that it is PSPACE complete, given x, to determine if the string
(N(x, 00...00), N(x, 00...01), ... N(x, 11...11)) is in L.

Cheers!

Squaresville

2006-10-01T23:38:00.000-04:00

Given a function from some domain to itself, we can form its 'square' f^2(x) = f(f(x)); third, fourth powers likewise.

How about the inverse problem, 'fractional powers'? What conditions on f allow us to express our function as f(x) = g(g(x)) for some g?

Puzzle: in the case where the domain is a set of nodes and f is presented as a directed graph with outdegree 1 (each u points to f(u)), try and classify the problem of recognizing squares as in P or NP-complete.

(for a quick intro to P and NP, see the wiki page).

And what if the domain is the real or complex numbers? Here we're courting higher math, but Taylor expansions offer some guidance. There's a thought-provoking if hand-wavy discussion of the real case here; for more authoritative references (which I haven't read) this page looks promising.

Complex numbers have nice properties; do fractional iterates exist more frequently in this case? I haven't thought much about this, but am reminded of a nifty result from a college course: If f(z) is an analytic function, then either f(z) has a fixed point OR h(z) = f(f(z)) has one. The proof is short and sweet once you assume the deep result of Picard, that any such f has image equal to the whole complex plane minus at most one point.

Hello, World

2006-09-25T18:31:00.000-04:00

Uploading this from my new phone cost 25 cents; you can decide whether it was worth it.

As of last week, I'm settled in La Jolla and proving day by day that it's possible to survive without a car in this land of midnight traffic and six-lane 'Scenic Drives'.

Invitation to Inanity

2006-09-21T13:47:00.000-04:00

Tired of work, but too lazy to get up? Try this little game:

Take a thin pen with a cap. Uncap it and place pen and cap in the palm of your hand. Now, shut your eyes and recap the pen, without the aid of your other hand or any other object or surface, and without marking yourself.

With my pen (a Pilot Precise V5, cheap and common), hand size, and dexterity level, this has proved surprisingly fun and challenging.

Play at your own risk, obviously. As a lefty, my hand is usually ink-smudged just from writing, so it's no big deal, but watch out for the clothes.