Vanity of Vanities, all is Vanity

when you are unable to fall asleep, and you already tried everything, including trying to read a book, count sheeps, and seeing Fox news 2am special on “are democrats an instantiation of the Antichrist?”. You are desperate for sleep. But don’t worry no more, because we have the cure, I reckon a survey on coresets would make you fall asleep mighty fast.

One of the nice aspects of living in a town dominated by a large university, is that bizarre topics that would not be discussed in other place, might be in the center of discussion. But the following mysterious election sign, calling to vote in favor of “plus two factorial”, put up by one of the aborigine, leave me in complete bewilderment.

!

One of the nice aspects of living in a town dominated by a large university, is that bizarre topics that would not be discussed in other place, might be in the center of discussion. But the following mysterious election sign, calling to vote in favor of “plus two factorial”, put up by one of the aborigine, leave me in complete bewilderment.

!

Full image is here.

Here is one of my favorite open problems.

Let **P** be a simple polygon in the plane. The _art gallery_ problem asks to find a minimum number of guards (i.e., points) that sees the whole polygons. A guard is just a point that can see in all directions but not through the walls of the polygon. There is a classical result in CG showing that by triangulating the polygon, and since the triangulation is 3 colorable, one can always place at most n/3 guards in the vertices of the polygon, and they will see the whole polygon.

But what if only **k** guards are needed? Can we compute those **k** guards efficiently? The answer is probably no. In fact, even approximating the number of guards up to a constant is hard. But, can we **log(n)** approximation? Can we do **log(k)** approximation?

The answer to both question currently is that I don’t know, and as far as I know this is open. If one limit the guards to lie on the vertices of the polygon (or to any other finite set of allowable locations), then this is no more than a set cover problem. One can use the greedy algorithm, and get O(log(n)) approximation. In fact, Valtr showed that the VC dimension of visibility polygons is **<= 23** (in P. Valtr, Guarding Galleries Where No Point Sees a Small Area, Israel J. Math., vol. 104, pp. 1-16, 1998.). As such, one can use Clarkson reweighting technique to compute a **O( log (kopt))** approximation, where **kopt** is the number of guards used in the optimal solution (see here).

As mentioned before, it is also known that the problem is hard to approximate within a constant factor. In fact, it is not hard to see (using perfect hindsight, or just the paper by Chwa et al.) that here is no hope for a witness set construction here. Namely, one can not hope to compute a set of points in a polygon P, such that if you guard all those points, then you are guaranteed to see all the points in the polygon.

It is natural to try and get an approximation algorithm using greedy strategy for set covering. Namely, repeatedly finding the guard that sees the largest area which is not guarded yet, and repeat it. This approach has two major problems, the first one is that finding the guards that sees most is not easy (although a quadratic time approximation algorithm is known). The second hurdle is that we dont know how to argue when this strategy stops – namely, how many guards it is using.

At this point, it seems like any hope for progress will only rise from better understanding of the exact algorithm which uses real algebraic techniques (see here). Whatever the path is, any progress on the general problem here would be exciting. In particular, an algorithm that works in polynomial time and outputs a set of guards using, say, **O(n1/2 *kopt2)** guards would be exciting, where n is the number vertices of the polygon, and **kopt** is the minimum number of guards used by the optimal set of guards.

Some people (i.e., dim, far-fetched and ambiguous) are complaining about clueless students. So, this is a great occastion to expose the fact that this is old news (or quoting Ecclesiastes “and there is no new thing under the sun”). Here some quotes from answers given by students long time ago:

1. The imports of a country are the things that are paid for, the exports are the things that are not
2. The two most famous volcanoes of Europe are Sodom and Gomorrah.
3. The principal products of the U.S. is earthquakes and volcanoes.
4. Luther introduced Christianity into England a good many thousand years ago. His birthday was November 1883. He was once a Pope. He lived at the time of the Rebellion of Worms.
5. DEMAGOGUE, a vessel containing beer and other liquids.

There are a lot of other gems in “ENGLISH AS SHE IS TAUGHT” by Mark Twain.

Saw yesterday the movie “Team America: World Police”. Similar to the south park movie, this is a hilariously funny movie.

And you might want to read the debate that never happened.

