Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 04, 2012, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Timon Hertli
Suppose you want to compute the probability that in a random permutation some element x comes before element y and z, or before element c and d. One way to compute this is to list all subpermutations on the involved elements, but this becomes quickly infeasible.
There is a nice technique to compute such probabilities. It was first used to analyze the famous PPSZ algorithm for k-SAT by Paturi, Pudlák, Saks and Zane. I used it also in my semester thesis for a similar topic.
We can make permutations continuous as follows: For each element x, we choose a real number u.a.r. in [0,1] (the "place" of x); the permutation is then obtained by ordering the elements in ascending order. By symmetry, we again obtain a (uniformly) random permutation. The places of the elements are independent, unlike the positions in a permutation. Using this independence, probabilities like the above can then be computed using simple integrals.
In the talk I will first introduce the technique and will give some examples what to do with it; among them how it is used in the analysis of the PPSZ algorithm. I think this technique is nice to know, even if it is quite simple and, as far as I know, not used outside of SAT yet.
Automatic MiSe System Software Version 1.4803M | admin login