Happy Easter! Christos a înviat!

## Sunday, April 19, 2009

## Tuesday, April 14, 2009

### Theory and Practice

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

^{5})? 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

^{3}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?

Posted by Mihai at 5:06 PM 23 comments Links to this post

## Wednesday, April 8, 2009

### Puzzle: Short-hop permutations

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.

^{6}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.

Posted by Mihai at 5:47 PM 4 comments Links to this post

### CC4: One-Way Communication and a Puzzle

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.

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

Say Alice and Bob receive two set ofThis 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.nelements from the universe [n^{2}]. Show that the one-way randomized communication complexity of set disjointness is Ω(nlgn) bits.

*n*lg

*n*) complexity holds even for large universes: use a universal hash function from the universe to a range of 100

*n*

^{2}. The hash functions introduces zero collisions with probability 99%, so it doesn't introduce false positives in the intersection.

Posted by Mihai at 1:29 AM 5 comments Links to this post

## Monday, April 6, 2009

### Puzzle: Cycle Containing Two Nodes

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

^{2}) time works. Can you solve it faster?

Posted by Mihai at 1:40 AM 16 comments Links to this post

## Friday, April 3, 2009

### CC3: the good, the bad, the ugly

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

- Alice receives a bit vector, x ∈ {0,1}
^{n} - 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.

_{i }=1 }, and Bob receives T = { y }.

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

^{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).

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

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

- 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(ε).

^{-a }x 2

^{-b}, so much much smaller than some constant ε. It could all be filled with errors.)

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.

^{n}and B ⊂ [n] such that |A| ≥ 2

^{n+1}/ 2

^{|B|/2}. Then E

_{A,B }[f(x,y)] ≥ 0.95.

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

_{y}=0 for at least 0.9 |B| indices from B (this is the definition of f). Call these good indices.

^{n - 0.9|B|}vectors x which are zero on the good indices. Thus:

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

^{n}/ 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.

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

Posted by Mihai at 1:14 AM 6 comments Links to this post

## Wednesday, April 1, 2009

### Matching in Regular Bipartite Graphs

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

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.

Posted by Mihai at 10:26 PM 1 comments Links to this post