Wednesday, September 28, 2011
Wednesday, June 15, 2011
Joint computational complexity, and the "buy-one-get-one-free conjecture"
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.
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.
Monday, May 09, 2011
An exciting new textbook, and a request
Friday, December 10, 2010
Thursday, November 04, 2010
ECCC: what authors should know
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.
Wednesday, July 21, 2010
"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.
Labels: general math
Monday, August 10, 2009
Wit and Wisdom from Kolmogorov
-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...]
"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."
Labels: general math