DEPARTMENT OF COMPUTER SCIENCE
DOCTORAL DISSERTATION DEFENSE

Candidate: Babu O. Narayanan

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.