DEPARTMENT OF COMPUTER SCIENCE

DOCTORAL DISSERTATION DEFENSE

Candidate: Babu O. Narayanan

Advisor: Ravi B. Boppana

DOCTORAL DISSERTATION DEFENSE

Candidate: Babu O. Narayanan

Advisor: Ravi B. Boppana

**Probabilistic Methods in Computer Science and Combinatorics **

11:00 a.m., Thursday, July 8, 1993

Room 1013, Warren Weaver Hall

Abstract

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
`$\epsilon< 1/2$`

.

Finally, we consider a problem in Ramsey theory. Let an adversary
color the edges of the Binomial random graph with *r* colors, the edge
probability being `$ 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.