There is an interesting op-ed by Deborah Tannen in the NYT about the failure of Bush in admitting mistakes, and how infuriating (some) women find it. Reading it I thought that maybe the author is over estimating the value of apology and asking for forgiveness.

Indeed, when I was growing up, it downed on me, that when we ask forgiveness, we are not asking for forgiveness, we are demanding it. By humiliating ourself to the point where we ask forgiveness, we had gained the right to be forgiven, at least in our minds. Thus, forgiveness is no longer the coin of the giver to give, but of the taker to take. And so, forgiveness becomes the easy way out, thus not requiring any real regret on the part of the sinner. Thus, the church became a factory of forgiveness, giving the people forgiveness in measured doses every Sunday.

So, the second edition of the CG handbook is out (was out for the last half a year I think). At >1500 pages it is a hefty addition to anybody library. Interestingly, it has no chapter on approximation algorithms. Hmmm.

Anyway, it is getting to the point where it is physically inconvenient to read. Maybe an electronic handbook would be a better investment (to mention the trees saved). In fact, if you have surveys that you think should be mentioned in the virtual handbook, send me a link…

There is a lengthy and tedious article in the NYT about the intellignce that lead to the war in Iraq. Nevertheless, this article is worth a read. This article got mentioned in slashdot, under the title “White House Lied About Iraq Nuclear Programs”. This is both inaccurate, and makes an issue that should not be politicized into a political issue.

What the article essentially documents is a failure of the intelligence system. In fact, the failure was more in the inability of the strong differing views to percolate into the higher levels of decision making. In particular, the CIA has a direct access to the president, while other agencies don’t. In particular, the CIA was relying essentially on one expert, in making their judgement about the usage of aluminum tubes for making centrifuges for getting enriched uranium. The issue at hand was whether Iraq was trying to build a nuclear bomb. The expert was **wrong**. In fact, the expert was clearly wrong, and other experts in other Agencies pointed it out (especially people the energy department).

However, the decision makers got very one sided picture of this argument. Hearing only the side of the CIA. Only when the whole argument became mute, did the argument in the intelligence level reached the white house.

This wrong intelligence was one of the main reasons the Bush administration used to support the war (we need to act now, before the evidence would be a nuclear mushroom). What this story exposes above everything else is a systematic failure in the intelligence management in the US. In particular, the decision makers were unaware to strong arguments about interpretation of evidence. The CIA was able to send memos to the president that were not provided to other agencies (i.e., the enemy?). A single expert, was essentially able to skew the intelligence picture provided to the president, although his view was a minority among experts on the topic.

This is not the only intelligence failure the US had recently experienced. The failure in 9/11 exposed a similar systematic structural failure, where the CIA had information that if it was provided to the FBI would have, with high probability, prevented 9/11.

Intelligence is a very fuzzy topic, sometime based on interpreting very few facts, and based on unreliable sources. And as the above demonstrate, intelligence agencies are not infallible. This is an expensive lesson Israel learnt at 1973, when despite several very clear signs of looming war, the intelligence agencies because of a “concept” failed to predict this war. Following the Yom Kippor war, drastic changes in the way Israel collect and analyze intelligence information were made. In fact, it is quite common in Israel to hear that the head of Army Intelligence is disagreeing with the Mosad head about interpreting the known facts. Usually when they both appear before some committee in the Israeli Kenest.

So, would we see similar changes in the US system? I doubt it. The US government is a huge (and almost monolithic) bureaucracy. Structural changes takes decades (Richard Clarke has a lot of interesting information about this in his book “against all enemies”). The most crucial thing is probably a new body that would decimate the intelligence from various sources and agencies, and deliver it to the decision makers (together with conflicting views if such exist). While essentially such a proposal is included in the recommendations of the 9/11 committee, it seems like the current administration is trying to wish-wash it away.

In the end of the day, any politician mentioning information from intelligence to support his or her views, might in the end of the chain rely on some clueless guy in the CIA, and despite the billions of dollars the US put into it, the intelligence just might be wrong. It was wrong so many times in the past.

The BBC is broadcasting parts of the HG2G that were not broadcast before on radio. One can here it online here.

On a completely unrelated note, in Linux one way of turning realplay input into mp3 files, is by doing:
:

vsound realplay bogi.ram
lame vsound.wav