WebDiarios de Motocicleta

The Conceptual Wars

2009-06-26T21:26:00.002-04:00

Scott Aaronson, in his regular post-FOCS-notification column, has indicated me as a leader of the Technicians Resistance Army of TCS (a leader, at least, in irășcibility).

As Anup points out, our guerrilla force shall strive to remain concealed in the shadows of the dark STOC/FOCS committee rooms. But, as an exposed member, I must accept my destiny as a preacher of our movement during the coming conceptual wars.

My basic plan is to sing the ideas of theoretical computer science from the rooftops¹. I want to convince you that we have a destiny grander than communicating with quantum aliens. I want to remind you of the beauty of the algorithm. I want to tell you mystical prophecies about the depth our field will achieve when it will show, e.g., that max flow needs superlinear time. And, yes, I want to reprehend you for behaving like a bitter fringe mathematician instead of accepting the place of TCS as the New Maths... Or for having such low self-esteem that you will gladly wipe the floors of the Economics department for some attention. And, against all odds, I want to convince you that solving hard problems is more rewarding than inventing easy new ones.

***

Just, please, hold off the war for a few weeks. For now, I am the chair of the Scientific Committee of the CEOI (Central European Olympiad in Informatics). These kids have prepared for years to get here, and we owe them some exciting problems (which will certainly find their way to the blog later).

–––––

¹This cool quotation comes, I believe, from Scott's job application. I learned of it in a bar from a friend who was on the job market at the same time as Scott. My friend added "I don't have this [...] in me."

Conceptual Contributions Conference

2009-06-04T18:02:00.002-04:00

At STOC, there was an announcement of a new conference dedicated to conceptual contributions, titled ICS (Innovations in Computer Science). Michael asks for more discussion on this conference.

Personally, I am enthusiastic about ICS. It seems like one of the best ideas in decades for improving the quality of STOC/FOCS.

Conference in Romania

2009-05-12T17:38:00.002-04:00

I am on the program committee for Advances in the Theory of Computing (AITC'09), to take place in Timișoara, Romania on September 26-29. The conference is a new, experimental theory track for a larger and more established conference (The 11^th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC'09).

The deadline for regular papers is May 30. You know you always wanted to visit Romania, so use the next couple of weeks to wrap up a result and send it in!

Alternatively, the conference will double up as a workshop (papers in the "presentation track" will not be published in proceedings, allowing you to submit elsewhere). The deadline for such presentations is July 1st.

So come to discuss the most exciting developments in theory, while enjoying your 1-liter beers with a view of one of the most beautiful Romanian cities.

Letter Grades

2009-05-08T03:42:00.004-04:00

In the US, final course grades are expressed in letters (the schemes I've seen are A/B/C, and A/A-/B+/B/B-). This leaves one with the interesting task of drawing barriers in between students (a task best performed at 2am the night before moving out of your apartment).

I am not comfortable with adding different components of the grade (like the midterm and final), as the average and standard deviation are vastly different. Is there a good statistical approach to this problem, with some convincing theory behind it? (Being at IBM Almaden, I should automatically go for rank aggregation, I guess... But there seems to be a lot of noise in the rank, since there are clusters of people with similar scores on each exam.)

Fortunately, if you only give one midterm (and assign low weight to the homework), you can plot the results in 2D. Unfortunately, you may end up with something like this:

Oh well... Everybody knows grades are somewhat random.

Complexity Everywhere

2009-05-03T15:21:00.003-04:00

I know that whenever I write about TCS politics on this blog, it ends up bad. For instance, I get a comment such as the following one (left by an anonymous to my last post):

What makes it tough for some of the papers you cite is the view that shaving off log factors is often viewed as much less interesting than larger improvements.

This, of course, makes my latin blood run even hotter, and I cannot help writing follow-up posts (this is the first). If only I could keep my promise of not writing about politics, my life would be so much simpler. (If only I could learn from history... I got to observe my father become a leading figure in Romanian Dermatology a decade before he could get a faculty position — mainly due to his latin blood. He got a faculty position well into his 50s, essentially going straight to department chair after the previous chair retired.)

So, let's talk about shaving off log factors (a long overdue topic on this blog). As one of my friends once said:

All this talk about shaving off log factors from complexity people, who aren't even capable of shaving on a log factor into those circuit lower bounds...

There is something very deep in this quote. Complexity theorists have gone way too long without making progress on proving hardness, their raison d'être. During this time, drawing targets around the few accidental arrows that hit walls became the accepted methodology. For instance, this led to an obsession about the polynomial / non-polynomial difference, where at least we had an accepted conjecture and some techniques for proving something.

Complexity theory is not about polynomial versus non-polynomial running times. Complexity theory is about looking at computational problems and classifying then "structurally" by their hardness. There are beautiful structures in data structures:

dictionaries take constant time, randomized. (But if we could prove that deterministically, dynamic dictionaries need superconstant time per operation, it would be a very powerful message about the power of randomness — one that computer scientists could understand better than "any randomized algorithm in time n^c can be simulated deterministically in time n^10c if E requires exponential size circuits.")
predecessor search requires log-log time. The lower bound uses direct sum arguments for round elimination in communication complexity, a very "complexity topic." A large class of problems are equivalent to predecessor search, by reductions.
the hardness of many problems is related to the structure of a binary hierarchy. These have bound of Θ(lg n) or Θ(lg n / lglg n) depending on interesting information-theoretic issues (roughly, can you sketch a subproblem with low entropy?). There are many nonobvious reductions between such problems.
we have a less sharp understanding of problems above the logarithmic barrier, but knowledge is slowly developing. For instance, I have a conjecture about 3-player number-on-forehead games that would imply n^Ω(1) for a large class of problems (reductions, again!). [This was in my Dagstuhl 2008 talk; I guess I should write it down at some point.]
the last class of problems are the "really hard" ones: high-dimensional problems for which there is a sharp transition between "exponential space and really fast query time" and "linear space and really slow query time." Whether or not there are reductions among these is a question that has preoccupied people for quite a while (you need some gap amplification, a la PCP). Right now, we can only prove optimal bounds for decision trees (via communication complexity), and some weak connections to NP (if SAT requires strongly exponential time, partial match requires weakly exponential space).

Ok, perhaps you simply do not care about data structures. That would be short-sighted (faster data structures imply faster algorithms; so you cannot hope for lower bounds for algorithms before proving lower bounds for data structures) — but it is a mistake that I can tolerate.

Let's look at algorithms:

Some problems take linear time (often in very non-obvious ways).
Sorting seems to take super-linear time, and some problems seem to be as fast as sorting. My favorite example: undirected shortest paths takes linear time, but for directed graphs it seems you need sorting. Why?
FFT seems to require Θ(n lg n) time. I cannot over-emphasize how powerful an interdisciplinary message it would be, if we could prove this. There are related problems: if you can beat the permutation bound in external memory, you can solve FFT in o(n lg n). The permutation bound in external memory is, to me, the most promissing attack to circuit lower bounds.
some problems circle around the Θ(n sqrt(n)) bound, for reasons unclear. Examples: flow, shortest paths with negative lengths, min convolution with a mask. But we do have some reductions (bipartite matching is as hard as flow, bidirectionally).
some problems circle around the n² bound. Here we do have the beginning of a classification: 3SUM-hard problems. But there are many more things that we cannot classify: edit distance and many other dynamic programs, min convolution (signal processing people thought hard about it), etc.
some problems have an n*sort(n) upper bound, and are shown to be X+Y-hard. Though the time distinction between n² and n*sort(n) is tiny, the X+Y question is as tantalizing as they get.
some problems can be solved in n^ω by fast matrix multiplication, while others seem to be stuck at n³ (all pairs shortest paths, given-weight triangle). But interestingly, this class is related to the n² problems: if 3SUM needs quadratic time, given-weight triangle requires cubic time; and if min-convolution requires quadratic time, APSP requires cubic time.
what can we say about all those dynamic programs that run in time n⁵ or something like that? To this party, TCS comes empty-handed.
how about problems in super-polynomial sub-exponential running time? Ignoring this regime is why the misguided "polynomial / non-polynomial" distinction is often confused with the very meaningful "exponential hardness." There is much recent work here in fixed-parameter tractability. One can show, for instance, that k-clique requires n^Ω(k) time, or that some problems require 2^{Ω(tree-width)} time.

And what can we say about k-SUM and all the k-SUM-hard problems (computational geometry in k dimensions)? This is an important illustration of the "curse of dimensionality" in geometry. I can show that if 3SAT takes exponential time, k-SUM takes n^Ω(k) time.

Finally, what can we say about PTAS running times? In my paper with Piotr and Alex, we showed that some geometric problems requires n^{Ω~(1/ε^2)}running time. This has a powerful structural message: the best thing to do is to exhaustive search after a Johnson-Lindenstrauss projection.
inside exponential running time, there is the little-known work of [Impagliazzo-Paturi] showing, for instance, that sparse-3SAT is as hard as general 3SAT. Much more can be done here.

Lest we forget, I should add that we have no idea what the hard distributions might look like for these problems... Average case complexity cannot even talk about superpolynomial running times (a la hidden clique, noisy parity etc).

This is what complexity theory is about. Sometimes, it needs to understand log factors in the running time. Sometimes, it needs to understand log factors in the exponent. Whereever there is some fascinating structure related to computational hardness, there is computational complexity.

While we construct exotic objects based on additive combinatorics and analyze the bias of polynomials, we should not forget that we are engaging in a temporary exercise of drawing a target around an arrow — a great exploration strategy, as long as it doesn't make us forget where we wanted to shoot the arrow in the first place.

And while complexity theory is too impotent right now to say anything about log factors, it should not spend its time poking fun at more potent disciplines.

The non-Gödel papers

2009-05-02T15:02:00.002-04:00

As you probably know, I think theory is in a deep crisis: our obsession to turn into philosophy (prividing unappreciated service to disciplines we do not understand), stemming from our deep commitment to become as ignorant and irrelevant as possible inside the CS department; the influx of people who like to pretend we're Mathematics, and have no idea what computation means; the obsession with the "polynomial" versus "non-polynomial" and it's many consequences; etc etc etc. Since I am not inclined to write novels, I have never been able to put all these arguments inside a coherent text.

Fortunately, every once in a while, the ball is raised at the net and I can say something short that expresses my feelings. Richard Lipton talks about the Gödel prize, and some papers that could also have won it. His examples are all in complexity, which is reasonable since he's a complexity theorist. But looking at the list of winners on Wikipedia, what it lacks more is algorithms — you know, papers that try to understand how fast some problems can be solved (the thing non-theorists believe we're studying).

