Probabilistic Methods in Computer Science and Combinatorics
11:00 a.m., Thursday, July 8, 1993
Room 1013, Warren Weaver Hall
Over the last few years, the Probabilistic method has become an important tool in Computer Science and Combinatorics. This thesis deals with three applications of the Probabilistic method.
The first problem concerns a model of imperfect randomness: the slightly-random source of Santha and Vazirani. In a slightly-random
source with bias
$\epsilon$, the conditional probability that the next
bit output is 1, given complete knowledge of the previous bits
output, is between
$1/2 - \epsilon$ and
$1/2 +\epsilon$ .
We show that, for every fixed
$\epsilon < 1/2 $,
and for most sets, the probability of hitting that set using a
slightly-random source is bounded away from 0.
The second problem arises in parallel and distributed computing. A
set of n processors is trying to collectively flip a coin, using a
protocol that tolerates a large number of faulty processors. We
demonstrate the existence of perfect-information protocols that are
immune to sets of
$\epsilon n$ faulty processors, for every fixed
Finally, we consider a problem in Ramsey theory. Let an adversary
color the edges of the Binomial random graph with r colors, the edge
$ c / (\sqrt n)$, where c is a large enough
constant. We show that, almost surely, a constant fraction of the
triangles in the graph will be monochromatic.