## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, May 26, 2011, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Thomas Rast

## Buffon machines

Buffon (1777) posed the famous needle experiment: throw a unit needle randomly onto an infinite sheet of paper with parallel lines at unit intervals. Then the probability of the needle intersecting a line is 2/pi. It can be considered as taking continuous random inputs and giving {0,1} output (termed "failure" and "success") with certain probabilities.

Flajolet, Pelletier and Soria (SODA11) transformed this into a more combinatoric setting by considering *Buffon machines* which are allowed only coin-flip randomness inputs. The goal is to make the probability of success some interesting number, such as 1/e, 1/pi, erf(x) or zeta(3). This surprisingly is possible with very short programs and a low expected number of coin flips, e.g., in the case of pi/12 less than 5 (!).

We will give an introduction to the setting and an overview of the constructions done by Flajolet et al. Then, time permitting, we will look at a few constructions in more detail. Text

Information for students and suggested topics for student talks