Here is my own "forgotten list," from which I am certain to have forgotten some papers. Please add your favorite examples in the comments — but note that I am deliberately discarding old papers that were inelligible, like splay trees, classic flow algorithms, persistence, etc.

In no particular order:

[Fredman-Willard] on the fusion tree. This kick-started a major field (integer search) and directly led to at least two dozen follow-up papers in STOC-FOCS-SODA. Candidates for the Gödel Prize do not get any better.

This paper has passed its eligibility period, unfortunately. Another good candidate in this line of work would be [Thorup] solving undirected shortest paths in O(n) time.
Karger's papers on mincut, which are very influential on the use of randomization in graph algorithms.
Clarkson's introduction of randomization to geometry (thanks, Suresh!).
Chazelle's series on "Lower Bounds for Orthogonal Range Searching" is a remarkable contribution. However, Chazelle should probably just win the Knuth Prize since his contributions are too varied (MST, fractional cascading, triangulation, etc).
the power of two choices is an influential and popular idea. I'm not sure who should get the award though; as with PCPs, it can perhaps be shared by a couple of papers.
dynamic graph algorithms are a broad, deep, and popular research topic. [Henzinger-King] and [Holm-de Lichtenberg-Thorup] could win a joint award for polylogarithmic connectivity. These papers basically restarted the whole area and led to maybe 2 dozen publications in STOC-FOCS-SODA. The latter is also a popular data structure to teach, for its basic beauty.

Another candidate pair for a joint award would be [Demetrescu-Italiano] and [Sankowski], which give remarkable solutions to all-pairs shortest paths and transitive closure.

Add your own favorite examples in the comments.

So, am I claiming an anti-algorithmic bias because these papers did not win? No, all sorts of randomness is involved in prizes. I am claiming an anti-algoritmic bias because, in the current environment, it seems such papers are not even viable candidates.

Christos a înviat!

2009-04-19T04:49:00.000-04:00

Happy Easter! Christos a înviat!

Theory and Practice

2009-04-14T17:06:00.003-04:00

Via David Eppstein, I find out about the Workshop on Theory and Multicores. A memorable citation from the call:

[...] Indeed, the programs of many mainstream computer science conferences, such as ASPLOS, DAC, ISCA, PLDI and POPL are heavily populated with papers on parallel computing and in particular on many-core computing. In contrast, the recent programs of flagship theory conferences, such as FOCS, SODA and STOC, hardly have any such paper. This low level of activity should be a concern to the theory community, for it is not clear, for example, what validity the theory of algorithms will have if the main model of computation supported by the vendors is allowed to evolve away from any studied by the theory. The low level of current activity in the theory community is not compatible with past involvement of theorists in parallel computing, and to their representation in the technical discourse.

Which theory community? The one that thinks our machine models are not robust enough to tell the difference between O(n lg n) and O(n⁵)? The one that thinks n^{O(1/ε^2)} is polynomial and even efficient? The one that thinks Amazon should be happy with an O(lg³n) approximation for its profit? The one that thinks the coolest conclusions we ever came to are the philosophical implications of interactive proofs and zero knowledge?

The theory community will do just fine, thank you very much.

As for "the low level of current activity" being incompatible "with past involvement of theorists in parallel computing" --- it is exactly the past involvement that led to the current attitude towards parallel computing! Parallel computing is the fabled field where we got burned badly, and the first example people use to argue that theory is still very young. (It usually goes like this: "Imagine an equivalent of Perelman disappearing for 20 years and coming back with an answer to the most burning question about PRAMs from 1985. Who would care now?").

