Vanity of Vanities, all is Vanity

As already mentioned in Lance blog, there is a new proof of the PCP by Irit Dinur. The result is here: The PCP theorem by gap amplification. Irit gave today a talk in Tel-Aviv univerersity, and the result looks quite nice, and not too complicated. It base some similarity to Omer Reingold recent proof that s-t undirected connectivity is in L (STOC 05).

The basic idea of the new proof is to start from a graph constraint problem (say 3-colorability, but more generaly, consider a graph where every node can receive a value out of a finite alphabet. Each edge in the graph, has a list of valid assignments to the two adjacent nodes. The question is whether one can find an assignement that satisfies all those constraints. Proving the PCP theorem is thus equivalent to coming up with a graph which either has a satisfying assignment, or alternatively, every assignment violates a large fraction of the edges. Starting from the graph G (which is assumed to be of constant degree, with self loops, expander, and generally splendid [which can be guarenteed using the regular schticks]), the idea now is to consider the “squared” graph H=G^t (for t a moderlately small constant, say Ackerman(4) [just kidding, the constant is large but not redicilous]). Every node in the squared graph H, now stores the value of all the variables in its reachable!
neighberhood (of distance roughly t). Two nodes in H are connected iff they are in distance t in G (since all the nodes in t have self loops [with probablity 1/2], this means all nodes of distance at most t).

Now, consider an assignment to H. It induces an assignement to G (there is a big technicality here which I am avoiding – each vertex in G is assigned the value which the vertices in its neighberhood in H think it should be assigned). Consider the resulting assignment to G, and its gap (i.e.,. procentage of violated edges). We want to argue that the gap in H is much bigger (say, twice bigger). To this end, consider a viiolated edge e, and a path pi in the graph G of length t, that has e more or less in the middle of pi. The path pi corresponds to an edge in H which is also violated. Intuitively (and this is the main meat in the paper, and is deifnitely not trivial, using the expander property of G), there are going to be much more violated edges in H than in G (a lot of paths of length t are being ruined by passing through e). Thus, skipping a lot of interesting details [involving sqrt(t) in varios places, and the alphabet size squared], the graph H has twice the gap as G (ob!
serve that the starting gap must be at least 1/n, so after log(n) iterations we would be done).

We would like to continue the process on H. Unfortunately, H has three problems: (i) it exists, (ii) its degree is too high, and (iii) the alphabet size used in each vertex is too large. The first problem is the graph own problem, and we ignore it. The second problem can be handled (and I am hazy about the details) by replacing each vertex by an expander (???), and the third problem is solved in the classical PCP way [of feeding the snake ot itself till it loses weight], by plugging in another small PCP verifier to replace every vertex. This reduces the alphabet to managable size, and we can apply the construction again, till the gap becomes a constant. The graph H is only a constant factor larger than G, and as such, after log(n) iterations, we would have a graph with polynomial size, and cosntant gap. Viola!

Overall, as far as I could judge from the talk, a very nice result, and much more understandable than the old stuff. Now, I just hope that nobody that really read the paper and understands it, would read this entry, and would point out my 50,000 mistakes. I only hope that all my mistakes cancel themselves out…

I am/was in Israel for the last several days, and the wether is perfect – sunny not to hot days. So many things are so very nice (like parents, friends, the food – vegtables having taste, etc), that in some corner of my mind I start wondering what I am doing in the US.

Of course, I know that this is a quiet period (politicaly), and that the hot days are just around the corner, and things that would drive me off the wall (like politics, rudeness of people, low salaries, etc) I am just ignoring. But still, it is nice to know there is a place where you can go to and feel comfortable in.

Anyway, the biggest news story of the day in Israel, is an industrial espionage story, where private investigators installed trojan-hourse software in companies CEOs computers, and essentially copied all their content. You can read all about it here. This is another example of inherent volonerability of companies that rises from the basic architecture of the OS used by 95% of computes in the world. This is a frightening thing for every one of us – losing the privacy of our own computers. For an instructor the larges tnightmare is of course that their final would leak before the exam. In any case, a lot of “security” companies are jumpng up and down trying to sell their products (of course, since security does not exist and is just a state of mind, those companies provide more of psychological services to the nerverecked companies).

Of course, all the companies that got this services, knew that the source of the documents was illigal. But, taking the “dont ask dont tell” attitude they were happy to get the information about their competition. Thus, competition and opertunity had caused them to cross into illigal ruthless behaviour. It would be interesting to see if the police would not only indicate the private investigators, but would also go after the companies that hired them.

This ruthless competitiveness, reminded me of a good science fiction book remotely along those lines: Catspaw by Joan D. Vinge. The previous book in this series and the followup books are unfortunatley not so good.

I was in STOC 05. It was very nice and there were some interesting results. I left from Baltimore to JFK and from JFK took a plane to Heathrow, London. LHR has the design charm of a brothel combined with the chaotic nature of a middle-eastern market. In any case, my flight to LHR was delayed by one hour, and I missed my connection to Tel-Aviv. After going from terminal 4 to terminal 3, to check if I missed my connection, I had to go to terminal 3 to get rerouted, after that I had to go to termainal 4 to catch my flight in the afternoon (I landed early morning). Every time I had to change terminal, I had to take a bus which took about 10-20 minutes (with waiting). Since i was completely tired from the flight, you can imagine how inspiring this experience was (inspiring for somebody that wants to begin a Jihad – maybe thats explains Al Queda – they just had really bad connections).

In any case, I flew to Israel via Brussels, and arrived to Israel just after midnight. The new airport terminal in Tel-Aviv is really impressive, BTW.

(And if you are in Israel and you want to meet me, just email me.)

We are roughly one month away from the submission deadline (June 24 for full papers and June 17 for abstracts) for FSTTCS.
The submission server is here.

FSTTCS is going to be in Hyderabad, India.

Going to India should be fun. The only question if the Indian defense system will again succeed in blocking me from coming…

I am currently reading the book _A people’s history of the united states_. This is somewhat of a left wing rant, with an interesting twist: How does history looks like from the point of view of the people? (Instead of nations.)

At times this book reads like the history of the left more than the history of the US, but it still exposes parts of history which were partially forgotten in the collective history. For example, violent fights between workers and guards and military (19 century), the colonial war in the Philippines. Etc.

It is amazing how far we had come in 150-200 years. In 1840 the literacy rate among women in the US was 40% and 70% among men.

Another impressive thing is how the fear of Communism (and socialism) made the US a more reasonable place economically, for the lower and middle classes. It is interesting that now there are indications. that since communism had failed, the US again is moving against the lower economic classes. Will we regret the day that Communism fell? After all, the amount of money the US is putting into basic research was cut because of the end of the cold war.

While the cold war tunneled energies into competitiveness. The current situation, seems to tunnel the US energies into aggressiveness. Not surprisingly, the US is finding itself overstretched militarily, and with an economy which is less able to compete in the global market.

The solution? Reading a right wing history book and having a larger tax cut. Of course!

CRA prize for undergrad student Mihai Patrescue.

The Goedel prize went to the paper
The space complexity of approximating the frequency moments by Noga Alon, Yossi Matias and Mario Szegedy, which appeared in STOC 1996.

I spent a week in Duke working with Pankaj and some other people. It was very nice. I played with some nice lenses for my camera, and decided to buy some additional lenses for my camera. After that I went to STOC, where I am now sitting in the business meeting.

**LONE STARR**: Helmet. So, at last we meet for the first time for the last time.
**DARK HELMET**: Before you die, there is something you should know about us, Lone Starr.
**LONE STARR**: What?
**DARK HELMET**: I am your father’s brother’s nephew’s cousin’s former roommate.
**LONE STARR**: What’s that make us?
**DARK HELMET**: Absolutely nothing—which is what you are about to become. Prepare to die.

>From Spaceballs – a better movie to watch than _Star Wars VI the revenge of the baby sat_.

The call for open problems for SoCG (here), is a good excuse to visit the problem of computing small coreset for **k**-median clustering in high dimensions.

Here is the problem: Given a set **P** of **n** points in Rd, find a (weighted) subset S of the points, such that for any set of C of k points, clustering S with C, is roughly the same price [i.e. up to (1+/-eps)] as clustering P with C. We will refer to S as a (eps,k)-coreset for P.

It is not too hard to show that such a coreset exists of size **O(k*eps-d * log(n) )**, once you come up with the right definition. In fact, being considerably more careful, one can show that one can compute such a coreset of size independent of n (but still exponential in d).

Recently, Ke Chen, showed the existence of the penultimate coresets (see here). Those are coreset of size polynomial in **d**. Namely, the coreset size is **[(d/eps) *log n]O(1)**. Surprisingly, this coreset construction also works for general finite metric (then there is no d, of course).

This leaves open the question of whether one can compute a coreset for k-median clustering of size polynomial in **d** and independent of **n**. This seems like it should be doable, and I am not sure how hard it will be (i.e., it might be easy).

Quoting Sariel Har-Peled :

> On Thu, May 12, 2005 at 05:09:24PM -0500, Apu Kapadia wrote:
> >
> > Okay, so I’m going to assume you will point out something wrong with my
> > argument. Google question on your blog (that I stumbled upon searching for
>
> > “salpha.bst”!):
> >
> > You have two arrays A and B, sorted in descending order.
> >
> > Add the first element of B to all elements of A, and vice versa, to get A’
>
> > and B’. Start picking the highest available element from A’ or B’,
> > advancing pointers as you do so. Whenever you encounter duplicates, they
> > will be adjacent and the pointers for A’ and B’ will point to the
> > duplicates, so you can just skip over them or advance the pointers to the
> > next lower number.
> >
> > Apu
> >
> >
>
> Hmm. The way you describe it, there are only O(n) numbers that you
> can generate, but you can generate n^2 numbers. The best way to think
> about this problem, is to consider the matrix
>
> M[i][j] = A[i] + B[j]
>
> And realize that it is sorted in both rows and columns. Then, you
> just need to sit down and think. You can do what you suggest on the
> matrix, but the set of candidates can be of linear size at some point
> in time, and using a heap makes it too expensive…
>
> bye
>
>

I just realized that my method fails with the counterexample:

10 8 8 8 8 8 8 8 8 8 8 8 8
4 3 3 3 3 3 3 3 3 3 3 3…

I won’t have 11 generated in my method at all…so it’s wrong. I initially
wasn’t thinking in terms of sets, which made it seem very simple.

Will think about it again later in matrix form like you mentioned. Off to IMPE.