Invited and Tutorials

# Invited talks

1. Algorithmic aspects of the Lovász local lemma
Can a needle be efficiently located in a haystack? Sometimes!

Department of Mathematics, National and Kapodistrian University of Athens, Greece

Let $\inline&space;\small&space;X_1,&space;\dots,X_n$ be random variables and let $\inline&space;\small&space;E_1,\dots,E_m$ be "undesirable" events, each depending on a subset of the variables. Suppose that the probabilities of all events are bounded by a number p<1. Obviously, if the events are mutually independent, the probability of an assignment to the variables avoiding all undesirable events (i.e. none occurring) is at least $\inline&space;\small&space;(1-p)^n>0$. Therefore, as the latter probability is strictly positive, we can conclude that there is at least one assignment for which none of the events occur. By an old and much used result of Lovász, the same is true if the events are not independent, but the number of events that each individual event is correlated with is inversely proportional to p, and with constant of proportionality not larger than Euler’s number e. This sufficient condition of Lovász is fortunately weak enough to hold in several cases where the probability of an assignment avoiding all undesirable events is very small (but positive), smaller than $\inline&space;\small&space;(1-p)^n$ (needle in a haystack). So rightly, the extremely simple randomized algorithm designed by Moser (thirty-five years after Lovász' non-algorithmic proof) to locate such an assignment (locate the needle) was hailed as a major algorithmic success. I am going to discuss a very simple direct approach to proving the correctness of Moser’s algorithm and various variants of it. More importantly, I will formulate a condition weaker than that of Lovász that is still sufficient to show the existence of a good assignment (one that avoids all undesirable events). However under only this condition, it seems that it is indeed inherently hard to locate a good assignment. Nevertheless, under this condition, the good assignment will be constructed efficiently, but alas, only through an algorithm that utilizes two interacting computing agents.

2. George Michailidis, Professor and Director of the Informatics Institute, University of Florida, United States