It's going to be hard to regain enthusiasm about parallel computing, as timely as the moment may be.

But at least we learned our lessons. Never again will a hyped-up mob of theorists rush head-on to study a machine model too early. Never will we study a machine model before such computers are even built, and while the practicality of such computers is still debated. We understand that producing a theoretical model too early will have us chasing the wrong rabbits, and that our results might be as relevant as the 5-state 17-symbol universal Turing Machine was in the design of the Pentium.

Alright, enough of this. I should go back to reading about 3-round quantum interactive proofs with entanglement.

Puzzle: Short-hop permutations

2009-04-08T17:47:00.005-04:00

Count the number of permutations of size n, such that |π(i) - π(i+1)| ≤ k, for all i. That is, the hop between any two consecutive values must be short.

I am asking for an algorithm, not a closed formula. (Combinatorialists: is one known?)

Your algorithm should work fast for values like n=10⁶ and k=8. I have not thought hard about supporting larger k (say, k = 20), but I would certainly be interested to hear such a solution if you have one.

Credits. This problem was used in a selection contest for the Romanian olympic team. The original author was Marius Andrei. My subjective judgment of its difficulty is "average+" (it was tricky, but I solved it within 10 minutes). YMMV.

CC4: One-Way Communication and a Puzzle

2009-04-08T01:29:00.004-04:00

As we will discuss in the next post, for some application it suffices to get lower bounds on the one-way communication complexity -- that is, the case in which a single message is sent, either from Alice to Bob, or from Bob to Alice. The party receiving the message must immediately announce to answer, based on the message and their own input.

Referring to our INDEXING lower bound in CC3, we can immediately obtain a one-way lower bound by setting a=0 (one message Bob→Alice) or b=0 (one message Alice→Bob). We conclude that Alice must send Ω(n) bits in the A→B model, and that Bob must send Ω(lg n) in the B→A model. The former case is much more interesting in applications, so when people say "the one way communication complexity of INDEXING," they always mean the Alice→Bob model.

One-way communication is often simple to analyze, and we can obtain lower bounds by direct appeal to information theory. Here is a short and simple proof of the INDEXING lower bound:

Lemma. The one-way communication complexity of INDEXING is Ω(n).

Proof. Assume there exists a protocol in which Alice sends n/10 bits, which works with probability (say) 0.99 over the uniform distribution. We use this to construct an encoder for a random vector of n bits. We show that the average length of the encoding is strictly less than n, which is a contradiction because the entropy of the random bit string is n.

Say we want to encode A[1..n]. We give Alice the input A, and include her message M in the encoding. Then, we specify the set of indices i, such that, if Bob has input i and receives message M from Alice, he will give an incorrect answer to INDEXING. This is the entire encoding.

Claim 1: we can decode A from the encoding. To accomplish this, simmulate the action of Bob for every possible i. For every index in the bad set, A[i] is the opposite of what Bob says.

