Today, I attended a very good talk given by Emo Welzl of ETHZ. I could not quite appreciate the drinks and snacks prior to the event, since the organizers kept too little of them and by the time I arrived, smart guys had grabbed hold of almost all of them. I had to content with a glass of orange juice! Anyway nothing comes free in this country. So getting an orange juice is itself luxury, one would say! Nevertheless, glad that I attended this talk. Monika Henzinger did the speaker introduction part, which she did very well. She mentioned that Emo comes from the same village as that of her husband (Thomas Henzinger). That is not really relevant, but I like such personal, less formal introductions. It takes the audience to a touch curious and close. He indeed proved her (Monika promised us that we are in game for a great talk) right with a truly nice lecture, calm, composed and thoughtful;words precisely chosen, well articulated throughout. He gave some insights into a problem which was never known to me. My field is not quite into SAT or algorithms, but at the end of this talk, I got to learn some thing. Moreover, he instigated me to learn a little more about these nice problems.
Here is a gist of what I understood. If you are interested in the talk subject, perhaps you should visit his homepage. What I state down is something my little brain, which never for once trained on this topic, digested out. Suppose we are given a Boolean function (that is a logic function which has either true or false, equivalently 0 or 1 results). Deciding satisfiability (known as SAT problem) of such formula in conjunctive normal form is known to be an NP complete problem. He discussed some nice (surprisingly simplified bounds) combinatorial bounds on the number of clauses (or equivalently constraints) for unsatisfiability. As usual in talks, I hardly could grasp the proof in total, but he began quoting the Lovász lemma as an essential ingredient. I got to learn a little bit about this rather nice and cute lemma. Loosely the lemma has the following setting.
If we consider a sequence of events where each of these events occur with a probability at most . Suppose each event is independent from all other events, except at most of them, then , where is the Napier constant (named after the famous Scottish mathematician John Napier). This did not strike me instantly, but pondering a little bit about it, I have realized that this is really cute a bound. I can think of a nice, little example scenario, where this can be applied. Let me figure out another cute one. You can expect me to post it. Now let me get back to that optimization problem on compound sets of channels that I have been stuck for the last four days.