Theory Day March 2, 2009 - Noga AlonColor Coding, Balanced Hashing and Approximate Counting Abstract: Color Coding is an algorithmic technique for deciding efficiently if a given input graph contains a path of a given length (or another small subgraph of a certain type). It illustrates well the phenomenon that probabilistic reasoning can be helpful in the design of deterministic algorithms. Applications of the method in computational biology motivate the study of similar algorithms for counting the number of copies of a given subgraph. While it is unlikely that exact counting of this type can be performed efficiently, approximate counting is possible, and leads to the investigation of an intriguing variant of families of perfect hash functions. Joint work with Shai Gutner |