Claim 2: the average size of the encoding is at most 0.85 n. The first component (Alice's message) is n/10 in size by assumption. The second component has size lg(n choose k), where k is the number of bad indices for a particular A. How do we analyze the expected size of this component?

E_A[k] = 0.01 n. Indeed, for uniformly random A and i, the algorithm works with probability 0.99. So in expectation over A, the bad set of indices has size 0.01 n.
By the Markov bound, Pr_A[k ≤ 0.02 n] ≥ 1/2.
When k ≤ 0.02 n, lg(n choose k) ≤ n/2.
When k ≥ 0.02 n, lg(n choose k) ≤ n.
Therefore E[lg(n choose k)] ≤ 0.75 n.

Therefore, the total size of the encoding is 0.85 n in expectation, contradiction.

□

A puzzle. Since this blog has featured algorithmic puzzles recently, it's time for a lower bound puzzle:

Say Alice and Bob receive two set of n elements from the universe [n²]. Show that the one-way randomized communication complexity of set disjointness is Ω(n lg n) bits.

This is the best result possible, since Alice can specify her entire set with O(n lg n) bits, after which Bob knows the answer with no error.

In fact, the O(n lg n) complexity holds even for large universes: use a universal hash function from the universe to a range of 100 n². The hash functions introduces zero collisions with probability 99%, so it doesn't introduce false positives in the intersection.

Acknowledgements. Thanks to Mert Sağlam for telling me about this question. As far as I know, the proof is folklore. David Woodruff wrote an email describing this result many years ago.

Puzzle: Cycle Containing Two Nodes

2009-04-06T01:40:00.003-04:00

The following simple puzzle was circulating among Romanian olympiad participants around 1998. It was supposed to be a quick way to tell apart algorithmists from mere programmers.

Given an undirected graph G, and two vertices u and v, find a cycle containing both u and v, or report than none exists. Running time O(m).

Update: Simple ideas based on a DFS (like: find one path, find another) do not work. Think of the following graph:

If you first find the path s → a → b → t, you will not find a second.

The one-line answer is: try to route two units on flow from s to t in the unit-capacity graph (with unit node capacities if you want simple cycles). This is not the same as two DFS searches, because the second DFS is in the residual graph (it can go back on the edges of the first DFS).

About the previous puzzle: As many people noticed, Alice can guarantee a win or a draw. She computes the sum of the elements on odd positions and the sum on the even positions. Depending on which is higher, she only plays odd positions or only even positions. (Bob has no choice, since the subarrays he's left with always have the ends of the same parity.)

But how do you compute the optimal value for Alice? If the sum of even and odd is equal, how can Alice determine whether she can win, or only draw? A simple dynamic program running in O(n²) time works. Can you solve it faster?

CC3: the good, the bad, the ugly

2009-04-03T01:14:00.003-04:00

This is the 3rd post in the thread on communication complexity, following Episodes 1 and 2.

This post is also available in PDF.

In today's episode, we will prove our first randomized/distributional lower bound. We will consider a problem that appears quite trivial at first sight -- INDEXING, defined as follows:

Alice receives a bit vector, x ∈ {0,1}ⁿ
Bob receives an index, y ∈ [n] (note standard notation: [n]={1,...,n})
their goal is to output x_y, i.e. the y-th bit of the vector x.

One way to view INDEXING is as the simplest case of lopsided set disjointness, where Bob's set is of size one: Alice receives the set S = { i | x_i=1 }, and Bob receives T = { y }.

Intuition. What trade-off should we expect between Alice's communication a, and Bob's communication b? Clearly, the problem can be solved by [a=1, b=lg n] and by [a=n, b=1].

In between these two extremes, the best use of b seems to be for Bob to send b bits of his index. Alice now knows the index to be in a set of n/2^b possibilities. She can simply send all her bits at these positions, using communication a = n/2^b. Finally, Bob announces the answer with one more bit.

We thus showed the upper bound: a ≤ n/2^b-1. It should be fairly intutive that this is also a tight lower bound (up to constants). Indeed, no matter what Bob communicates, his index will be uncertain in a set of n/2^b possibilities (on average). If Alice sends less than n/2^b+1 bits of information, at least half of the possible index positions will not have a specified answer based on Alice's message. In other words, the protocol fails to determine the answer with constant probability (i.e. makes constant error).

Distributions. Before proving a distributional lower bound, we must find the distribution that makes the problem hard. From the intuition above, it should be clear that the right distributions are uniform, both for Alice's vector and for Bob's index.

Rectangles. We are in the situation of product distributions: the inputs of Alice and Bob are independent. This is a very good situation to be in, if you remember the main take-home lesson from Episode 1: rectangles. Remember that some fixed communication transcript is realized in a combinatorial rectangle A x B, where A is a subset of Alice's possible inputs, and B a subset of Bob's possible inputs. The main ideas of a deterministic proof were:

little communication from Alice means A is large;
little communication from Bob means that B is large;
but the rectangle must be monochromatic (the answers must be fixed, since the communication is over)
if A and B are large, you must have both yes-instances and no-instances.

For a product distribution, we will perform essentially the same analysis, given that the densities μ(A) and μ(B) can be measured independently. The only difference will be that the rectangle is not monochromatic, but almost monochromatic. Indeed, if the protocol may make some errors, the answer need not be fixed in the rectangle. But it must happen that one answer (yes or no) is much more frequent -- otherwise the error is large.

The first three steps of the analysis are formalized in the following randomized richness lemma, from the classic paper of [Miltersen, Nissan, Safra, Wigderson STOC'95]:

Lemma. (randomized richness) Say Alice and Bob compute a function f : XxY -> {0,1} on a product distribution over XxY. Assuming that:

f is dense, in the sense that E[ f(x,y) ] ≥ α ≥ 1/5.
the distributional error is at most ε.
Alice communicates a bits, and Bob b bits.

Then, there exists a rectangle AxB (A⊂X, B⊂Y) satisfying:

Alice's side is large: μ(A) ≥ 2^-O(a);
Bob's side is large: μ(B) ≥ 2^-O(a+b);
the rectangle is almost monochromatic: E [ f(x,y) | x∈A, y∈B ] ≥ 1- O(ε).

Proof: Though the statement is very intuitive, the proof is actually non-obvious. The obvious approach, which fails, would be some induction on the bits of communication: fix more bits of the communication, making sure the rectangle doesn't decrease too much, and the error doesn't increase too much in the remaining rectangle.

The elegant idea is to use the deterministic richness lemma. Let F be the output of the protocol (what Alice and Bob answer). We know that f and F coincide on 1-ε of the inputs. By definition, the protocol computes F deterministically with no error (duh!). It is also clear that F is rich, because it is dense E[F] ≥ α-ε.

So apply the deterministic richness lemma from Episode 1. We get a large rectangle of F in which the answer is one. But how do we know that f is mostly one in the rectangle? It is true that F and f differ on only ε of the inputs, but that ε might include this entire rectangle that we chose! (Note: the rectangle size is ~ 2^-ax 2^-b, so much much smaller than some constant ε. It could all be filled with errors.)

We were too quick to apply richness on F. Now define G, a cleaned-up version of F. Consider some transcript of the protocol, leading to a rectangle AxB. If the answer is zero, let G=0 on AxB. If the answer is one, but the error inside this rectangle is more than 10 ε, also let G=0. Otherwise, let G=1 on the rectangle.

How much of the truth table gets zeroed out because of excessive error (above 10 ε)? Well, the overall average error is ε, so we can apply a Markov bound to it: the mass of all rectangles in which the error exceeds 10 ε is at most 1/10.

Thus, G is also fairly dense: E[G] ≥ E[F] - 1/10 ≥ α - (1/10) - ε ≥ 1/10 - ε. Thus, G is rich, and we can find a bit rectangle in which it is identically one. But in that rectangle, E[f] ≥ 1 - 10 ε by construction of G.

□

The good, the bad, the ugly. It remains to prove that in any large rectangle, the fraction of zeros must be non-negligible (it may not be almost all ones). This part is, of course, problem specific, and we shall do it here for INDEXING.

Unfortunately, these proofs are somewhat technical. They typically apply a number of "pruning" steps on the rectangle. An example of pruning on the space of rectangles was seen above: we zeroed out all rectangles that had more than 10 ε error. In these proofs, we throw out rows and columns we don't like for various reasons. One usually makes many funny definitions, talking about "good rows", "bad rows", "ugly columns", etc.

While looking at such proofs, it is important to remember the information-theoretical intuition behind them. After you understand why the statement is true (handwaving about the information of this and the entropy of that), you can deal with these technicalities on the night before the STOC/FOCS deadline.

Here is how the proof proceeds for INDEXING:

Lemma: Consider any A ⊂ {0,1}ⁿ and B ⊂ [n] such that |A| ≥ 2ⁿ⁺¹ / 2^|B|/2. Then E_A,B[f(x,y)] ≥ 0.95.

Proof: Assume for contradiction that Pr_A,B[f(x,y) = 0] ≤ 1/20. Let an ugly row be a row x∈A such that Pr_B[f(x,y) = 0] > 1/10. At most half of the rows are ugly by the Markov bound. Discard all ugly rows, obtaining A'⊂A, with |A'| ≥ |A|/2.

For every remaining x∈A', we have x_y=0 for at least 0.9 |B| indices from B (this is the definition of f). Call these good indices.

There are (|B| choose 0.9|B|) = (|B| choose 0.1|B|) choices for the good indices. For every set of good indices, there are at most 2^{n - 0.9|B|} vectors x which are zero on the good indices. Thus:

|A'| ≤ (|B| choose 0.1|B|) 2^{n - 0.9|B|} ≤ 2ⁿ 2^{O(0.1 |B| lg 10)} / 2^0.9|B| = 2ⁿ / 2^{0.9|B|-O(0.1 |B| lg 10)}

This is at most 2ⁿ / 2^0.5|B| , at least for a sufficiently small value of 1/10 (I never care to remember the constants in the binomial inequalities). We have reached a contradiction with the lemma's guarantee that A is large.

□

Combine this with the richness lemma with an error ε=0.05. We have |A|≈2^n-a and |B|≈n/2^b, so it must be the case that a = Ω(|B|) ≥ n/2^O(b). We have obtained a tight lower bound.

Matching in Regular Bipartite Graphs

2009-04-01T22:26:00.003-04:00

It is well known that d-regular bipartite graphs have a perfect matching. Applying this iteratively, it even follows that such graphs can be decomposed into the union of d perfect matchings. (The existence of a matching follows from Hall's theorem, which is probably beaten into students during any combinatorics course.)

But how easy is it to find a perfect matching in a d-regular bipartite graph? The following classic gem finds a matching in O(m) time --- but, oddly enough, it assumes d is a power of two!

Find an Eulerian circuit of the graph in O(m) time, which exists for any even d. Now throw out the 2nd, 4th, 6th, etc edges of the circuit. You are left with a graph that is (d/2)-regular. Recurse to find a matching.

Why do you get a regular graph when you throw out all edges on even positions? Think about it: the edges of the circuit go back and forth between the two parties of the graph. For any vertex v, its d incident edges are grouped into d/2 pairs of consecutive edges. One edge of such a pair appears on an odd position in the circuit, and one on an even position.

This algorithm is due to Gabow and Kariv [STOC'78]. By contrast, obtaining a linear-time algorithm for d not a power of two took until 2001 [Cole-Ost-Schirra]. In SODA'09, [Goel-Kapralov-Khanna] achieved sublinear algorithms for d greater than sqrt(n). The idea is that matchings are so frequent that you can still find one (with care) in a random sample of the graph.

My interest is not so much with the sublinear complexity, but more with matching in general bipartite graphs (not regular). After you see this beautiful algorithm for matching in regular graphs, it is hard not to feel a bit optimistic that general bipartite matching may also be solvable in O(m) time.

A Classic Problem

2009-03-26T18:05:00.001-04:00

Consider a doubly-ended queue with 1000 elements. Alice and Bob take turns to remove an element from either end of the queue. The player who removes a larger sum wins.

Who wins the game?

This problem appeared in IOI 1996 in Hungary, but it's a well-known puzzle by now.

Communication Complexity (II): Randomized, Distributional

2009-03-25T23:52:00.003-04:00

Prelude: A while back I posted an introduction to communication complexity, in which I showed how to obtain deterministic lower bounds by analyzing monochromatic rectangles. That post is also available in PDF if you want to review it.

I will continue with a series of posts giving a "practical introduction" to communication complexity. This will hopefully be a good reference to whoever wants to work in the area. I will ignore as much theory as possible (I find the theory of communication complexity to be quite dry compared to the applications), and take you straight to proving interesting bounds.

Episode 2. This episode will set up the theory of randomized communication. There are two common extensions beyond deterministic protocols:

randomized complexity:: The protocol tosses some coins to determine its actions. The communication complexity is fixed independent of the coins. For any input, the protocol gives a correct answer with probability 2/3 over the coin tosses. This probability can be amplified to any 1-ε, by running O(lg(1/ε)) independent repetitions in parallel, and taking the majority answer.
distributional complexity:: A distribution D is specified over the input pairs (x,y), where x is Alice's input, and y is Bob's. The protocol uses some fixed communication complexity, and it gives a correct answer with probability 1-ε over D. Note that amplification is generally impossible (two independent copies behave identically when run on the same input).

The case of randomized complexity further splits into two subcases:

public coins:: The coin tosses are observed by both Alice and Bob.
private coins:: Each player tosses his own coins privately. They may, of course, communicate the outcomes if they wish. The players trust each other fully, so privacy only makes life more difficult.

Cannonical example: Equality. Let Alice and Bob receive two n-bit vectors x,y ∈ {0,1}ⁿ. Their goal is to determine whether x=y. The complexity of this function by each measure is:

Deterministically, the total communication must be Ω(n), so the players cannot do anything nontrivial. Oddly, this does not follow by richness, as the lower bound is episode 1 (the equality function is only [2ⁿ,1]-rich). Nonetheless, it can be deduced elementary, as follows.

We claim that any 1-rectangle cannot be nontrivial (i.e. have more than one cell). If the sides of the rectangle are {x₁, x₂, ...} and { y₁, ...}, then x₁ = y₁, x₂ = y₁, but x₁ and x₂ were distinct.

On the other hand, there are 2ⁿ cells with a value of one (the diagonal of the matrix). So there must be Ω(2ⁿ) different rectangles, which can only be obtained by communication Ω(n).
The public coin complexity is O(1). Choose a hash function h:{0,1}ⁿ -> [100] by public coins. Then Alice can communicate h(x), and Bob says yes iff h(x)=h(y). The error probability is 1/100 if h comes from a universal family.
The private coin complexity is Θ(lg n). For the upper bound, Alice chooses a hash function, and communicates both the hash function and h(x). The hash function takes O(lg n) bits to communicate (if you know stuff about universal hash functions, the optimal description size grows like loglog of the universe, which in this case is 2ⁿ).

The lower bound is not important.
The distributional communication complexity is only defined if we specify some distributions. For instance, if D chooses x and y uniformly and independently, a protocol with zero communication works with probability 1 - 1/2ⁿ. Indeed, Pr[x=y] = 1/2ⁿ, so you may just always answer "no."

Some theory. You can spend some time investigating the relations between these complexity measures, but personally I find this to be dry theory. Here are a few basic factoids you should know.

Lemma 1. Public coin complexity ≤ Private coins complexity ≤ Public coins complexity + O(lg n), where n is the size of the inputs.

Proof: This result may seem surprising at first -- Alice and Bob may toss many public coins and use them in a nontrivial way. How can they simmulate this with private coins and just O(lg n) extra bits of communication?

In fact, however, the proof is pretty standard in the land of derandomization. The main idea is that you can sample from the space of coin tosses, and understand the behavior just on the sample. Say you sample 100n strings of random coin tosses. On some input (x,y), the average error probability on the sample is roughly equal to the average error over the true random coins, with probability 1 - 2^-Ω(100 n) over the random sample.

But there are only 2²ⁿ possible inputs. Thus, there exists a sample which simultaneously works for all inputs (for a large enough value of 100). The protocol may restrict itself to the sample without loss of generality. Then Alice, can pick one of the sample strings by private coins, and communicate the choice with lg(100n) bits.

□

This lemma shows that the gap that we saw in Equality is the maximum possible. The take-away message is that we almost never worry about private-coin complexity, since this restriction changes the complexity so little. When people say "randomized protocol" they almost always mean "public-coin randomized protocol."

Lemma 2. Say some problem has a randomized (public-coin) protocol with error probability ε. Then, for any distribution D, there exists a protocol with distributional error ε.

Proof. Let e(x,y)=1 iff the protocol makes an error on inputs x,y. The randomized protocol gives (∀) x,y: E_coins[e(x,y)] ≤ε.

Since every term is bounded, so is the mean: E_(x,y)~D[ E_coins [e(x,y)] ] ≤ε.

But then we can switch the expectations: E_coins [ E_(x,y)~D [e(x,y)] ] ≤ε.

Finally, there exists a setting not exceeding the mean: (∃) coins: E_(x,y)~D[e(x,y)] ≤ε. Having fixed the public coins, the protocol is deterministic.

Observe that the protocol depends on the distribution D, because the coins are fixed after seeing the distribution, and they're built into the protocol.

□

So what does this mean in practice? Just like randomized algorithms are more natural for upper bounds, distributional analyses are more natural in lower bounds. A natural lower bound starts by proposing a distribution D on the inputs that makes the problem hard. Then, it proves that no protocol can work well on that distribution, implying a distributional lower bound. This is the strongest statement of the lower bound.

However, as an added bonus, the lower bound implies that no randomized protocol can solve the problem any better. If you think about it, this is obvious: any randomized algorithm can be made deterministic by picking its best set of coins (the coins minimizing error on the hard distribution).

In principle, it might be possible to show randomized lower bounds directly, without also showing distributional lower bounds. This would be somewhat odd, because it would mean you are showing a lower bound, but you cannot tell us how to choose hard inputs (then why is the problem hard?). Currently, all known randomized lower bounds also give distributional lower bounds.

The above lemma is sometimes called "the easy direction of Yao's lemma." I oppose the terminology, since it's sily to be giving credit for kindergarden observations. The real "Yao's Lemma" (or the hard direction thereof) is the following:

Lemma 3. Assume that for any D, there exists a protocol with distributional error ε. Then, there exists a randomized protocol with error ε.

This tells us that trying to find a hard distribution always makes sense. If there exists no distribution that makes the problem hard, it must be that it's actually easy (for randomized algorithms). This is an interesting philosophical statement ("you can always find a hard distribution"), but of course, it is never used in practice.

The proof is based on the von Neumann's minimax theorem (something you might learn about in economics and game theory). The proof is not important for communication lower bounds, though the minimax principle is something well worth understanding.

Blogs, research, being social

2009-03-22T23:53:00.002-04:00

Richard Lipton has a new blog. Noam Nisan has a new blog.

Does TCS have too many blogs for its own sake? No doubt about that. My Google Reader list of blogs has long ago been downgraded from STOC/FOCS status ("should be aware of") to SODA status ("occasionally you can see interesting things").

This partially explains why I haven't been writing much. What should I write on? Maybe I should describe results in my area. But I never learned anything about graph drawing from David Eppstein; for me graphs are means, not ends.

I never learned any cryptography from Luca. The really basic problems in cryptography are basic complexity questions -- I already know them, and have no clue how to attack them. The cryptographic side of crypto... well, they can deal with it themselves. I'm only interested enough to hear about it when it's done. [NB: Luca's rare posts about Italian research are cool though -- I use them to argue that research in Romania sucks not because we are emerging from 50 years of comunism, but because we descend from Rome. How many researchers from those countries who never worked in the US can you name?]

I now understand why online courseware can never replace physical courses: in a physical course, the professor has to waste quite a few hours of his day preparing and teaching. For the student, this sacrifice should (in principle) mean that the stuff is important enough. What would be an equivalent online mechanism that could extract an equivalent sacrifice? Maybe I should pledge $10 to a charity for each person that reads one of my technical blog posts carefully.

On the other hand, maybe I should write non-technical blog posts trying to influence the community. But I never became convinced that I should include experiments¹ in my papers. And neither did "the community:" if you ever read comments on Michael's somewhat puritan blog, you have undoubtedly noticed that he mostly gets comments from people who agree with him, and is usually ignored by theory die-hards.

¹ If you really must know, I find that algorithm engineering is a craft in itself (which I have been lucky enough to practice in my non-TCS life). Asking for experiments is like saying you are only interested in papers that completely close a problem.

The obvious issue is the one of sacrifice that I mention above. If you want to convince me of something, let's grab a beer and I'll listen. Proselytizing on the web is too cheap.

Well, then, maybe I should not care too much about content, and should write general observations about life, the universe, and everything (a la Lance, Scott). The main problem is that we already know the answer.

For as long as I can remember, I have been trying to understand society through mathematics, computer science, economics, mechanism design, etc. If you have a țuică with me, you run a risk of hearing my theories of what the continuum hypothesis really means, what undecidability really means, why the world is the way it is, what the role of research is, how to change this or that aspect of society, and so on. But I do have enough drinks with my friends, and I am left with zero motivation to blog about such things. Online mental exercises are wasted on me.

Which brings me to my next point... The social aspect of research was already bad enough. I grew up going to computer contests, where you were either good enough to win, or not good enough (for instance, in my first year of high school, I missed qualifying for the IOI by 2 points out of 900, which I found fair enough, if somewhat random). Ideally, research positions should also be handed out by a 5-year contest for solving hard problems, not by who can draw the biggest target around his arrow.

The social aspects of the research world may inescapable. But on blogs, hype travels much faster, and waves grow into tsunamis. Noam talks about the impact of blogs on highlighting results. For all our talk about theoretical depth, our work is already too shallow, if you ask me. I'd hate it if research turned into a Facebook contest for popularity. (NB: This discussion is unrelated to Mark Braverman's recent result, which did get quite a few blog posts.)

Maybe it's time to think about some problems.

The LSD Proof

2009-03-20T00:24:00.003-04:00

From my colleagues among Israeli faculty, I hear strange tales about dealing with people who want to be your PhD students. It seems so many students are enthusiastic about doing a PhD (with theory faculty!), that hazing them becomes a good idea. As the stories go, you should tell your candidate students "Go read this paper, and come back once you've understood it."

The trick, of course, lies in your choice of the paper. If you ever want to do this to somebody who dreams of working in communication complexity, you might try this lower bound for lopsided set disjointness. The proof is straightforward to me, but it is fairly long and diverse, throwing all the tricks in the book at this problem. If you want to work in communication complexity, it makes sense to first reach the level where the proof is straightforward to you.

The story of set disjointness stretches back to the dawn of communication complexity. An optimal deterministic lower bound is easy to prove (see my earlier post). From what I understand, in the late 80's, proving a randomized lower bound was a major problem. The issue is that you cannot use independent distributions for Alice's and Bob's inputs, since two random sets will intersect with overwhelming probability.

A randomized lower bound was obtained in 1992 by [Kalyanasundaram, Schnitger] and by [Razborov]. The technique was explained in an information-theory view by [Bar-Yossef, Jayram, Kumar, Sivakumar], who also found new interesting applications.

The basic idea is to consider a distribution in which the two sets never intersect. Let the universe be split into n blocks. For each block, we will either choose Bob's element publicly, or choose Alice's element publicly. The other player gets a private random input that is different from the public choice, making the sets disjoint. Under this distribution, the blocks are independent. Thus, if the protocol communicates o(n) bits in total, I can find a block about which it communicates o(1) bits of information. I will now alter the distribution, making it independent on that block alone. The protocol is still the same, so it will have large error because it cannot spot the difference.

In STOC'95, [Miltersen, Nisan, Safra, Wigderson] introduced asymmetric communication complexity (in which Alice and Bob have inputs of significantly different sizes), and showed how asymmetric lower bounds imply interesting data structure lower bounds. They proved an optimal deterministic lower bounds for asymmetric set disjointness, and left the randomized case as an "interesting" open problem. I suspect, however, that they simply did not have the time or motivation to work out how the previous techniques applied in the asymmetric case.

In my FOCS'06 paper with Alex Andoni and Piotr Indyk, we showed the first exciting application of lopsided set disjointness (LSD) to data structures: it implied that data structures with O(1) query time cannot solve (1+ε)-approximate nearest neighbor with less than n^Ω(1/ε²) space. This application only required a weaker version of an LSD lower bound, which could be proved with independent inputs given to Alice and Bob.

The really exciting development was my FOCS'08 paper, which showed that many interesting lower bounds could be obtained by just the right reductions from LSD. At this stage, I needed the optimal LSD lower bound --- so I just had to sit down and claim that the proof would appear in the journal version.

Ridden by guilt (and reminders from Jeff, acting as editor of the special issue), I had to finally write down the proof. Once you really, really understand the old symmetric technique, and you're confortable with the standard tricks from communication lower bounds, this proof is not too exciting. I'm glad to be done with it.

Midterm

2009-03-16T18:26:00.002-04:00

As you know, I am teaching Computability and Complexity at Berkeley. Here is the midterm I gave today. It may be fun for my younger readers to look through it. Leave comments.

Regarding problem 3: I believe nobody should get a CS degree without being able to reason about grammars, precedence, associativity etc. This is far more important that knowing pushdown automata, the pumping lemma or anything like that.

Problems 4 and 7 are typical interview puzzles. Unfortunately, not too many people recognized problem 7 as a disguise for the streaming problem of finding a majority element. I should have asked for Socrates to use only O(n) debates.

Problem 8 is actually hard. Even if you have an intuitive idea why Inca Machines cannot recognize more than regular languages, you need to find a couple of tricks to make it a formal proof.

Teaching

2009-02-27T19:56:00.004-05:00

Through an unexpected turn of events, I am teaching CS 172 at Berkeley. This is the standard course on Finite Automata, Regular Grammars, Turing Machines, undecidability, NP-completeness, etc. At Berkeley it is a course aimed primarily for seniors (i.e. it comes after Algorithms, Discrete Math, and usually other "advanced" courses).

Bill Steiger taught the first weeks (finite automata), but unfortunately he has had to return to New Jersey unexpectedly, and I was asked to take over.

So why did I accept? On the one hand, I can cite Feynman on why teaching is important: if you research fails for a while, you can at least find comfort in your constant teaching. But since said comfort is so easily found in wine, this does not quite explain it.

The main reason I accepted was that I remember taking this course with Mike Sipser in sophomore year: it was all so much fun. No student needs to go through this! This course should be significantly redesigned, and by teaching it, I can take a stab at the new version.

The main reasons I dislike the course are: (1) the mental masturbation: teach kids clean unimportant topics (because they're clean and elegant); and (2) the very out-dated perspective, which might have seemed elegant at the time, but with time has proven misleading. Here are some examples:

the pumping lemma. In the era in which limited state matters (think streaming algorithms), and we have many exciting developments in understanding limited state (by lower bounds), we have students memorize a mechanical way to show that {w w^R} is not regular.
push-down automata. In case you don't remember this: push-down automata are not a nice limited class of machines that can parse grammars --- they are nondeterministic ! Grammars that need the whole nondeterministic shebang are parsed via dynamic programs (most famously, the Earley). More restricted classes are parsed by algorithms with cryptic names, like the LALR parser.
the lack of exciting stuff in the undecidability section. People in programming languages and databases go on and on about decidable and undecidable logics. Surely there has to be a more exciting example than the Post correspondence problem (and, no, all rights to use "PCP" for this problem have been revoked as of 1990).
Turing machines. All computer-looking models of computation are equivalent within logarithmic (often constant) factors. Saying that we cannot fix a model of computation with less than a polynomial imprecision in the running times can only lead to a new generation of seriously misguided theorists.
the P vs NP fetish. I have too much to say about this, so let's keep it for another post. Suffice it to say that the P vs NP fetish has led to people ignoring major topics like fixed-parameter tractability or SAT sparsification.
a dry approach to space complexity. While things like NL= coNL are reasonably interesting, they seem to me far less interesting than space/time trade-offs. The issue of space/time trade-offs (which has some connection to what computation means in the real world) is completely buried by looking only at the space complexity alone, leading to some unexciting language theory.

My attempts to "fix" the course will be documented on this blog. In the time, please suggest your favorite topic that you think should be covered in introductory complexity courses.

FOCS 2009

2009-02-20T00:29:00.004-05:00

Sorry for not blogging. It's not that I've been busy -- it's more like incredibly busy.

Anyway, the FOCS 2009 call for papers seems to be out. Following are the key changes in the call.

Pre-submission abstracts: are out. As I said before, I am against them.

Full proofs: are required for the "central claims in the paper." Essentially, you don't need to prove that 3rd extension of your results that nobody will care about, but you need to write a complete proof of the main result (i.e. the really interesting result for which the paper is being accepted). When SODA'09 introduced this, my gut feeling was slightly against, but with time as a good advisor, I have become a convert. I am glad I managed to push this into the call (it was harder than I had expected...)

Here are excerpts from mails that I wrote on this topic:

[...] It happens too often that people submit a paper vague enough that an interested reviewer cannot even refute (how can you give counter-examples to something that is not fully specified in the paper?). Obviously, the job of conferences is not to check correctness, but if we get lucky with a passionate reviewer, we should allow him to do the job right. [...] PCmember makes a valid point that the committee can (and should) ask for clarifications when a proof is missing or unclear. But this does not rule out the following scenario: " Lemmas 13 to 15 don't have proofs in the paper. The reviewers never themselves thought about the problem, and the lemmas appear quite reasonable and straight-forward, so no objection is raised (no need to bother the author for a technicality). After the paper is published, somebody who has thought about the problem reads the proof and has doubts about Lemma 14. What now? " The paper should be verifiable not only by the committee (whose emails the author will certainly not ignore!) but also by future readers (imagine the authors' response time if the future reader is a guy with a funny name from China :).

I hope asking for complete proofs becomes standard. As with journals, the main reason to trust the proof is not that somebody else formally checked it, but that the author carefully wrote down a detailed proof.

Post-submission description: This is the biggest innovation in the call. You are supposed to write a 2-page description of your paper one week after the deadline, in which you informally describe the contribution, the main ideas etc.

I am very sorry that this made it. To be blunt, I think the two main reasons this idea made it were:

Some people thought something is "wrong" with current STOC/FOCS and something should be changed. People didn't quite have a consistent story of what was wrong or what should be changed, but the desire of change made the PC agree with the most radical experiment on the table.
There was no vote (almost nobody responded to a request for a vote). I have no idea whether 75% of the PC supports this, or a vocal 20% of the PC supported it. An unfortunate state of fact.

My formal objection was the following (several people agreed in private emails):

Essentially, we can make the conference system as complicated as we want: pre-submission abstracts, double blind, 2-page summary, video at time of submission, rebuttals, a million rules for conflicts of interest etc etc. Some field which obsess about some central conference implement some subset of these ideas (think SIGGRAPH, SIGCOMM etc). Fortunately, in theory we have avoided all this non-sense. We are implementing the basic systems principle: keep the interface simple. The process is minimal (submit a paper, get a decision and reviews). Since we have a fast turn-around cycle (with two major conferences a year, plus other reasonable conferences like SODA), there is no need to "bullet-proof" one conference. Any mistake by a PC should be rectified by the next one if the author clears up the misunderstandings in his paper. What would the 2-page abstract do? It would force me to cut some arbitrary part of my introduction (I typically have around 4 pages). Why impose this 2 page fixed format for what should be the introduction? Also, the 2-page abstracts would sanction the idea that a foggy introduction written at the last minute is ok, since you can rectify it 1 week later. -- Yes, yes, we threated that we may not read the 2-page abstract, but that is also wrong. If we actually don't read it, we seem like the evil PC that just wants to keep authors busy for no good reason. And any argument that "thinking about your contribution 1 week later is good for you" is as annoying as any paternalistic argument. Theory has a light-weight process centered on ideas. Anything else should be minimized. Let's keep it simple.

To be clear, everybody seemed to agree that the 2-page description is only an experiment, and future PCs should not borrow it without serious review. I hope it will die after this conference.

Against Pre-Submission Abstracts

2009-02-05T14:48:00.004-05:00

Claire Mathieu's SODA and Michael Mitzenmacher's STOC asked for paper abstracts to be submitted one week in advance of the deadline. As the FOCS'09 PC is debating this issue, I wrote the following email expressing my objections. I hope this makes sense to enough people, and we will abandon pre-submission abstracts in theory conferences.

I am strongly opposed to the 1-paragraph pre-submission abstracts, so let me try to argue against them. Many people, myself included, only write papers in the last week before the deadline. It doesn't matter why this happens, but the PC has to be accommodating. We cannot lecture the community about how they "should" write papers. ( If the argument about being accommodating is not a strong enough for you, I claim that it is, in fact, the optimal rational decision to only write papers the week before. If you're working on several problems at the same time, you're usually stuck waiting for some brilliant idea to move forward. Such ideas come more frequently when you're relaxed and allow your mind to explore improbable paths --- i.e., such ideas tend not to come in the last week. Writing a formal paper, however, is a much more predictable thing: apply brain power, get the proof. This can be done in the last week, even when sleeping little and working with a time constraint. ) If we accept the fact that some authors will write papers in the last week, it means that many of the abstracts will not materialize into papers (if a bug is found, or if the writing is not finished in time --- especially likely if complete proofs are required by submission). Abstracts that do not materialize into papers are annoying for everybody. For the authors, they are annoying because you have to write an abstract for something that doesn't exist yet, describing some results that might change slightly, and you're not even sure that all proofs will work and you will actually submit! For the committee, they're annoying because you are reading and bidding on non-existent papers, generating useless work. I don't see why these disadvantages are worth it. After all, we're only saving a few days (eliminating paper proceedings would probably save a month!). Cheers, -mip

Morse meets Hamming

2009-01-31T13:26:00.004-05:00

A while ago (2003), I proposed the following problem in the Romanian national olympiad:

You are given an alphabet of n letters, and the frequency p₁, ..., p_n with which each letter is transmitted. The goal is to find an optimal prefix-free binary encoding for the alphabet (as in Huffman coding). However, the code will be used for transmission over a telegraph, so the cost of a "zero" and "one" are different: a zero (dot) takes 1 second to transmit, and a one (dash) takes 2 seconds. Find an optimal code according to these costs and the given frequencies.

If you are an algorithmist, you will probably have fun thinking about the problem. What is the best running time that you can come up with? (I believe the best known is O(n²); getting any polynomial is already non-trivial.)

Generalizing this "telegraph problem" to arbitrary letter costs gives an interesting, SODA-esque research question that has been investigated quite a bit, but remains largely open. Say that a "zero" has cost α and a "one" has cost β (say β>α). The best known running times are n^β+O(1), but the problem is not known to be NP-hard for large β. Can you either show hardness or improve the upper bound?

If you are interested in previous work (including approximation algorithms), see Mordecai Golin's webpage, and follow references.

Talk at Berkeley

2009-01-20T23:21:00.002-05:00

A long long time ago, when we took our first computers course, we learned that computers represent things in bits, not in base 10, since bits are easier to store (say, charged vs uncharged capacitor). Well, bits may be easier for computers, but apparently not much easier...

We can represent an array A[1..n] of digits using ceiling(n log₂ 10) bits on a regular computer, such that reading or writing any A[i] value can be done in constant time.

Come hear the details at my talk tommorow (Wednesday, 12pm, Wozniak lounge, Soda Hall, Berkeley). The write-up is forthcoming, and will be posted here.

Succincter

2008-12-10T02:00:00.002-05:00

'Tis the season to be doing succinct data structures.

[P] My FOCS'08 paper demonstrated how to use recursion to achieve better redundancy. For many fundamental problems, it achieved a redundancy of n / (lg n / t)^t bits with query time O(t). The toy problem that people remember from my paper is storing trits: store A[1..n], where A[i] in {1,2,3}, using close to n log₂3 bits and fast access to A[i].

[Golynski] In SODA'09, Alexander Golynski (PhD from Waterloo, currently at Google NY) showed a remarkable lower bound for succinct data structures. Suppose you want to represent a permutation π such that you can access π(x) and π^-1(x) in time t. Then, your data structure needs redundancy Ω(n lg n / t²) bits. In particular, for constant access time, your data structure needs a constant factor more space than the minimum!

This is essentially the first "meaningful" lower bound for succinct data structures. [Gal-Miltersen] did prove a previous lower bound, but for a much harder problem: polynomial evaluation. (For this problem, we believe sublinear query time requires superpolynomial space, so never mind succinct data structures.)

Notice that Golynski's lower bound is much higher than my upper bound for storing trits and other problems. His bound is in fact tight for storing a permutation.

[Viola] Emanuele Viola looks at the trits problem in the bit-probe model and shows that, with bit probe complexity t, the redundancy needs to be at least n / 2^O(t). My result implies a redundancy of n / 2^O(sqrt{t}) if t is the bit-probe complexity.

As I always want to point out, the true model is the word RAM, but the bit-probe model is sometimes interesting as a mathematical curiosity.

[Mitzenmacher-Wiener] Michael has a student working on an implementation of the results in my paper. You could've guessed it from here, I suppose.

[P.-Thorup] In recent ongoing work, we gave a very strong result for the trits problem: we can achieve a redundancy of exactly 2 bits, with O(1) query time. This completely kills the problem.

In the bit-probe model, it immediately implies an upper bound matching [Viola].

It is not yet clear whether such strong upper bounds can be extended beyond the trits problem (e.g., for dictionaries and arithmetic coding). But we have some ideas and we are working hard on it (i.e. drinking and hiking).

B.A.M. 2

2008-12-01T02:15:00.002-05:00

The Berkeley Algorithmists' Meeting will continue on Tuesday at 3:30pm.

Scheduling. There have been enough calls to change the time that I will do a recount of the votes and probably change it starting next week. If you would like to come and have not sent me your time constraints, please send them ASAP to mip@alum-mit-edu

Lecture notes. There are definite plans to post lecture notes here, though scheduling constraints will delay this for another week or so.

New topic: Orthogonal Range Queries

I want to spend a couple of meeting talking about range queries, a hugely important topic (in my opinion) that we don't teach too much of. The theory that has developed around this topic is one of the deepest examples of a coherent theory in TCS (maybe close to PCPs, depending on your subjective perception of depth).

Some ideas we will discuss, in an order TBD:

persistence
predecessor search (especially van Emde Boas)
buffer trees
RMQ
the 3D structure of Nekrich
rank/select
lower bounds