## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, October 04, 2012, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Timon Hertli

## Using Integrals to Compute Probabilities on Permutations

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.

Information for students and suggested topics for student talks